편집자 주: 이 기사의 출처는앰비랩스(ID: secbitlabs), 승인을 받아 Odaily에서 재인쇄했습니다.

편집자 주: 이 기사의 출처는

앰비랩스(ID: secbitlabs)

, 승인을 받아 Odaily에서 재인쇄했습니다.

얼마 전에 저는 스탠포드에서 CS355(고급 암호화) 과정을 수강했습니다. 우리는 Dan의 박사 과정 학생 세 명인 Dima Kogan, Florian Tramer 및 Saba Eskandarian이 가르쳤습니다. 3명의 박사강사는 각자의 특성이 있고 연구 방향도 매우 다르다. Dima는 개인 정보 보호 기술 PIR(Private Information Retrieval)에 중점을 두고 Florian은 ML 및 블록체인 연구에 중점을 두고 Saba는 영지식 증명에 중점을 둡니다.

CS355 고대부터 현재까지의 암호학 분야의 거의 모든 것을 다룬다. 최초의 단방향 함수(One-way Function)부터 타원 방정식(ECC) 및 페어링, 마지막으로 인기 있는 일부 MPC, 영지식, 개인 정보 검색(PIR), 완전 동형 알고리즘 등 최근 몇 년 동안 . 수업이 이틀 전에 끝났기 때문에 지식 콘텐츠가 아직 얕은 기억에 남아 있는 동안 노트 웨이브를 정리했습니다. 강의내용도 너무 재밌고 나머지 내용은 시간날때 공유할게요~

이번 호에서는 최근 인기를 끌고 있는 FHE(Fully Homomorphic Encryption)와 이에 수반되는 Lattice 기반 암호화 기술에 대해 이야기하겠습니다.

보조 제목

완전 동형암호란?

FHE(Fully Homomorphic Encryption)라는 이름을 많은 친구들이 들어봤을 것입니다. 최근 몇 년 동안 개인 프라이버시 보호에 대한 주제가 점점 더 많아지고 있으며, 동형암호를 비롯한 일련의 암호 응용 기술도 널리 보급되고 있습니다.

이 주제를 더 잘 이해하기 위해 완전 동형 암호화의 정의를 간략하게 소개하고자 합니다.

• 암호화 시스템 검토

• 시작하기 전에 가장 전통적인 암호화 시스템을 검토해 보겠습니다.

• 우리 모두는 암호화 시스템을 구축하려면 종종 키(Key)가 필요하다는 것을 알고 있습니다. 이 키를 통해 한쪽 끝에서 평문 정보를 암호문으로 암호화한 다음 다른 쪽 끝에서 키를 통해 암호문을 원래 형태로 다시 변경할 수 있습니다. 이 키가 없으면 우리가 어떤 정보를 전달했는지 다른 사람들이 알기 어렵습니다.

위의 그림은 기본적으로 모든 일반적인 암호화 시스템의 전체 그림을 보여줍니다. 모든 암호화 시스템은 좀 더 공식적인 방식으로 설명하면 의심할 여지 없이 세 가지 작업을 수행합니다.

먼저 암호화와 복호화를 위한 한 쌍의 키가 생성 알고리즘에 의해 무작위로 생성됩니다.

암호화 당사자는 암호화 키와 암호화 알고리즘을 통해 원본 텍스트를 암호화하고 최종적으로 암호문을 얻습니다.

그러면 복호화 시 복호화 당사자는 복호화 키와 복호화 알고리즘을 통해 암호문을 복호화하고 최종적으로 원본 원본을 복원할 수 있다.

암호화 알고리즘에 대해 아는 친구는 AES, RSA 등과 같은 일반적인 암호화 알고리즘을 확실히 알고 있을 것입니다. 암호화 시스템은 일반적으로 대칭 암호화 시스템과 비대칭 암호화 시스템의 두 가지 유형으로 나뉩니다. 여기서 설명하는 세 단계는 모든 암호화 시스템에 적용할 수 있습니다. 대칭이면 암호화와 복호화에 사용되는 키가 동일합니다. 비대칭 시스템이라면 암호화는 공개키(Public Key)를 사용하고 복호화는 다른 개인키(Private Key)를 사용한다.

암호 연구에서 우리는 새로운 시스템의 정의를 볼 때마다 이 시스템이 가져야 할 속성(Properties)을 명시해야 하는 경우가 많습니다.

첫째, 구현할 첫 번째 속성은 정확성입니다. 정확성이란 올바른 키가 있으면 복호화 알고리즘을 통해 암호문을 원본 텍스트로 복원할 수 있음을 의미합니다. 복호화 성공률을 표현하기 위해 종종 확률 방법을 사용합니다.

위의 방정식은 우리가 올바른 키를 가지고 있다면 복호화 알고리즘이 암호화 알고리즘에 의해 생성된 암호문을 복원할 수 있는 확률이 100%임을 나타냅니다.

달성하고자 하는 두 번째 속성은 Semantic Security입니다.

시맨틱 보안의 정의에 대해서는 여기에서 설명하지 않습니다. 그러나 서로 다른 원본 텍스트에 해당하는 두 개의 암호문이 있는 경우 어떤 암호문이 어떤 원본 텍스트에 해당하는지 구별할 수 없다는 것을 이해할 수 있습니다.

시맨틱 보안의 주요 의미는 구경꾼이 두 개의 암호화된 메시지를 구별할 수 없다는 것입니다. 따라서 침입자가 네트워크를 도청하고 내가 보낸 암호화된 정보를 본다면 내가 사용하는 암호화 시스템이 의미론적으로 안전한 한 침입자가 암호문에서 암호화된 내용에 대한 정보를 얻을 수 없다고 확신할 수 있습니다.

위의 두 가지 속성을 만족하면 암호화 시스템이 건전해집니다.

동형암호: 우발적인 특수 속성

암호화 시스템이 무엇인지 이해한 후 무작위로 생성된 왜곡된 문자로 보이는 이 암호문에 주의를 기울일 수 있습니다. 우리 모두는 암호문 자체를 보는 것만으로는 어떤 정보도 얻을 수 없다는 것을 알고 있습니다. 그러나 이것은 키가 없고 암호문만 있으면 아무것도 할 수 없다는 것을 의미합니까?

우리 모두는 답을 알고 있습니다. 그렇지 않습니다.

그러나 많은 암호화 알고리즘 중에서 알고리즘 클래스에 의해 생성된 암호문에는 특별한 동형 속성이 있습니다. 암호화 알고리즘을 사용하여 숫자 1의 암호문을 얻으면 숫자 2의 암호문을 얻습니다. 이때 암호문을 더하면 바로 암호문이다!

이 속성에 대해 가산 동형사상이라고 합니다. 즉, 암호화된 암호문은 이전 원본 텍스트와 미묘한 대수적 관계를 유지합니다. 암호문을 합산하면 원본을 합산하고 암호화하면 새로운 암호문을 얻을 수 있습니다. 같은 방식으로 가산적 준동형 외에도 곱셈적 준동형을 가진 암호화 알고리즘도 있습니다. 곱셈 동형 알고리즘으로 생성된 암호문을 곱한 다음 원본 간의 곱셈 결과에 해당하는 암호문을 얻을 수 있습니다. 전체 프로세스에서 우리는 키와 관련된 정보를 알 필요가 없으며 무작위로 왜곡된 코드처럼 보이는 암호문을 결합하기만 하면 됩니다.

예: 익명 투표 시스템

다음으로 동형암호의 실용성을 생생하게 설명하는 예를 들어보자.

우리 모두는 온라인 투표가 어떤 것인지 알고 있습니다. 회사의 상사가 투표의 물결을 일으키고 싶다면 회사가 996 시스템을 채택해야 하는지 여부를 선택하십시오. 그런 다음 상사는 IT에 서버를 설정하도록 요청하고 직원이 자신의 선택을 제출하도록 할 수 있습니다. 아니오에 0, 예에 1로 투표하십시오. 최종 투표 기간이 지나면 보스는 모든 투표를 합산할 수 있습니다. 최종적으로 모든 투표의 합이 직원 수의 절반을 초과하면 회사는 996을 시작합니다.

이 투표 메커니즘은 매우 간단해 보이지만 큰 사생활 보호 문제가 있습니다. 상사가 모든 직원이 마음 속으로 996이 되기를 원하지만 어떤 직원이 초과 근무를 원하지 않는지 알아보기 위해 일부러 피싱 법 집행 기관에 이 투표를 시작했다면 다음과 같습니다. 사장님은 조용히 남동생에게 인터넷 도청을 맡기고 각 직원이 제출한 선택 사항을 기록하고 마지막으로 누가 0표를 줬는지 확인할 수 있습니다. 그 결과 직원들은 매우 두려워하고 감히 마음을 털어 놓지 않습니다.

가산 동형암호 알고리즘을 사용할 수 있다면 이 문제를 쉽게 해결할 수 있습니다.

첫째, IT는 KeyGen 알고리즘을 사용하여 암호화 및 복호화 키 쌍(pk, sk)을 생성한 다음 공개 키를 각 직원에게 배포할 수 있습니다.

그 후 각 직원은 암호화 알고리즘을 통해 자신의 선택(1 또는 0)을 암호문으로 암호화한 다음 암호문을 IT 서버로 보냅니다.

마지막으로 IT 부서는 모든 사람의 선택을 합산하고 결합된 암호문을 얻은 다음 이 암호문을 상사에게 보낼 수 있습니다. 마지막으로 보스는 해독된 키를 사용하여 암호문을 열고 최종 투표 결과를 얻습니다.

이렇게 가산적 준동형의 특징으로 득표수 집계 시스템을 성공적으로 구현했으며, 상사가 누군가를 보내 네트워크를 감시해도 암호화된 암호문 cti만 볼 수 있고, 각각 어떤 득표를 했는지 알 수 있는 방법이 없다. 투표한 사람 . .

물론 이 시스템은 여전히 ​​매우 불완전하며, 예를 들어 IT 부서는 상사가 모든 사람의 투표를 해독하고 문서에 기록하도록 직접 도울 수 있습니다. 이 문제를 해결하는 데 도움이 되는 다른 암호화 도구가 있습니다. 공간상의 이유로 여기서는 자세히 설명하지 않겠습니다.

하지만 여기서 우리는 동형암호 알고리즘의 위력을 느낄 수 있어야 합니다. 이렇게 이해할 수 있습니다. 동형 암호화 알고리즘을 통해 사용자는 신뢰할 수 없는 원격 서버(클라우드)와 일종의 보안 위임 컴퓨팅(Secure Delegated Computation)을 수행할 수 있습니다. 사용자는 동형암호 기술을 통해 자신의 민감한 개인 정보를 클라우드에 맡길 수 있으며, 클라우드는 암호화된 데이터에 대해 어느 정도 계산을 수행하고 최종적으로 사용자가 원하는 암호화 결과를 얻어 사용자에게 반환할 수 있습니다. 마지막으로 사용자는 복호화 키를 사용하여 얻은 결과를 열 수 있습니다. 프로토콜 전체에서 주체(클라우드)는 개인 입력과 관련된 유용한 정보를 볼 수 없습니다.

동형암호 시스템의 분류

두 가지 가장 기본적인 준동형 특성을 일반적으로 이해한 후에는 다른 개념을 이해하기가 매우 쉬워집니다. 체계적 관점에서 동형 암호 시스템은 크게 부분 준동, 근사 준동, 유한 계열 완전 준동 및 완전 준동의 네 가지 범주로 나뉩니다.

다음으로 각 범주의 구체적인 정의를 차례로 살펴보겠습니다.

부분 동형 암호화

준동암호의 초기 단계를 부분 준동암호라고 하며, 암호문은 하나의 준동형 특성만을 가진다고 정의한다. 이 단계에는 위에서 설명한 덧셈 동형 및 곱셈 동형의 두 가지 모드가 포함됩니다.

앞에서 언급한 보안 프록시 컴퓨팅 시나리오에 넣어 개인 입력이 있고 클라우드가 (x1, x2,...)를 계산하는 데 도움이 되기를 바란다면 클라우드를 사용하여 이러한 값을 계산할 수 있습니다. inputs.함수를 나타냅니다.

가산 동형 암호화 알고리즘을 통해 계산할 수 있다면 이 함수는 개인 입력(더하기 연산)의 선형 조합만 포함해야 함을 의미합니다. 작동하는 예는 개인 입력에 상수를 곱하고 함께 추가하는 것입니다.

그러나 두 개의 입력을 함께 곱하려는 경우 위에서 언급한 가산 동형 알고리즘은 무력합니다. 모든 비공개 입력의 선형 조합만 가능합니다.

일반적인 가산 동형암호 알고리즘은 순환군 기반의 ElGamal 암호화 알고리즘이다.

ElGamal은 순환 그룹의 특성을 이용한 Diffie-Hellman 키 교환 프로토콜을 기반으로 한 매우 편리한 공개 키 암호화 알고리즘입니다. 공간상의 이유로 여기서는 순환 그룹의 정의를 자세히 설명하지 않고 각 그룹이 생성기를 찾을 수 있다는 것만 알면 됩니다.

그런 다음 이 생성기를 지수화할 수 있습니다. ElGamal 암호화의 구현 방법은 대략 다음과 같습니다.

처음에 우리는

우리는 ElGamal의 정확성과 안전성을 증명하지 않을 것입니다. 하지만 이 암호화 시스템의 암호화 방법을 본 후에는 모두 전력 연산이기 때문에 ElGamal의 잠재적인 추가 동형 특성을 찾을 수 있습니다.

같은 원리가 곱셈 동형암호 알고리즘에도 적용될 수 있습니다. 우리는 모든 비공개 입력을 함께 곱할 수만 있지만 선형 조합(더하기)을 수행할 방법은 없습니다. 곱셈 동형의 예는 실제로 매우 일반적입니다.우리 모두에게 친숙한 RSA 암호화는 곱셈 동형 시스템입니다.

RSA 암호화의 구현 방법은 대략 다음과 같습니다.

우리는 이 두 메시지의 곱셈에 해당하는 암호문을 얻습니다! 이것이 곱셈의 준동형 특성입니다. 이 암호문 위에 새로운 암호문을 계속 중첩하여 암호문 간의 곱셈을 얻을 수 있습니다.

다소 동형 암호화

이전 단락에서 말했듯이 개인 입력을 곱하고 이들 간의 선형 조합을 얻으려면 간단한 부분 동형 암호화 알고리즘(RSA, ElGamal)을 완성할 수 없습니다. 그래서 우리는 다음 단계로 가야 합니다.

부분 동형 암호화의 다음 단계는 거의 동형 암호화로, 우리가 달성하고자 하는 완전 동형 암호화에 한 단계 더 가깝습니다. 대략적인 준동형 암호화 알고리즘이 있으면 암호문에 대한 덧셈과 곱셈을 동시에 계산할 수 있습니다. 다만 이 단계는 대략 준동형(Somewhat Homomorphic) 단계이기 때문에 할 수 있는 덧셈과 곱셈의 횟수가 매우 제한적이고, 계산할 수 있는 함수도 한정된 범위 내라는 점에 유의해야 한다.

근사 동형암호의 이 단계에서는 일반적인 예가 많지 않은데, 가장 잘 이해된 예를 든다면 페어링(Pairing) 순환 그룹 암호화 알고리즘을 기반으로 해야 합니다.

위에서 우리는 일반 순환 그룹을 기반으로 하는 ElGamal 암호화 알고리즘에 대해 간략하게 논의했습니다. 우리 모두는 이 알고리즘이 부가적으로 동형적이라는 것을 알고 있습니다. 즉, 암호문 간의 모든 선형 조합을 얻을 수 있습니다. 사실, 일부 특수한 순환 그룹에서 약한 승법 동형 속성을 찾을 수 있습니다.

이런 식으로 변장한 처음 두 값의 힘 사이의 제품 조합을 얻습니다! ElGamal 암호화에서 두 값의 힘이 선형적으로 결합될 수 있다는 속성과 결합하면 완전한 준동형 시스템을 얻게 됩니다.

사실 현실은 그리 아름답지 않은데, 페어링이라는 특수성이 모든 순환군에서 나타나지 않기 때문이다. 따라서 페어링으로 페어링할 수 있는 두 그룹의 값을 곱하고 새 그룹에 매핑하면 새 그룹이 해당 페어링 속성을 찾지 못할 수 있습니다!

즉, Pairing 속성이 있는 순환 그룹에서는 매우 제한된 곱셈만 수행할 수 있습니다. 우리의 현재 그룹은 페어링을 지원하지만 새로운 매핑 그룹인 GT는 어떠한 페어링도 지원하지 않는다면, 현재 시스템을 기반으로 동형암호 연산을 수행하고자 한다면, 연산 가능한 기능은 어떠한 선형 조합도 가능하지만, 최대 하나의 곱셈 레이어만 포함할 수 있습니다.

이 제한은 임의의 논리와 깊이의 함수 F를 계산할 수 없기 때문에 시스템이 대략 동형임을 증명합니다.

완전히 수평화된 동형 암호화

다음 단계에 도달한 후, 우리는 완전한 준동형의 목표에 한 걸음 더 가까워졌습니다.

이 단계를 유한 시리즈 완전 동형 암호화라고 합니다. 이 단계에서 이미 횟수에 대한 제한 없이 암호문에 대한 덧셈과 곱셈의 조합을 수행할 수 있습니다.

그러나 그것이 유한 급수 동형사상이라고 불리는 이유는 이 단계의 알고리즘이 함수 F의 복잡도를 제한하는 복잡도 상한 L이라는 새로운 개념을 도입할 것이기 때문입니다. 이진 회로 C로 표현할 수 있다면 깊이와 크기는 L의 범위 내에 있어야 합니다.

즉, L이 상대적으로 크면 더 간단한(복잡도가 낮은) 동형 연산을 다양하게 수행할 수 있습니다. 유한급수 동형암호의 알고리즘은 완전동형암호 다음 단계의 초석이기도 한데, 복잡도 내에서 완전동형을 실현할 때 완전동형암호의 실현은 머지 않았습니다.

이 복잡성의 상한선 L이 어떻게 나오는지 이해할 수 있습니다. 우선, 완전한 준동형 암호화 알고리즘이 있는 경우 암호문에 대해 더하기 및 곱하기 연산을 수행할 수 있다고 상상할 수 있습니다. 그러나 이 알고리즘은 암호화할 때 암호문에 일정량의 무작위 노이즈를 추가합니다.

노이즈가 제어 가능한 범위 내에 있으면 암호 해독 알고리즘이 암호 텍스트에서 원본 텍스트를 쉽게 복원할 수 있습니다. 그러나 준동형 계산을 위해 암호문을 함께 쌓으면 각 암호문의 노이즈가 중첩되고 확대됩니다. 암호문에 대해 비교적 간단한 논리를 수행하면 중첩된 노이즈가 여전히 허용 가능한 범위 내에 있습니다. 그러나 암호문을 너무 복잡하게 쌓으면 노이즈의 범위가 임계값을 초과하면 원본 텍스트를 완전히 덮어쓰게 되어 복호화에 실패하게 됩니다.

완전 동형 암호화(FHE)

많은 호출 끝에 마침내 우리가 기다리고 있는 완전 동형 암호화(FHE)에 도달했습니다.

이 단계에 도달하면 앞서 언급한 보안 프록시 계산이 가능해집니다. 매우 효율적인 완전 동형 암호화 시스템을 찾을 수 있다면 데이터 유출 없이 모든 로컬 컴퓨팅을 클라우드로 안전하게 프록시할 수 있습니다!

보조 제목

완전 동형 암호화 시스템의 정의

아래에서 완전 동형 시스템의 역사에 대한 논의를 시작하기 전에 완전 동형 시스템의 공식적인 정의를 체계적으로 정의할 수 있습니다. 완전 동형 암호화 시스템에는 총 4개의 알고리즘이 있습니다.

보조 제목

완전 동형 암호화 시스템의 속성

이제 이 시스템의 속성(Properties)을 살펴보겠습니다. 첫째, 시스템이 정확해야 합니다.

즉, 우리가 회로 F를 임의로 선택하고 원본 문자 메시지 세트 m1,m2,....를 임의로 선택하면 처음에 KeyGen 알고리즘에 의해 생성된 키가 있는 경우:

둘째, 시스템은 의미론적으로 안전해야 합니다. 위에서 이 정의를 이미 설명했습니다.

마지막으로 완전 준동형 암호화 시스템을 실용적으로 만들기 위해서는 압축성이라는 추가 요구 사항을 추가해야 합니다.

이 간단한 기능을 추가해야 하는 이유는 무엇입니까? 이 요구 사항이 없으면 무의미한(속임수) 완전 동형 시스템을 쉽게 만들 수 있습니다.

Eval의 출력 크기에 제한이 없다면 Eval을 여러 번 반복해서 중첩하면 얻어지는 암호문의 크기가 점점 커집니다. 마지막으로 복호화할 때 원본 암호문을 모두 복호화한 다음 계산하기만 하면 됩니다. 이것은 사용자가 자신의 건강 정보를 암호화하여 병원에 자신이 아픈지 여부를 판단하도록 요청하는 것과 같습니다. 병원은 암호문을 그대로 돌려 보낸 다음 그의 전체 데이터 모델 세트와 의학 교과서를 돌려 보내는 것과 같습니다. 당신이 수학을 직접해야 사용자.

이러한 유형의 완전 동형 시스템은 또한 더 큰 단점이 있습니다. 즉, 최종 암호문이 연산 회로 F의 특정 세부 사항을 완전히 덮을 수 없다는 것입니다. 이 병원 사용 시나리오에서 병원의 가장 귀중한 자산은 이 데이터 분석 시스템일 수 있습니다. F를 사용자에게 헛되이 되돌려 보내면 열심히 일한 결과를 다른 사람이 쉽게 훔칠 수 있습니다.

요약하면 정확성, 의미론적 보안 및 간결성의 세 가지 요소가 충족되는 한 사소하지 않은 완전 준동형 암호화 시스템을 갖게 됩니다.

보조 제목

완전 동형 암호화의 역사적 검토

완전 동형 암호화 알고리즘이 구현되는 방법을 배우기 전에 완전 동형 암호화의 개념이 어떻게 생겼는지 살펴보는 것이 좋습니다.

FHE(full homomorphism)의 개념은 실제로 1970년대 후반에 제안되었습니다. 1978년 데이터 뱅크와 프라이버시 동형에 관한 논문에서 Rivest, Adleman 및 Dertouzos는 암호문에 대해 특정 계산을 수행할 수 있고 암호문에서 간접적으로 작동할 수 있는 시스템의 개념을 처음으로 언급했습니다. 원본 텍스트. 나중에 이 아이디어는 다시 요약되어 완전 동형 암호화라고 명명되었습니다.

완전동형암호의 개념이 오래전부터 제안되었음을 알 수 있다. 놀랍게도, 논문이 출판되기 2년 전인 1976년에 Diffle-Hellman 키 교환 프로토콜이 막 제안되었습니다! 암호 필드의 상상력이 여전히 매우 풍부하다는 것을 알 수 있습니다.

FHE의 개념이 제안되었을 때 전체 학계는 그것에 감동했고 완전한 동형 속성을 가진 완벽한 알고리즘을 찾기 위해 수십 년 동안 검색을 시작했습니다. 그러나 지난 수십 년 동안 사람들은 생각할 수 있는 모든 옵션을 시도했지만 완전 동형의 모든 조건을 만족할 수 있고 보안이 쉽게 검증될 수 있는 옵션을 찾을 수 없습니다.

2009년까지 스탠포드에서 공부하던 크레이그 젠트리(Craig Gentry) 박사는 갑자기 영감을 받아 FHE 알고리즘의 어려움을 돌파했다. 박사 학위 논문에서 그는 처음으로 합리적이고 안전한 완전 준동형 암호화 시스템을 제시했습니다! 이 시스템은 이상적인 격자의 가정을 기반으로 합니다. Gentry09에서 제안한 완전 준동형 시스템은 종종 1세대 완전 준동형 암호화 시스템이라고 합니다.

Gentry의 논문에서 그는 Bootstrapping이라는 중요한 개념도 언급했습니다. 부트스트래핑은 암호문을 위한 특수 처리 기술로, 처리 후 임계값에 가까운 노이즈가 있는 암호문을 노이즈가 매우 낮은 새 암호문으로 "새로고침"할 수 있습니다. 부트스트래핑을 통해 유한 시리즈 시스템의 노이즈는 절대 임계값을 초과할 수 없으므로 완전히 동형 시스템이 됩니다. 이런 식으로 모든 크기를 동형적으로 계산할 수 있습니다.

Gentry의 주요 돌파구 이후 전체 암호계는 다시 광기에 빠졌고 모두가 Gentry의 아이디어를 기반으로 하는 보다 효율적이고 다재다능한 완전 동형 시스템을 찾기 위해 안간힘을 쓰기 시작했습니다.

2011년 두 거물인 Brakerski와 Vaikuntanathan은 격자 암호화의 또 다른 가정인 LWE(Learning With Errors)를 기반으로 하는 새로운 완전 동형 암호화 시스템을 제안했습니다. 같은 해에 Brakerski, Gentry 및 Vaikuntanathan이 함께 시스템을 완성하고 공식적으로 발표했습니다. 그들이 발명한 완전 준동형 시스템을 줄여서 BGV 시스템이라고 합니다. BGV 시스템은 계열이 한정된 동형암호 시스템이지만 부트스트래핑을 통해 완전 동형암호화할 수 있다. BGV 시스템은 Gentry09에서 제안한 시스템보다 더 현실적인 LWE 가정을 사용합니다. 일반적으로 BGV 시스템을 2세대 완전 동형 암호화 시스템이라고 합니다.

2013년 이후 암호권은 기본적으로 꽃을 피웠습니다. 원래의 3세대 완전 동형 시스템을 기반으로 BGV 및 GSW 시스템의 작동 효율성을 최적화하고 가속화하기 위해 다양한 새로운 설계가 등장했습니다. IBM은 BGV 시스템을 기반으로 오픈 소스 완전 동형 컴퓨팅 라이브러리 HElib를 개발했으며 주요 모바일 플랫폼에 성공적으로 이식되었습니다. 동시에 또 다른 오픈 소스 프로젝트인 TFHE도 매우 주목할 만합니다. TFHE는 GSW 시스템을 기반으로 다양한 최적화와 가속이 추가되어 현재 매우 유명합니다.

기존의 완전 동형 라이브러리를 개발하는 것 외에도 많은 팀이 GPU, FPGA 및 ASIC와 같은 이기종 하드웨어를 통해 완전 동형 암호화 알고리즘의 계산을 더 빠르게 가속화하는 방법을 연구하고 있습니다. 예를 들어, cuFHE는 잘 알려진 CUDA 기반 GPU 가속 완전 동형 암호화 시스템입니다.

오늘날로 보면 젠트리가 완전 동형 체계의 문을 두드린 지 11년이 지난 것 같다. 이제 업계는 FHE에 대한 연구로 가득 차 있으며 많은 사람들이 다양한 각도와 애플리케이션 요구 사항에서 완전 동형 시스템을 연구하고 있습니다. 오늘날까지 우리는 이미 다양한 FHE 구현 방법을 가지고 있지만 모두가 여전히 추구하는 것은 FHE 시스템 운영의 효율성입니다. 현재 최첨단 FHE 라이브러리를 예로 들면, 모바일 플랫폼에서 비교적 단순한 일부 논리를 동형적으로 계산하는 데 수십 밀리초 또는 수십 초가 걸릴 수 있습니다. 이러한 시간 단위는 컴퓨터 시스템에서 매우 느립니다.

이기종 플랫폼에서 FHE 시스템을 보다 효율적으로 실행하는 방법은 여전히 ​​풀리지 않는 수수께끼입니다. 이 문제가 해결되면 모든 컴퓨터 계산을 완전한 준동형으로 전환하고 에이전트가 타사 클라우드에서 계산을 수행하는 것이 가까운 미래가 될 것입니다.

보조 제목

FHE와 MPC의 관계

MPC는 사실 오랫동안 연구되어 온 매우 잘 알려진 분야입니다. 암호학자 Yao Zhizhi가 지난 세기에 Garbled Circuits를 출시한 이후로 MPC 분야는 널리 인정받았고 많은 발전이 있었습니다. 이제 사용할 수 있는 MPC 라이브러리가 많이 있으며 특정 운영 효율성도 있습니다.

MPC를 알고 있다면 완전 동형 암호화 시스템의 어려운 역사를 본 후 많은 질문이 있을 수 있습니다. 완전 동형 암호화를 MPC 프로토콜로 직접 대체할 수 없는 이유는 무엇입니까?

실제로 MPC 프로토콜은 FHE 프로토콜을 완전히 대체할 수 있습니다. 사용자와 개인 입력을 프로토콜의 당사자로 사용하고 원격 프록시 컴퓨팅 서버를 다른 당사자로 사용하면 MPC 프로토콜 실행 조건을 충족합니다.특정 상호 작용을 통해서만 프록시 컴퓨팅이 가능합니다. 그리고 서버는 개인 입력도 볼 수 없습니다.

그러나 우리가 간과하는 매우 중요한 점이 있습니다. MPC는 대화형이기 때문에 계약을 완료하기 위해 사용자와 서버가 함께 계산하고 통신해야 합니다. 이것은 또한 FHE 프록시 컴퓨팅의 가장 기본적인 요구 사항과 충돌합니다. 사용자가 계약을 완료하기 위해 항상 온라인 상태를 유지하고 컴퓨팅 성능의 일부를 지불해야 하는 경우 계산은 전혀 "대리"되지 않으며 양 당사자는 정보 보안을 위해 더 많은 계산을 수행할 뿐입니다. . 이것은 또한 MPC 분야가 주요한 돌파구를 만들었지만 FHE 분야는 아직 알려지지 않은 이유를 설명합니다. 두 시스템이 완전히 다른 문제를 해결하기 때문입니다.

보조 제목