기술나눔

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

학습 자료:
완전동형암호Ⅰ: 이론과 기초(상하이 교통대학교 Yu Yu 선생님)
완전동형암호II: 완전동형암호의 이론과 구성 (Xiang Xie 선생님)

---

오늘날 2세대(BGV 및 BFV)와 3세대 완전 동형 암호화 방식은 모두 LWE를 기반으로 합니다. 이제 고급 완전 동형 암호화 방식도 LWE를 기반으로 하므로 이 기사에서는 LWE에 대한 기본 지식을 요약합니다.
먼저 숫자를 암호화하고 싶습니다.$에스$, 이제 일련의${ㅏ}_{나}$오른쪽$에스$암호화하여 가져오기${ㅏ}_{나}에스$, 실제로 최대 공약수 GCD를 해결하면 문제가 해결될 수 있습니다.$에스$ .그러나 임의의 노이즈가 추가되면${이자형}_{나}$,얻다${ㅏ}_{나}에스+{이자형}_{나}$, 그러면 해결하기 어려울 것입니다$에스$ 값. 이 과정은 LWE에 대한 나의 간단한 이해입니다. 소위 오류는 소음입니다.

완전 동형암호의 계산 과정은 키 생성 KeyGen, 암호화 Enc, 동형 계산 Eval, 복호화 Dec의 세 단계로 나누어집니다. ,

키젠：

먼저 위의 방정식을 구성하고,$에스\cdot ㅏ+이자형=에스ㅏ+이자형$, 공개 키 pk($-ㅏ$그리고$에스ㅏ+이자형$스플라이싱) 및 개인 키 sk($에스$ 그리고 접합 1개). 따라서 pk와 sk를 곱한 결과는 랜덤 노이즈 e(0에 가까운)임을 알 수 있습니다.

엔씨：

암호화에 사용되는 공개키 pk, r은 0 또는 1만 포함하는 임의의 벡터이고, m은 암호화할 정보(벡터의 최하위 비트에 넣음)입니다.

12월：

복호화에 사용된 개인키 sk와 ct의 내적을 계산한 후 mod 2를 찾아 복호화 결과를 얻는다.

정확성 증명:

sk와 pk를 곱하여 2e(KeyGen이 충족하는 조건)를 얻은 다음 r과 내적을 수행하여 작은 균등 잡음을 얻습니다. 최종 결과는 m+ 작은 균등 잡음이므로 mod 2를 통해 잡음을 제거할 수 있습니다. 복호화 결과를 얻습니다. m. 이것이 구성된 노이즈가 e가 아닌 2e인 이유입니다. 짝수 랜덤 노이즈를 구성하면 암호 해독 중에 노이즈를 제거하기 위해 mod 2를 사용하는 것이 편리하다는 것입니다.

안전 증거:

pk가 의사 난수이고 r이 충분히 높은 엔트로피를 갖는 경우(즉, 무작위성이 강한가?) pk와 pk 곱하기 r은 모두 의사 난수입니다. m으로 자연과 벡터를 추가하면 암호화 결과도 의사 난수(pseudo-random)가 됩니다.

다음은 Xiang Xie 선생님의 공식적인 설명입니다.
암호화 공식: 암호문 c = 공개키 pk ✖️ 랜덤 r + 평문 m
복호화 공식: 일반 텍스트 m = <암호문 sk, 개인 키 sk> mod q mod 2

이를 바탕으로 mod 2를 사용하여 일반 텍스트 m의 값을 해독할 수 있습니다. 소음이 충분히 작으면 정확도가 보장됩니다.
여기서 구별해야 할 것이 있습니다.$피케이=(ㅏ,비=ㅏ{에스}^{\prime }+2이자형)$는 BGV 솔루션이고 BFV는$피케이=(ㅏ,비=ㅏ{에스}^{\prime }+이자형)$, 차이점은 BGV는 정보를 낮은 비트로 인코딩하는 반면 BFV는 메시지를 높은 비트로 인코딩한다는 것입니다(BFV를 학습할 때 설명하겠습니다).

Eval(덧셈 동형 및 곱셈 동형):

동형 덧셈 또는 곱셈은 상당한 노이즈 축적을 가져오고 곱셈은 2차 증가 추세를 나타냅니다.
그런 다음 동형 곱셈의 결과를 해독하는 방법에 대해 이야기해 보겠습니다. 다음 공식을 볼 수 있습니다. 두 암호문의 곱셈은 암호문과 개인 키의 텐서 곱을 수행한 다음 내부 곱을 수행하는 것과 같습니다. 따라서 암호문과 개인 키 모두 크기가 두 배로 커졌습니다. 예는 동등성을 증명하는 것입니다.

그렇다면 문제는 동형곱셈 후 암호문 크기와 개인 키 크기를 어떻게 복원할 것인가 하는 것입니다. 이것이 바로 키 전환이 해결하는 문제입니다.

다음은 Xiang Xie 선생님의 설명입니다.

키 전환

암호문과 개인키의 크기를 선형 크기로 복원하는 것이 목표입니다.

이제 암호문 c1과 c2의 곱셈을 구합니다.

위의 프로세스는 비트 분해의 개념을 기반으로 합니다.

다음은 Xiang Xie 선생님의 설명입니다.

키 스위칭의 목표: 개인 키 변환$\widetilde{에스}$아래에$\widetilde{씨}$ 개인 키로 변환$에스$아래에$씨$,그리고$\widetilde{씨}$그리고$씨$모두 동일한 일반 텍스트로 암호화됩니다.
여기서 핵심 개념은 개인 키를 사용한다는 의미인 KSK(Key Switching Key)입니다.$에스$암호화하다$\widetilde{에스}$。

키 전환 프로세스를 통해 개인 키는 다음에서 파생될 수 있습니다.$에스\otimes 에스$선형이 되었다$에스$, 암호문은 다음과 같이 변경됩니다.$\widetilde{씨}$선형이 되었다$씨$ .그리고 공식의 마지막 줄에서 Key Switching 후의 내용을 볼 수 있습니다.$⟨씨,에스⟩$그리고 원본$⟨\widetilde{씨},에스\otimes 에스⟩$소음차이가 있습니다$2{\widetilde{씨}}^{티}\widetilde{이자형}$ , 이 부분은 매우 클 수 있습니다! 따라서 여기서는 아직 키 전환을 구현할 방법이 없습니다.

여기에 가젯 매트릭스 G가 도입되었습니다.

따라서 Key Switching 과정은 다음과 같습니다.

이 시점에서 추가되는 오류는 매우 작습니다.
정리하자면 Key Switching을 통해 원래의 개인키는$\widetilde{에스}=에스\otimes 에스$아래에$\widetilde{씨}=씨\otimes 씨$, 개인 키로 변환됩니다.$에스$아래에$씨$, 키 전환 후 키에 주의하세요$에스,씨$원래 값이 아닙니다(다시 확인).

BGV의 경우 덧셈의 노이즈는 선형적으로 증가하고 곱셈의 노이즈는 정사각형으로 증가합니다. 키 전환은 곱셈을 지원하지만(sk가 극도로 커지도록 제한) 실제로는 원래의 곱셈 노이즈에 추가되는 노이즈가 매우 작습니다. 또한 매우 큽니다. 따라서 이 소음을 더욱 줄여야 합니다.

모듈러스 감소

이때 LWE를 통해 작은 깊이의 동형 곱셈과 덧셈 계산을 구현했는데, Key Switching은 각 레이어마다 새로운 키를 사용하지만, 계산 깊이가 깊어질수록 노이즈의 확장이 폭발적이어서 아직 평준화되지 않았습니다. . FHE(지정된 깊이에서 FHE를 계산할 수 있음).
이제 우리는 모듈로 변환이 필요한 부트스트래핑을 사용하지 않고 특정 깊이를 계산할 수 있는 FHE를 구현하려고 합니다.

간단히 말해서 암호문 c를 도메인 모듈로 q에서 도메인 모듈로 p로 변환하는 것입니다(p<
구체적인 예는 다음과 같습니다.
Modulus Reduction을 수행하지 않으면 깊이가 깊어짐에 따라 노이즈가 2배 지수 추세로 증가하고 레벨 >= 3 이후에는 암호 해독 오류가 발생합니다.

각 레벨에서 모듈러스 감소를 수행하면 모듈러스가 지속적으로 감소하는 대신 노이즈도 절대값 범위 내에서 유지됩니다.

따라서 레벨화된 FHE를 구현하려면 모듈러스를 설정할 수 있습니다.${비}^{디}$, 그러면 깊이를 계산할 수 있습니다$디$회로(여기서$비$ 새로 고쳐진 암호문의 노이즈 상한입니다.계획된$디$깊이 후에 모듈러스는 다음과 같이 감소되어야 합니다.$비$ , 현재 암호 해독에 오류가 없는지 확인합니다. BGV는 레벨화된 FHE입니다.