Simultaneous Approximation for Lattice-Based Cryptography

논문 개요

이 논문은 격자 기반 암호학 (Lattice-based Cryptography) 의 보안성과 효율성을 동시에 개선하기 위해 새로운 문제 클래스와 축소 (Reduction) 기법을 제안합니다. 저자 Julia VanLandingham 은 동시 근사 (Simultaneous Approximation, SA) 격자라는 특수한 격자 구조에서 정의된 두 가지 새로운 문제인 SIAP와 CAP를 도입하고, 기존의 표준 격자 문제 (SVP, SIVP, CVP) 를 이 SA 격자 문제들로 변환하는 결정론적 다항 시간 축소 알고리즘을 제시합니다.

1. 연구 배경 및 문제 제기

• 배경: 격자 기반 암호는 양자 컴퓨터 공격에 대한 저항성과 평균 - 최악 사례 (Average-to-worst-case) 축소 가능성으로 인해 각광받고 있습니다. 그러나 일반적인 격자 시스템은 큰 공개키 크기를 요구하는 단점이 있습니다.
• 기존 접근법의 한계:
  • 이상 격자 (Ideal Lattices): 키 크기를 줄일 수 있지만, 일반적인 격자 문제만큼의 보안 강도 (Hardness) 를 보장하지 못하며, 특정 이상 격자에 대한 공격 알고리즘이 존재합니다.
  • 동시 디오판틴 근사 (Simultaneous Diophantine Approximation): 암호 분석에 사용된 역사는 있으나, 이를 기반으로 한 암호 시스템 연구는 미미했습니다.
• 목표: SA 격자 (Simultaneous Approximation Lattices) 를 사용하여 키 크기를 줄이면서도, 일반 격자 문제만큼이나 해결하기 어려운 (Hardness preserving) 새로운 암호 기반을 마련하는 것입니다. Martin (2020) 이 제안한 SA 격자는 SVP 와 SAP(동시 근사 문제) 의 동등성을 보였으나, 정수 팽창 (Integer Inflation) 이 커서 키 크기 최적화 측면에서 한계가 있었습니다.

2. 핵심 방법론 (Methodology)

2.1. SA 격자 및 새로운 문제 정의

• SA 격자 (Definition 2.1): 차원 $n$의 격자가 $I_n$ (단위 행렬) 의 열과 하나의 벡터 $x \in \mathbb{Q}^n$으로 생성되는 격자입니다. 이는 일반 격자 ($n^2$개의 정수 필요) 에 비해 $n+1$개의 정수로 표현 가능하여 저장 효율이 높습니다.
• 새로운 문제 정의:
  • SIAP (Shortest Independent Approximation Problem): SA 격자에서의 SIVP (Shortest Independent Vectors Problem) 에 해당합니다.
  • CAP (Closest Approximation Problem): SA 격자에서의 CVP (Closest Vector Problem) 에 해당합니다.
  • SAP (Simultaneous Approximation Problem): SA 격자에서의 SVP 에 해당합니다.

2.2. 일반 격자에서 SA 격자로의 근사 알고리즘 (Algorithm 1)

논문은 임의의 격자 $L$을 SA 격자로 근사하는 알고리즘을 제시합니다.

• 핵심 아이디어: 주어진 격자 행렬 $M$에 대해, $c \cdot \text{adj}(M) + A$ 형태의 행렬 $\tilde{M}$을 구성합니다. 여기서 $A$는 작은 정수 오차 행렬입니다.
• 구체적 절차:
  1. 행렬 $\tilde{M}$의 부분 행렬식 (minors) 들이 서로 소 (coprime) 가 되도록 $A$의 원소를 반복적으로 조정합니다.
  2. Lemma 2.1과 Jacobsthal 함수의 성질을 이용하여, 두 행렬식이 서로 소가 되도록 하는 작은 정수 $x$를 항상 찾을 수 있음을 증명합니다.
  3. 이렇게 생성된 $\tilde{M}$과 벡터 $b$를 사용하여 SA 격자를 생성하고, 원래 격자의 문제를 SA 격자의 문제로 변환합니다.

2.3. 축소 (Reduction) 알고리즘

• Algorithm 2, 3, 4: 각각 SVP, SIVP, CVP 문제를 SAP, SIAP, CAP 문제로 변환합니다.
• 특징: 이 변환은 차원 보존 (Dimension-preserving) 및 갭 보존 (Gap-preserving) 특성을 가지며, 결정론적 다항 시간 내에 수행됩니다.

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

3.1. 정수 팽창 (Integer Inflation) 의 최적화

• 문제: Martin 의 기존 연구에서는 정수 입력 길이가 $O(n^4 \log(nk))$로 증가하여 키 크기 감소 효과를 상쇄했습니다.
• 개선: 본 논문은 새로운 알고리즘을 통해 정수 팽창을 $O(n^2 \log(nk))$로 줄였습니다 (Theorem 2.7).
• 최적성 증명: Section 3.4 에서 이 바운드가 최적 (Optimal) 임을 증명합니다. 정수 팽창을 $O(n^{2-\epsilon})$ 이하로 줄인다면, SVP 를 다항 시간 내에 근사적으로 해결할 수 있게 되어 격자 문제의 난이도가 무너질 수 있음을 보여줍니다 (Theorem 3.14).

3.2. NP-난해성 (NP-Hardness) 증명

• Theorem 1.2: SIAP와 CAP는 임의의 상수 $\gamma$에 대해 $\ell_1, \ell_2, \ell_\infty$ 노름 하에서 NP-난해 (NP-hard) 임을 증명했습니다.
• SAP 또한 $\ell_\infty$ 노름 하에서 NP-난해이며, 특정 조건 하에서 무작위 축소 (Randomized Reduction) 를 통해 NP-난해임을 보였습니다.
• 이는 SA 격자 기반 시스템이 일반 격자 기반 시스템과 동등한 보안 강도 (Security Level) 를 가질 수 있음을 의미합니다.

3.3. 복잡도 분석

• 제안된 축소 알고리즘 (Algorithm 2, 3, 4) 의 시간 복잡도는 $O(n^5 \log^3(nk))$의 정수 연산으로 분석되었습니다 (Theorem 3.11).

4. 의의 및 결론 (Significance)

1. 보안성과 효율성의 균형: SA 격자는 일반 격자만큼 해결하기 어렵다는 것이 수학적으로 증명되었음에도 불구하고, $n+1$개의 정수로 표현되어 키 크기를 획기적으로 줄일 수 있는 잠재력을 가집니다.
2. 새로운 암호 기반: SIAP와 CAP는 기존 이상 격자 (Ideal Lattices) 의 보안 취약점을 보완하면서도 키 크기를 줄일 수 있는 새로운 암호학적 기반이 될 수 있습니다.
3. 이론적 한계 규명: 정수 팽창의 하한을 증명함으로써, SA 격자 기반 암호 시스템의 설계 시 피할 수 없는 이론적 한계를 명확히 했습니다.

결론적으로, 이 논문은 SA 격자 기반 암호 시스템이 "작은 키 크기"와 "강한 보안성"을 동시에 달성할 수 있는 유효한 후보임을 이론적으로 입증하였으며, 이를 위한 최적의 축소 알고리즘과 정수 팽창 바운드를 제시했습니다.