동형암호 알고리즘의 실제 적용?

https://stackoverflow.com/questions/1023981

06-07-2019
|

문제

암호화 분야에서 흥미로운 일이 벌어지고 있는 것 같습니다.첫번째 동형암호 최근에 등장한 계획 (설명, HT).대략적으로 말하면 인코딩 방식이다. x ~ 안으로 f(x) 계산할 수 있도록 f(x+y) 쉽게 아는 f(x) 그리고 f(y) 쉽게 복구할 수 없더라도 x 그리고 y (그리고 동일 f(x*y)).

이러한 유형의 계획에 대한 실제 적용은 무엇입니까(보안이 확립된 후)?나에게는 개인 데이터를 조작하기 위한 알고리즘 작성을 훨씬 쉽게 만들 수 있는 것으로 보입니다.

여기 있습니다 내 생각:

전자투표
개인 데이터의 무결성 확인
일반적으로 개인 정보 보호에 도움이 될 가능성이 있습니까?

예:A, B, C 은행에 계좌가 있습니다.Entity X는 총 금액이 $1000 이상인지 확인하고 싶어합니다.A, B, C, D 은행의 명세서를 기꺼이 받아들일 것입니다. 하지만 불행히도 단일 계좌에 돈이 충분하지 않습니다.A 은행은 내 공개 키를 사용하여 500달러에 대한 정보를 암호화합니다.마찬가지로 은행 B와 C는 내가 각각 $200와 $300를 가지고 있다는 정보를 암호화합니다.그들은 이 데이터를 X에게 보내고 X는 이를 실제로 $1000로 암호화된 것으로 증명하는 숫자에 추가합니다(내 공개 키로 $1000를 암호화하고 결과가 동일하다는 것을 증명함으로써).나는 공개하지 않고 무언가를 증명했습니다. X 각 계좌에 내가 가진 돈이 얼마나 되는지.

다른 예시:좋은 시민 X_1, ..., X_n이 팀을 이루어 두 후보 중 한 명을 선택하고 있으며 그 중 한 명은 라떼를 마시는 리버입니다.ㅏ난 다른 사람은 비총을 소지한 총 애호가(모든 이름은 허구입니다).그들은 투표가 비공개이지만 신속하게 진행되기를 원한다고 결정합니다.벡터 형식으로 투표를 보냅니다. (1, vote_A, vote_B, vote_None) 이를 공개적으로 추가하고 다음 형식으로 결과를 얻는 선거관리위원회에 암호화됩니다. (count, count_A, count_B, count_None).그걸 확인한 후 count = count_A + count_B + count_None, 관리들은 후보자 중 한 사람의 승리를 선언하고 그 후 전자 투표와 관련이없는 어떤 이유로 판사에 의해 선거가 무효라고 선언되고 향후 10 년 동안 법원에서 싸웠지 만, 어쨌든 그건 내 문제가 아닙니다.

노트:- 한 번의 작업에서 동형성만 필요하기 때문에 이전에도 RSA를 사용하여 이러한 특정 예가 가능했다고 생각합니다.우리는 더 많은 작업을 통해 근본적으로 더 흥미로운 것을 얻을 수 있기를 희망합니다. 따라서 예를 생각해 보세요!

특히 실제로 사용될 가능성이 있는 코드 및/또는 개발 프레임워크가 포함된 답변을 보고 싶습니다. SO인 이유는 이론적인 컴퓨터 과학 토론 게시판이 아닙니다.
아래 주석에서 설명한 내용을 반복하는 동형 알고리즘을 사용하면 데이터를 알지 못한 채 데이터를 관리하는 프로그램을 만들 수 있습니다.불행히도 프로그램 유형은 다소 제한되어 있습니다.당신은 가질 수 없습니다 if (x=0) ... 왜냐하면 x 암호화되어 있으며 각 단계가 매우 느립니다(일부 격자가 관련되어 있음).

해결책

여기 어둠 속에서 야생 샷이 있습니다.

우리는 계산을 수행하는 사람으로부터 일반 텍스트를 보호 할 생각입니다. 그러나 목표가 일반 텍스트와 알고리즘을 모두 보호한다면 어떨까요?

예를 들어 MRI 기계를 가져 가십시오. MRI 기계의 가장 비싼 부분은 기계가 자기 공명 데이터를 분석하는 알고리즘입니다. 이로 인해 그들은 신뢰할 수없는 당사자 (또는 그 문제에 대한 사람)가 자체 검사하기 전에 프로그램을 파괴하도록 설계된 하드웨어 장치에 의해 크게 보호됩니다.

MRI 메이커가 MRI 데이터 컴퓨팅을 중앙 집중화 할 수 있다면 알고리즘을 잃을 위험이 환상적입니다. 그러나 법률에 따르면 개인 환자 데이터에 액세스 할 수 없습니다.

그래서! 동종 암호화를 통해 환자 데이터와 알고리즘이 모두 보호되는 경우 이런 일이 발생할 수 있습니다. '완전'동종 암호화 (즉, 암호화 된 데이터에 대한 링 동질성을 유도 함)는 데이터에서 작동하는 훨씬 더 효율적이고 강력한 계산 세트가 가능합니다.

다른 팁

PKI 괴짜로서, 동형 암호화 함수가 비대칭 키 시스템이었다면 서명 세계에서 정말 흥미로운 가능성이 있습니다.서명자는 잠재적으로 메시지에 서명할 수 있고 수신자는 메시지를 다시 전송할 수 있습니다. 부분 메시지 및 암호문의 해당 부분을 제3자에게 공개합니다.

함수 표기법에서는 다음과 같습니다.

사용자 표시:

sign(일반 텍스트, 개인 키) = 암호문

그리고 다음을 전송합니다:

보내기(일반 텍스트, 암호문, 인증서)

애플리케이션이 세그먼트를 가져옵니다.

일반 텍스트 = 원하는 일반 텍스트 + 기타 일반 텍스트

다음과 같은 방법을 사용하여 동일한 암호문 변환을 계산합니다.

ciphertext::plaintext이면 ??::desiredPlaintext

원하는 암호문을 찾으려면

애플리케이션은 원하는 콘텐츠를 외부 서비스에만 전달합니다.

보내기(원하는 일반 텍스트, 원하는 암호문, 인증서)

그리고 서비스는 마치 사용자가 직접 보낸 것처럼 이 메시지를 확인할 수 있습니다.

이는 동형인 일반 텍스트를 압축하는 데 사용되는 해시 알고리즘에 따라 달라집니다.그렇지 않으면 이 일이 안 되겠죠...또는 해시 알고리즘이 적용되지 않습니다.

이는 서명된 사용자 요청에 대한 응답으로 외부 서비스가 어떤 작업을 수행하기를 원하지만 사용자가 해당 외부 서비스에 보낸 모든 것을 노출하고 싶지 않은 경우에 매우 유용할 수 있습니다.

한 가지 예는 간단한 패키지 주문 시스템입니다. 웹 앱에 항목 컬렉션 구매 요청을 보냅니다.철저한 보안을 유지하기 위해 일부 품목을 특정 날짜까지 특정 결제 정보와 함께 특정 위치로 배송하기를 원함(그리고 비용을 지불할 것을 약속함)을 확인하는 구매 주문서에 서명합니다.지금..웹 앱은 여러 가지 일이 일어나기를 원할 것입니다:

금융 기관에서 내 계좌에 비용을 청구하고 나로부터 대금을 받기 시작해야 합니다.
재고는 재고에서 품목을 가져오거나 재고 부족 문제를 처리해야 합니다.
배송은 재고에서 수령하고 물건을 내 주소로 옮겨야 합니다.

재고나 배송팀에서 청구서 지불 방법을 알 이유가 없습니다.그리고 재무팀이 내 배송 주소를 알 이유가 없을 수도 있습니다...각각의 경우에 원하는 일반 텍스트와 원하는 암호 텍스트는 수신자가 누구인지에 따라 변경됩니다.이는 내가 구매한 주체(Amazon)와 항목을 제공하는 주체(중고 도서 판매자)가 다른 Amazon.com 중고 도서와 같은 시스템에서 훨씬 더 강력합니다.

격자 암호화에 관한 논문을 읽으면 대칭 키 시스템처럼 들립니다.이는 메시지에 서명하는 데 그다지 도움이 되지 않습니다.

"절대로 말하지 않는다(never say never)"라는 개념에 대해 개인 정보 보호 애플리케이션에 사용하는 것이 불합리하다고는 말하고 싶지 않습니다.그러나 암호문에서 일반 텍스트로 전환하는 여러 가지 방법을 찾을 수 있다는 것은 확실히 문제가 있는 것 같습니다.

동종 암호화의 가장 큰 적용은 IMHO 데이터 마이닝에 있습니다. 이 알고의 사용은 개인 정보 보호 및 트렌드 발견의 문제를 동시에 해결할 수 있습니다. 예를 들어, 회사가 일부 SAS 제공 업체에서 판매 정보를 호스팅한다고 가정 해 봅시다. 이제 해당 제공 업체는 실제 정보를 실제로 공개하지 않고도 정교한 데이터 마이닝 서비스를 제공 할 수 있습니다. 기본적으로 데이터를 계산 공급자에게 보내고 CPU주기를 활용하여 귀하를 대신하여 계산하고 암호화 된 데이터를 다시 보낼 수 있습니다. 클라우드 기반 시스템으로 이동하려고하지만 개인 정보 보호 / IP 우려 사항이있어서 그렇게하지 못하게하는 회사에게는 정말 환상적입니다.

더 낮고 개인적인 차원에서 또 다른 잠재적 인 응용 프로그램은 모든 종류의 재무 데이터를 처리하는 것입니다. Ilya의 예제 확장 된 예는 실제로 재무 정보, 신용 카드 처리 등을 실제로 보지 않고 회계사의 세금 신고서 제출에 적용될 수 있습니다.

그러나 계획이 엄격하게 테스트되고 안전하다고 간주 될 때까지 내 흥분을 유지했습니다. 암호화 조류는 첫 번째 시험에 실패하고, 수정을 받고, 일부 정부 당국에 의해 "인증"될 때까지주기를 반복하는 악명 높은 습관을 가지고 있습니다.

Bruce Schneier의 동종 암호화에 대한 Bruce Schneier의 다소 부정적인 테이크를 보는 데 관심이있을 수 있습니다.

http://www.schneier.com/blog/archives/2009/07/homomorphic_enc.html?nc=11

나는 얼마나 비싸다 f(x) + f(x) 계산은 아마도 암호화 된 데이터베이스를 구현하는 방법으로 사용될 수 있습니다.

암호화 된 일부 데이터 1 백만 행을 저장할 수 있습니다. f(x_1), f(x_2), ... f(x_n). 당신은 할 수 있습니다

SELECT SUM(x)
FROM Foo
WHERE y = 'some value'

처음으로 계산할 수 있습니다 SUM(f(x)) 그런 다음 해독합니다 SUM(x).

이를 사용하면 경계 깊이의 임의의 비수체 회로를 실행할 수 있으므로 로그 키 길이가 주어지면 NC1 알고리즘 (기본적으로 피드 포워드 부울 회로)을 실행할 수 있습니다.

그렇다면 어떻게 이것을 사용할 수 있습니까?

입력 세트를 통해 회로 및 감소 체계를 맵/감소를 살펴 보겠습니다.

먼저 데이터 :

우리는 클라이언트가 검색하려는 모든 데이터를 암호화하지 않아도되므로 암호화 된 1과 암호화 된 0을 서버에 제공하고 링 구조를 사용하여 임의의 암호화 된 정수를 구성 할 수 있습니다. 우리에게, 또는 우리는 그것들을 비트로 직접 사용할 수 있습니다. 이렇게하면 서버가 검색하는 일부 또는 모든 데이터를 제공 할 수 있습니다. 정수의 경우 농민 산술 (이중 또는 이중 및 각 비트마다 1을 추가)으로 구성 할 수 있습니다. 비트는 적절한 암호화 비트를 제공합니다.

우리는 설계에서 부울과 정수 값을 혼합하고 일치시킬 수 있으며, cond * + (1 -cond)를 평가하여 if/when/else (두 가지 simd 스타일을 평가해야 함)를 얻을 수 있습니다. Cond에서는 링의 내장 산술을 사용하여 회로를 더 얕게 만들 수 있습니다.

다른 한편으로, 우리는 일부 데이터도 사전 암호화했을 수도 있지만, 동일한 키 세트를 계속 사용하기 위해 동일한 키 세트를 계속 재활용해야하므로 이는 제대로되기 위해 심각하게 까다로워집니다.

이제 서버가 제공 한 데이터가 있습니다. 이제 서버가 검색하는 것과 같이 서버가 알기를 원하지 않는 것들을 암호화하고 맵 함수에 대한 추가 입력이라고 말하면 올바른 지점의 회로에이를 공급하도록하십시오.

각 입력에 임의의 NC1 유사 회로를 매핑하여 필드를 추출하고 일부 값을 곱한 다음 일반적으로 저렴하게 줄일 수있는 형태로 매핑 할 수 있어야합니다.

그런 다음 크기가 잘 된 결과가있는 간단한 모노이드와 같이 더 작은 회로를 사용하여 조각을 줄입니다. (즉, 매치를 찾았는지 나타내는 비트를 얻기 위해 맵핑을 한 다음 작은 가산기 회로로 비트를 계산하여 줄어 듭니다).

회로를 논리적으로 구성하고 동종 반지에서 이러한 암호화 된 비트에서 실행을 시뮬레이션하면되므로 작은 DSL을 사용하여 비교적 빠르게 구현할 수 있습니다. 즉, Haskell의 Lava와 같은 무언가를 동질성 암호화 조각을 똑바로 똑바로 입수했다고 가정 할 수 있습니다.

또한 각 게이트가 있음을 명심하십시오 진지하게 실행 비용이 많이 듭니다.

따라서 요약하기 위해

서버에 암호화 된 1과 0과 맵에 암호화 된 metainfo를 제공하고 함수를 줄입니다.
각 데이터 포인트에 대해 동종 링에 인코딩하고 입력과 메타 정보를 모두 공급하여 감소에 적합한 값을 얻습니다.
균형 잡힌 바이너리 트리 (또는 트리 높이를 최소화하기위한 기타 균형 잡힌 배열)에서 감소 작업을 회로의 출력 및 암호화 된 MAP Metainfo에 적용하십시오.
암호 해독을 위해 결과를 클라이언트에게 넘겨주십시오

기존 동종 암호화 알고리즘의 문제점은 Polylogarithmic (NC1) 회로 만 실행할 수 있다는 것입니다.

또한 인코딩의 복잡성이 폴리로 게라리트 회로를 직접 실행하는 복잡성보다 낮은 방식으로 낮은 것으로 보이지 않으므로 특히 까다로운 일을하지 않는 한 First Blush에서 무료 작업을 선택하지 않았습니다.

seti@home, 단백질 폴딩 프로젝트 등과 같은 분산 컴퓨팅은 수천 명의 사용자의 CPU 시간과 전기의 기부를 활용하기 때문에 상당히 인기가 있습니다. 더 흥미로운 것은 사람들이 상업 프로젝트에 이러한 자원을 제공하기 위해 돈을받을 수있는 모델입니다. 그러나 책임있는 회사는 처리를 위해 수천 개의 익명 컴퓨터에 데이터를 배송하려고합니다. 암호화 된 데이터에 알고리즘을 효율적으로 적용 할 수 있다면 신뢰할 수있는 관계가없는 사람에게 처리를 위임 할 수 있습니다.

전자 투표는 실제로 동종 암호화의 실질적인 적용입니다. http://heliosvoting.org/

동종 암호화의 도움으로 일부 은행 신청은 더 빨라질 수 있습니다.

클라우드에서 로컬로 가져 가서 클라우드에 다시 넣는 대신 클라우드에서 암호화 된 데이터로 작업을 수행 할 수 있습니다. 또한 결합 기능을 암호화 할 필요가 없습니다. 암호화 파이프 라인, 암호화 성능 작업은 괜찮을 것입니다.

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow