Bridges connecting Encryption Schemes

1. 연구 배경 및 문제 정의 (Problem)

• 배경:
  • 프록시 리-암호화 (Proxy Re-Encryption, PRE): 동일한 암호화 체계 내에서 하나의 비밀키로 암호화된 문서를 다른 비밀키로 변환하는 기술은 잘 알려져 있습니다.
  • 유니버설 프록시 리-암호화 (Universal PRE): 서로 다른 두 암호화 체계 간에 암호문을 변환하는 일반적인 방법은 제안되었으나, 이를 구현하기 위해 **구분 불가능성 은폐 (Indistinguishability Obfuscation)**와 같은 달성하기 어려운 프로토콜이 필요하여 실용성이 낮습니다.
  • 하이브리드 동형 암호 (Hybrid Homomorphic Encryption): 데이터 소유자가 대칭키 암호로 데이터를 암호화하고, 이를 호모모픽 암호 (FHE) 로 변환하여 서버에서 연산을 수행하는 방식이 주목받고 있습니다. 이 과정에서 두 체계 간의 안전한 변환 메커니즘이 필요합니다.
• 문제: 서로 다른 두 암호화 체계 간의 변환 프로토콜을 공식적으로 정의하고, 이러한 변환이 **보안성 (IND-CPA)**을 유지하는지 분석하는 이론적 기반이 부족했습니다.

2. 방법론 및 핵심 개념 (Methodology & Key Concepts)

2.1 브리지 (Bridge) 의 정의

저자들은 두 암호화 체계 $S_1$과 $S_2$를 연결하는 브리지를 다음과 같이 정의합니다:

1. 평문 공간 매핑: $S_1$의 평문 공간 $P_1$에서 $S_2$의 평문 공간 $P_2$로 가는 단사 함수 $\iota$ (다항 시간 계산 가능 및 역함수 존재).
2. 브리지 키 생성: $S_1$의 비밀키 $sk_1$을 사용하여 $S_2$의 비밀키 $sk_2$를 생성하고, 이를 기반으로 **브리지 키 (Bridge Key, $bk$)**를 생성하는 알고리즘.
3. 변환 알고리즘 ($f$): $bk$와$S_1$의 암호문$c_1$을 입력받아$S_2$의 암호문$c_2$를 출력하는 다항 시간 알고리즘.
   • 정확성 조건: $Dec_2(sk_2, f(bk, Enc_1(pk_1, m))) = \iota(m)$이어야 함.

2.2 보안성 분석 프레임워크

• 연관 암호화 체계 (Associated Encryption Scheme): 브리지 $B$의 보안성을 정의하기 위해, 브리지에 고유하게 대응되는 새로운 암호화 체계 $G_f$를 구성합니다.
  • $G_f$의 평문은 $S_1$의 평문과 동일하고, 암호문은 $(c_1, f(bk, c_1'))$ 형태의 쌍입니다.
  • $G_f$의 보안성이 곧 브리지의 보안성으로 정의됩니다.
• 주요 정리 (Theorem 2): 브리지의 IND-CPA 보안성은 다음 두 조건이 충족될 때 보장됩니다.
  1. 첫 번째 암호화 체계 $S_1$이 IND-CPA 보안성을 가질 것.
  2. 기술적 가정: 브리지 키 생성 과정에서 생성되는 공개키/브리지키 분포가, 특정 조건 (예: $S_1$의 비밀키에 대한 암호문이 아닌 무작위 값) 하에서도 계산적으로 구별 불가능 (Computationally Indistinguishable) 할 것.

2.3 젠트리 (Gentry) 의 레시피를 활용한 구성

• 젠트리 타입 브리지: 젠트리가 FHE 를 만들기 위해 사용한 Re-encrypt (부트스트래핑) 절차를 일반화하여 브리지를 구성하는 방법을 제시했습니다.
  • $S_1$의 복호화 회로를 $S_2$ (호모모픽 암호) 내부에서 호모모픽하게 평가하여 $S_1$의 암호문을 $S_2$의 암호문으로 변환합니다.
  • 이 경우, 브리지 키는 $S_1$의 비밀키 비트들을 $S_2$로 암호화한 값들의 벡터가 됩니다.
• 보안성 증명: $S_1$과 $S_2$가 각각 IND-CPA 보안성을 가진다면, 젠트리 타입 브리지도 IND-CPA 보안성을 가짐을 증명했습니다 (Proposition 2 및 Theorem 3).

3. 주요 기여 (Key Contributions)

1. 브리지의 형식적 정의: 서로 다른 암호화 체계 간의 변환을 '사상 (Morphism)'으로 간주하고, 이를 수학적으로 엄밀하게 정의했습니다. 이는 범주론적 관점에서 암호화 체계를 바라보는 새로운 시각을 제공합니다.
2. 일반적인 보안성 정리: 브리지의 보안성이 첫 번째 체계의 보안성과 추가적인 기술적 조건 (브리지 키 분포의 구별 불가능성) 으로 환원됨을 증명했습니다. 이는 기존 프록시 리-암호화 분석보다 더 정교한 분석을 제공합니다.
3. 구현 가능한 구성법 제시:
   • 젠트리 레시피: 호모모픽 암호를 이용한 복호화 회로 평가를 통한 브리지 구성.
   • 대안적 예시: 젠트리 레시피에 해당하지 않는 브리지 (예: GM 암호에서 SYY 암호로의 변환) 를 제시하며, 브리지 키가 비어있는 (Empty Bridge Key) 경우에도 보안성이 성립함을 보였습니다.
4. 구체적인 예시 (Appendix A & B):
   • CSGN 암호화 체계에서 다양한 FHE 체계 (BGV, BFV, TFHE) 로 연결되는 4 가지 다른 브리지 예시를 제시했습니다.
   • Goldwasser-Micali (GM) 에서 Sander-Young-Yung (SYY) 로 가는 브리지를 구성하고, 이를 이용한 호모모픽 비교 회로 (Comparison Circuit) 연산을 시연했습니다.

4. 실험 결과 (Results)

저자들은 제안된 브리지들의 성능을 실험적으로 검증했습니다.

• 실험 환경: BGV, BFV, TFHE 라이브러리 (HElib, SEAL, TFHE) 를 사용하여 CSGN 암호에서 FHE 로 변환하는 브리지 성능을 측정.
• 성능 비교:
  • 단항식 (Monomial) 평가: CSGN 에서 곱셈 연산이 저렴하므로, 곱셈을 CSGN 에서 먼저 수행한 후 FHE 로 변환하는 방식이, 모든 연산을 FHE 에서 수행하는 것보다 더 빠를 수 있음을 발견했습니다.
  • 임계값 (Threshold): 단항식의 차수가 특정 임계값을 넘을 때 브리지 방식을 사용하는 것이 효율적입니다.
  • TFHE 의 특성: TFHE 는 자동 부트스트래핑을 수행하므로 곱셈 횟수가 증가함에 따라 실행 시간이 지수적으로 증가하는 경향을 보였습니다.
• GM-SYY 브리지: 비교 회로 (Comparison Circuit) 를 GM 암호문에서 SYY 암호문으로 변환하여 평가하는 실험에서, 변환 및 평가 시간이 입력 비트 수에 대해 선형적으로 증가함을 확인했습니다.

5. 의의 및 결론 (Significance & Conclusion)

• 이론적 의의: 암호화 체계 간의 변환을 '브리지'라는 개념으로 체계화하고, 이를 범주론적 사상과 연결함으로써 암호학의 이론적 토대를 확장했습니다.
• 실용적 의의:
  • 하이브리드 동형 암호 최적화: 대칭키 암호와 FHE 를 결합한 하이브리드 시스템에서, 데이터 소유자가 암호화된 데이터를 서버에 전송할 때, 효율적인 연산을 위해 암호화 체계를 전환하는 안전한 메커니즘을 제공합니다.
  • 보안성 보장: 복잡한 변환 프로토콜이 기존 암호 체계의 보안성을 훼손하지 않음을 수학적으로 증명하여, 실제 클라우드 컴퓨팅 환경에서의 적용 가능성을 높였습니다.
• 향후 연구: 브리지 키가 비어있는 경우 (Entangled schemes) 와 같은 새로운 형태의 브리지를 탐구하며, 다양한 암호화 체계 간의 연결성을 연구하는 기초를 마련했습니다.

요약하자면, 이 논문은 서로 다른 암호화 체계 간의 안전한 변환을 위한 **이론적 프레임워크 (브리지)**를 제시하고, 젠트리 레시피를 일반화하여 구체적인 구성법을 제공하며, 실제 구현을 통한 성능 검증을 통해 클라우드 보안 및 동형 암호 응용 분야에 중요한 기여를 했습니다.