Succinct Oblivious Tensor Evaluation and Applications: Adaptively-Secure Laconic Function Evaluation and Trapdoor Hashing for All Circuits

1. 문제 정의 (Problem Definition)

이 논문은 비관적 텐서 평가 (Oblivious Tensor Evaluation, OTE) 의 새로운 개념을 제안하며, 특히 간결성 (Succinctness) 과 적응적 보안 (Adaptive Security) 을 동시에 달성하는 것이 핵심 목표입니다.

• 기본 시나리오: 앨리스 (Alice) 는 긴 벡터 $x$를, 밥 (Bob) 은 짧은 비밀 벡터 $y$를 보유하고 있습니다. 두 당사자는 한 번의 동시 메시지 교환을 통해 $x \otimes y$ (텐서 곱) 의 가법적 비밀 공유 (additive secret sharing) 를 로컬로 계산해야 합니다. 이때 밥의 입력 $y$는 앨리스에게, 앨리스의 입력 $x$는 밥에게 노출되어서는 안 됩니다.
• 기존 한계:
  • 통신 복잡도: 기존 프로토콜들은 입력 $x$의 차원에 비례하여 통신량이 증가하거나, 상호작용이 여러 번 필요했습니다.
  • 보안 모델: 많은 기존 방식이 '선택적 보안 (Selective Security)'만 제공하거나, '적응적 LWE (Adaptive LWE)'와 같은 강력하고 아직 증명되지 않은 가정에 의존했습니다.
  • 응용의 제한: 기존에 구축된 트랩도어 해시 (TDH) 나 간결한 동형 비밀 공유 (HSS) 는 선형 함수나 제한된 회로 (NC1) 만 지원했습니다.

2. 방법론 (Methodology)

저자들은 학습 오류 (Learning With Errors, LWE) 가 가정하에 최적의 복잡도를 가진 새로운 OTE 프로토콜을 구축하고, 이를 기반으로 여러 암호학적 원시 (Primitives) 를 설계했습니다.

A. 간결한 비관적 텐서 평가 (Succinct NI-OTE)

1. 반-간결 (Half-Succinct) OTE 구축:
   • 먼저 한 당사자 (해시러) 의 메시지만 입력 크기에 무관하게 짧고, 다른 당사자 (인코더) 의 메시지는 입력에 의존하는 프로토콜을 LWE 기반 SIS (Short Integer Solution) 문제와 LWE 샘플을 사용하여 구축합니다.
   • 인코딩은 $C = A^T S + E + I_m \otimes y^T$ 형태를 가지며, 해시는 $d = A \cdot x$입니다.
2. 풀-간결 (Fully-Succinct) 부스팅 (Bootstrapping):
   • 반-간결 프로토콜의 단점 (인코더 메시지가 길어짐) 을 해결하기 위해 재귀적 압축 전략을 사용합니다.
   • 입력 $x$를 블록으로 나누어 해시한 후, 이 해시 값들 자체를 다시 OTE 프로토콜에 입력하여 재귀적으로 압축합니다.
   • 핵심 기술: 재귀 과정에서 밥의 메시지가 급격히 커지는 것을 방지하기 위해, 무작위 행렬 $S$를 LWE를 통해 의사난수 (Pseudorandom) 로 생성하고, 행렬 $A, B$를 이진수 (Binary) 로 샘플링하여 노이즈가 커지지 않도록 설계했습니다.
   • 결과적으로 통신량은 $x$의 차원에 대해 로그 (Logarithmic) 수준으로 줄어듭니다.

B. 적응적 격자 인코딩 (Adaptive Lattice Encodings)

• 기존 BGG+ 인코딩은 적응적 공격에 취약했습니다. 저자들은 새로운 인코딩 방식을 제안합니다:
  • 인코딩: $c^T = s^T A + r^T (x^T \otimes G) + e^T$
  • 여기서 $s$는 암호화 키, $r$은 인증 키로 분리됩니다.
  • 이 방식은 표준 LWE 가정 하에 적응적 보안을 보장하며, 선형 연산과 특정 조건 하의 곱셈 연산을 지원합니다.
• 압축 기술: 이 적응적 인코딩을 OTE 프로토콜과 결합하여 입력 크기에 대해 로그 크기로 압축된 인코딩을 생성하고, 필요 시 다시 확장할 수 있는 방법을 제시했습니다.

C. 역 트랩도어 해싱 (Reverse Trapdoor Hashing, Reverse TDH)

• 기존 TDH 는 입력 $x$를 해시하고 함수 $f$에 대한 키를 생성하는 방식이었습니다.
• Reverse TDH는 반대로 함수 $f$를 해시하고 입력 $x$에 대한 인코딩 키를 생성합니다.
• 이 구조를 통해 모든 함수 (RAM 프로그램 포함) 에 대해 간결한 해시와 인코딩을 가능하게 합니다.

3. 주요 기여 및 결과 (Key Contributions & Results)

이 논문은 표준 LWE 가정 하에 다음과 같은 획기적인 결과를 도출했습니다.

1. 최적의 간결 OTE (Succinct NI-OTE):

   • 입력 $x$의 차원에 무관한 로그 크기의 메시지로 텐서 곱을 계산하는 프로토콜을 최초로 제안했습니다.
   • 보안은 표준 LWE에 기반하며, CRS(공통 참조 문자열) 크기도 입력 크기와 무관합니다.

2. 모든 함수에 대한 간결한 HSS 및 Batch Laconic OT:

   • 간결한 동형 비밀 공유 (Succinct HSS): 모든 함수에 대해 적용 가능하며, 통신 복잡도가 입력 $x$의 크기에 대해 로그 수준 ($|x|^\epsilon$이 아님) 으로 최적화되었습니다.
   • 배치 Laconic OT: 수신자의 메시지가 상수 크기이고 전송률이 1/2 인 최적의 배치 옵시비어스 전송 프로토콜을 제공합니다.

3. 적응적 보안 및 Rate-1 Laconic Function Evaluation (LFE):

   • 적응적 보안: 공격자가 공개 파라미터를 본 후 입력을 선택할 수 있는 상황에서도 안전한 최초의 LFE 프로토콜입니다.
   • Rate-1: 인코딩 크기가 입력 크기 + 출력 크기 + 다항식 오차 항 ($m + \ell + D \cdot poly(\lambda)$) 으로, 이론적으로 가능한 최적의 효율성을 가집니다.
   • 기존 작업 개선: Quach, Wee, Wichs (FOCS 2018) 의 작업은 적응적 LWE 가정에 의존했으나, 본 논문은 표준 LWE로 개선했습니다. 또한 Wee (2024) 의 $\ell$-간결 LWE 가정을 표준 LWE로 대체했습니다.

4. 모든 함수에 대한 트랩도어 해시 (TDH):

   • 선형 함수를 넘어 모든 함수 (및 RAM 프로그램) 에 대해 간결한 TDH 를 구축했습니다. 인코딩 키의 크기는 함수 설명 크기에 비례하며 입력 크기와 무관합니다.

4. 의의 및 중요성 (Significance)

• 이론적 돌파구: "적응적 LWE"와 같은 미해결이거나 약한 가정을 제거하고 표준 LWE만으로 강력한 암호학적 원시들을 구축했다는 점에서 이론적 중요성이 큽니다.
• 실용적 효율성: 통신 복잡도가 입력 크기에 대해 로그 수준으로 줄어듦으로써, 대용량 데이터 처리나 분산 시스템에서의 프라이버시 보호 기술의 실용성을 크게 높였습니다.
• 새로운 기술적 도구: 제안된 적응적 격자 인코딩과 간결 OTE는 향후 다른 암호학적 구성 요소 (FHE, PCG 등) 를 설계하는 데 핵심적인 도구로 활용될 수 있습니다.
• 동시 연구와의 차별성: 동시 연구인 Boyle et al. [BJSS25] 와 유사한 결과를 도출했으나, 본 논문은 더 최적화된 파라미터 (인코딩 키 크기 $|f| \cdot poly(\lambda, \log m)$) 를 제공하며, 표준 LWE 기반의 Rate-1 FHE 구축 가능성도 시사합니다.

결론

이 논문은 간결한 OTE라는 새로운 원시를 도입하여, 표준 LWE 가정 하에 적응적 보안과 최적의 통신 효율성을 동시에 만족하는 다양한 암호학적 프로토콜 (LFE, TDH, HSS, OT) 을 가능하게 했습니다. 이는 격자 기반 암호학의 이론적 한계를 넓히고, 향후 효율적인 프라이버시 보호 기술의 토대를 마련했다는 점에서 매우 중요한 업적입니다.