기술 요약: 부호 이론 및 다항식에 기반한 동형 암호 체계

문제 정의

동형 암호(Homomorphic Encryption, HE)는 복호화 없이 암호화된 데이터에 대한 보안 연산을 가능하게 하며, 이는 프라이버시를 보호하는 클라우드 컴퓨팅에 필수적인 기능이다. 완전 동형 암호(Fully Homomorphic Encryption, FHE)는 임의의 연산을 허용하지만, 실제 구현 측면에서는 효율성, 노이즈 관리 및 보안 기초와 관련하여 상당한 과제에 직면해 있다.

본 논문은 HE 체계를 두 가지 주요 대수적 가족, 즉 부호 이론(coding theory) 기반 체계와 다항식(polynomials)(종종 격자 기반 구조를 통해 실현됨) 기반 체계로 분류하여 HE의 지형을 다룬다. 핵심 문제는 이 특정 영역들에 대한 최신 기술 현황을 조사하고, 그들의 구성, 보안 가정 및 실질적인 생존 가능성을 분석하는 것이다. 본 논문은 하나의 이분법을 강조한다: 많은 부호 이론적 제안들이 대수적으로는 우아하지만, 종종 비표준적인 보안 가정에 의존하거나 파괴된 반면, 다항식/환(ring) 기반 체계들은 실용적이고 안전한 HE의 표준이 되었다는 점이다.

방법론

본 논문은 문헌에 등장하는 특정 암호 체계들을 검토하고 분석하는 포괄적인 조사 방법론을 채택한다. 분석은 다음과 같은 두 가지 주요 섹션으로 구성된다:

1. 부호 이론 기반 체계: 저자들은 선형 부호의 코드워드(또는 노이즈가 섞인 코드워드)로 메시지를 인코딩하는 과정을 포함하는 암호 체계들을 조사한다. 주요 개념은 다음과 같다:

   • 평가 부호(Evaluation Codes): 유한체 상의 다항식 평가(예: Reed-Muller, Reed-Solomon)를 사용하여 부호 구조를 정의함.
   • 랭크 메트릭 부호(Rank Metric Codes): 확장체 상의 랭크 가중치(rank weight) 및 아이디얼 부호(ideal codes)를 활용함.
   • 보안 메커니즘: DSCP(Decoding Synchronized Codes Problem), IRSD(Ideal Rank Metric Decoding) 또는 코드워드 내에서 "좋은" 위치와 "나쁜" 위치를 식별하는 어려움과 같은 문제들에 의존함.

2. 다항식 기반 체계: 저자들은 밑바탕이 되는 대수적 구조가 다항식 환(종종 $Z[x]/(x^n+1)$와 같은 몫 환)에 의해 정의되는 체계들을 검토한다. 주요 개념은 다음과 같다:

   • 격자 가정(Lattice Assumptions): 대부분의 현대적 체계는 LWE 또는 Ring-LWE 문제에 의존함.
   • 노이즈 관리: 동형 연산 중 발생하는 노이즈 성장을 제어하기 위한 부트스트래핑(bootstrapping), 재선형화(relinearization), 모듈러스 스위칭(modulus switching) 등의 기술.
   • 근사 산술(Approximate Arithmetic): 실수/복소수 연산을 위해 설계된 체계(예: CKKS).

본 논문은 Armknecht et al., Challa-Gunta, Bogdanov-Lee, Aguilar-Melchor et al., Dasgupta-Pal, BFV, BGV, CKKS, GSW, FHEW/TFHE, DGHV를 포함한 특정 체계들의 알고리즘(Keygen, Encrypt, Decrypt, Eval)을 상세히 설명한다.

주요 기여 및 결과

1. 부호 이론적 체계 분석

조사 결과, 부호 이론적 체계들이 흥미로운 대수적 구조를 제공함에도 불구하고, 심각한 보안 및 실무적 장애물에 직면해 있음이 드러났다:

• Armknecht et al.: 평가 부호 및 Reed-Muller 코드를 기반으로 하는 다소 동형(somewhat homomorphic) 체계이다. 보안은 DSCP에 의존하며, 대칭키 방식이고 제한된 횟수의 곱셈을 지원한다.
• Challa-Gunta: Reed-Muller 코드를 기반으로 FHE를 주장하는 두 가지 대칭키 체계(벡터 및 행렬 버전)이다. 본 논문은 이들이 비표준적인 보안 주장(코드워드 위치를 숨기는 것)에 의존하며 실제 배포가 부족하다고 언급한다.
• Bogdanov-Lee: 수정된 Reed-Solomon 코드를 기반으로 하는 비대칭 다소 동형 체계이다. 결과: 본 논문은 이 체계가 **파괴되었음(broken)**을 명시적으로 밝힌다. "Square code" 차원을 이용한 구별자 기반 공격(distinguisher-based attack)을 통해 공격자가 다항 시간 내에 비밀 좌표 세트를 복구하고 모든 암호문을 복호화할 수 있다.
• Aguilar-Melchor et al.: 무작위 랭크 메트릭 아이디얼 부호에 기반한 대칭키 체계이다. 하나의 암호문 곱셈을 지원한다. 결과: 제안된 부트스트래핑 메커니즘은 부트스트래핑 키의 수가 기저의 IRSD 문제를 해결하기 위한 임계값을 초과하기 때문에 안전하지 않은 것으로 간주된다.

2. 다항식 기반 체계 분석

본 조사는 다항식/환 기반 체계를 안전하고 실용적인 HE의 현재 표준으로 식별한다:

• Dasgupta-Pal & DGHV: 정수 산술 및 AGCD(Approximate GCD) 문제에 기반한 초기 체계들이다. 이들은 다소 동형이지만, 부트스트래핑을 통해 완전 동형으로 만들 수 있다.
• BFV, BGV, CKKS, GSW: LWE/RLWE에 기반한 비대칭 레벨드 완전 동형(leveled fully homomorphic) 체계들이다.
  • BFV/BGV: 유한 환 상의 정확한 산술을 지원한다. 곱셈 중 암호문의 차수 성장을 처리하기 위해 재선형화를 활용한다.
  • CKKS: 근사 산술을 지원하여 실수/복소수 데이터 애플리케이션에 적합하다.
  • GSW: 행렬 기반 암호문과 "Flatten" 연산자를 사용하는 기초적인 체계이다.
• FHEW/TFHE: 불리언 회로의 빠른 부트스트래핑을 위해 설계된 완전 동형 체계이다. 토러스(torus) 상에서 작동하며, 게이트 부트스트래핑을 사용하여 노이즈를 갱신함으로써 무제한적인 회로 깊이를 허용한다.

3. 비교 종합

본 논문은 주요한 차이를 강조하는 비교 개요(Table 1)를 제공한다:

• 부호 이론적 체계: 개념적으로는 중요하지만, 자주 비표준적인 보안 가정, 현대적 검증의 결여, 또는 특정 취약점(예: Bogdanov-Lee)을 겪는다. 이들은 주로 이론적이거나 개념적인 상태로 남아 있다.
• 다항식/환 기반 체계: 포스트 양자 암호의 핵심인 잘 확립된 난해성 가정(LWE, RLWE) 위에 구축되었다. 이러한 체계들은 실질적인 구현, 소프트웨어 라이브러리로 이어졌으며, 정확한 산술 및 근사 산술 모두에 널리 사용되고 있다.

의의 및 주장

본 논문은 "부호 이론"과 "다항식" 접근 방식이 서로 분리된 객체로서의 엄격한 구분이 아니라고 주장한다. 대신, 이들은 공통된 스펙트럼의 대수적 동형 암호를 나타낸다:

• 대수적 핵심: 두 가족 모두 정보를 구조화된 대수적 객체(코드워드 또는 다항식)로 인코딩하며, 이 구조와 덧셈 및 곱셈 사이의 호환성을 활용한다.
• 패러다임의 차이: 대비되는 점은 정당성(correctness)과 보안의 공식화에 있다. 부호 이론적 체계는 문제를 디코딩(숨겨진 에러로부터의 보간) 관점에서 구성하는 반면, 다항식 체계는 이를 구조화된 환 위의 노이즈가 섞인 산술(noisy arithmetic) 관점에서 구성한다.
• 현재 상태: 본 논문은 격자 기반(다항식) 체계가 견고한 보안 기초와 효율성 덕분에 이론과 실무 모두에서 현재 지배적이지만, 부호 이론적 접근 방식 또한 중요한 연구 방향으로 남아 있다고 결론짓는다. 이들은 대안적인 설계 패러다임을 제공하며 디코딩 문제에 관한 독립적인 수학적 질문을 제기한다.

본 논문은 LWE와 같은 표준 가정을 가진 부호 기반 체계, 격자 설정 외부에서의 안전하고 효율적인 부트스트래핑, 그리고 비표준 제안들에 대한 체계적인 보안 분석의 필요성을 포함한 여러 공개된 문제들을 식별한다. 논문은 매력적인 대수적 구조의 존재 자체만으로는 불충분하며, 설득력 있는 HE 체계를 위해서는 강력한 난해성 가정과 정밀한 노이즈 제어가 필수적임을 강조한다.