정수 연산을 위한 BGV 및 BFV 방식

BGV(Brakerski-Gentry-Vaikuntanathan, 2012)는 RLWE에 기반한 레벨형 FHE 체계입니다. 패킹된 정수 평문에 대해 임의의 덧셈과 곱셈을 지원합니다. ‘레벨형’이라는 말은 부트스트래핑 없이 고정된 깊이 L까지의 회로를 처리한다는 뜻입니다.

BGV와 BFV는 평문을 Z_t[x]/(x^n+1)의 다항식으로 인코딩합니다. 여기서 t는 작은 평문 법입니다(예: t=65537). 각 다항식은 n개의 정수 값(계수당 하나)을 인코딩합니다. 암호문에 대한 산술 연산은 n개의 모든 값에 동시에 수행되며, 이를 SIMD 병렬성이라고 합니다.

BGV는 법 전환을 사용하여 잡음을 줄입니다. 각 곱셈 후 암호문 법 q를 Q_L에서 Q_{L-1}로 줄입니다. 그러면 잡음이 Q_L/Q_{L-1}만큼 나뉘어 복호화 가능한 범위 안에 유지됩니다. 회로 깊이 L은 L개의 법 레벨에 해당합니다.

BFV(Brakerski/Fan-Vercauteren, 2012)는 BGV와 비슷하지만 잡음 관리 전략이 다릅니다. 즉, 크기 불변 방식을 사용합니다. BFV는 법 전환이 필요하지 않고, 대신 곱셈 후 암호문의 크기를 다시 조정합니다. 구현이 더 단순하며 Microsoft SEAL에서 사용됩니다.

평문 환에 중국인의 나머지 정리를 적용하면 각 암호문에 서로 독립적인 n/2개의 정수 값(슬롯)을 저장할 수 있습니다. 암호문 덧셈 연산 하나는 n/2개의 모든 쌍을 병렬로 더합니다. 곱셈은 모든 쌍을 곱합니다. 처리량은 암호문 연산 하나당 n/2개의 정수 연산입니다.

1차 암호문 두 개를 곱하면 결과는 2차 암호문(구성 요소 3개)이 됩니다. 재선형화는 평가 키(재선형화 키)를 사용하여 잡음이 추가되는 대가로 다시 1차 암호문으로 변환합니다. 이 단계는 곱셈을 수행할 때마다 필요합니다.

from seal import EncryptionParameters, scheme_type, SEALContext, KeyGenerator, Encryptor, Evaluator, Decryptor parms = EncryptionParameters(scheme_type.bfv) parms.set_poly_modulus_degree(4096) parms.set_coeff_modulus(CoeffModulus.BFVDefault(4096)) parms.set_plain_modulus(PlainModulus.Batching(4096, 20))

암호문 회전은 n/2개의 평문 슬롯을 순환 방식으로 이동합니다. 다음 작업에 유용합니다. 합계 축소(모든 슬롯을 하나로 누적), 행렬-벡터 곱셈(회전 후 누적), 합성곱(이동 후 곱셈)입니다. 갈루아 키(미리 계산된 회전 키)가 필요합니다.

n=8192인 BFV에서 덧셈은 약 10 µs, 곱셈은 약 5 ms입니다(재선형화 포함). 필요한 경우 부트스트래핑에는 30-60초가 걸립니다. 정수 4096개를 배치로 처리하면 곱셈 1회당 정수 하나의 상각 비용은 약 1 µs입니다. 실시간 처리에는 비현실적이지만 오프라인 분석에는 사용할 수 있습니다.

n과 q를 선택할 때 SEAL은 Q < 2^109인 128비트 보안에 n=4096을, 더 큰 회로에는 n=8192를 권장합니다. HE 표준(homomorphicencryption.org)은 매개변수 표를 제공합니다. 항상 권장 매개변수를 사용하십시오. 직접 선택한 값은 보안을 쉽게 약화할 수 있습니다.

암호화된 데이터베이스 질의(복호화하지 않고 암호화된 레코드를 검색합니다). 비공개 유전체 분석(암호화된 DNA에 대해 통계량을 계산합니다). 암호화된 금융 집계(개별 고객을 보지 않고 암호화된 계좌 잔액을 합산합니다). 안전한 모델 평가입니다.

BGV와 BFV는 RLWE를 사용하여 암호화된 정수 산술을 수행합니다. 배치 인코딩은 SIMD 병렬성을 제공합니다. BGV는 법 전환을 사용하고, BFV는 크기 불변 방식을 사용합니다. 재선형화는 곱셈 후 차수를 복원합니다. 다음 주제: 근사 산술과 머신러닝을 위한 CKKS입니다.