기술 요약: 저노이즈 LPN에 대한 최악의 경우 어려움(Worst-case Hardness)을 향하여

문제 정의

학습 패리티 노이즈(Learning Parity with Noise, LPN) 문제는 암호학의 기초적인 가정으로, 대칭 키 프리미티브 및 공개 키 암호(PKE)의 기반 역할을 한다. 유사한 LWE(Learning With Errors) 문제의 평균적인 경우의 어려움(average-case hardness)은 최악의 경우 격자 가정(worst-case lattice assumptions)에 의해 뒷받침되는 반면, LPN에 대해 이와 유사한 최악의 경우-평균의 경우 환산(worst-case-to-average-case reduction)을 확립하는 것은 여전히 핵심적인 미해결 과제로 남아 있다.

선형 코드의 통계적 평활화(statistical smoothing)에 의존하는 기존의 LPN 환산 방식들, 구체적으로 Brakerski 등[BLVW19]과 Yu 및 Zhang[YZ21]의 연구는 이 방법을 사용한다. 이러한 방법들은 생성 행렬(generator matrix)의 행들의 무작위 희소 조합(random sparse combinations)이 통계적으로 균등 분포(uniform)에 가까워야 한다는 요구사항을 가진다. 이 요구사항은 결과적인 평균적인 경우의 어려움을 노이즈율 $1/2 - 1/\text{poly}(n)$ 수준으로 제한하게 된다. 이러한 높은 노이즈율은 일반적으로 역 다항식(inverse-polynomial) 노이즈율(예: $n^{-1/2}$) 또는 부서브 지수 시간 알고리즘에 대한 상수 노이즈율을 필요로 하는 공개 키 애플리케이션에는 불충분하다. 또한, 이러한 기존 환산에서 요구되는 최악의 경우 가정(예: 매우 낮은 노이즈율에서의 최근 근접 코드 문제(Nearest Codeword Problem))은 약하거나 비현실적인 전처리 가정을 요구한다.

방법론

저자들은 통계적 평활화 요구사항을 **계산적 구별 불가능성(computational indistinguishability)**으로 완화하는 새로운 접근 방식을 제안한다. 무작위 희상 조합이 통계적으로 균등 분포에 가까워야 한다고 요구하는 대신, 저자들은 해당 조합이 균등 분포와 계산적으로 구별 불가능하기만을 요구한다.

이러한 전환은 주어진 행렬 $A \in \mathbb{F}_2^{m \times n}$의 특성에 기반한 "윈-윈(win-win)" 구조로 이어진다:

1. 코드의 디코딩: 만약 무작위 조합이 계산적으로 균등 분포와 구별 불가능하다면, 효율적인 LPN 솔버를 사용하여 $A$에 의해 생성된 코드를 무작위 노이즈로부터 디코딩할 수 있다.
2. 듀얼(Dual)의 구별: 만약 무작위 조합이 계산적으로 균등 분포와 구별 가능하다면, 구별기(distinguisher)는 $A$의 듀얼 코드에 대한 디코딩 문제의 결정 버전(decision version)을 해결하게 된다(구체적으로, 고정 가중치 신드롬(fixed-weight syndromes)을 균등 분포와 구별하는 문제).

이 환산은 $A$를 생성 행렬으로 볼 때, $A^T$가 듀얼 코드의 패리티 검사 행렬(parity-check matrix) 역할을 한다는 관찰에 기초한다. $r^T A$가 주어졌을 때 벡터 $r$을 복구하는 것은 $r$을 노이즈 벡터로 하는 듀얼 코드를 디코딩하는 것과 동일하다.

주요 기여 및 결과

1. 주요 환산 정리

본 논문은 LPN의 어려움이 다음 두 문제의 **최악의 경우 동시 어려움(worst-case simultaneous hardness)**으로부터 도출됨을 보여주는 환산(정리 3.1)을 제시한다.

• 행렬 $A$에 의해 생성된 코드를 무작위 노이즈로부터 디코딩하는 문제.
• $A$의 듀얼 코드의 무작위 노이즈가 섞인 코드워드(신드롬)를 균등 분포와 구별하는 문제.

정리 1.1 (비형식적): $n$개의 변수, $t$개의 샘플, 그리고 노이즈율 $n^{-\alpha}$를 갖는 Search LPN을 해결하는 데 있어 비영(non-negligible) 이득을 갖는 효율적인 알고리즘이 존재한다고 가정하자. 임의의 상수 $\beta > 0$ (단, $\alpha + \beta < 1$)에 대하여, 모든 행렬 $A$에 대해 다음을 만족하는 효율적인 알고리즘 $S$와 $D$가 존재한다:

• $S$는 노이즈율 $n^{-(\alpha+\beta)}$를 갖는 무작위 노이즈로부터 $A$에 의해 생성된 코드를 디코딩할 수 있다.
• 또는 $D$는 노이즘율 $n^{\beta}/m$에 대해 듀얼의 노이즈가 섞인 코드워드를 균등 분포와 구별할 수 있다.

2. 공개 키 암호학을 위한 인스턴스화

특정 파라미터를 설정함으로써, 저자들은 자신들의 환산이 Alekhnovich의 공개 키 암호 구성[Ale03]에 필요한 영역에서 LPN 어려움을 도출함을 입증한다.

• 파라미터: $\alpha = 0.5$ (목표 노이즈율 $n^{-0.5}$), $\beta = 0.45$, $m = O(n^{2.9})$로 설정.
• 결과: 이는 코드와 그 듀얼의 동시 최악의 경우 어려움을 가정할 때, $t=2n$ 샘플과 노이즈율 $n^{-0.5}$를 갖는 LPN의 어려움을 함의한다.
• 의의: 이 파라미터 영역은 통계적 평활화를 사용하는 기존의 최악의 경우 환산을 통해서는 접근할 수 없었던 영역이었다.

3. 기술적 과제 및 해결책

저자들은 통계적 평활화에서 계산적 평활화로 이동할 때 발생하는 어려움을 다룬다. 통계적 설정에서는 푸리에 분석(Fourier analysis)을 통해 평활화된 행렬과 노이즈의 결합 분포를 쉽게 처리할 수 있다. 계산적 설정에서 저자들은 $r^T A$가 의사 난수(pseudorandom)라 하더라도, 누설된 정보인 $r^T e$가 결합 분포를 구별 가능하게 만들 가능성이 있음을 보여준다.

• 해결책: 환산은 **무작위 베르누이 노이즈(random Bernoulli noise)**로부터 디코딩하는 알고리즘 $S$를 구축한다. 저자들은 대부분의 평활화 벡터 $r$의 선택에 대해, 비트 $r^T e$가 $r$이 고정된 후에도 독립적인 베르누이 변수처럼 행동한다는 것을 증명한다. 이를 통해 모든 최악의 경우 에러 벡터에 대해 $r^T e$가 편향되지 않아야 한다는(이전의 장벽이었던) 조건 없이도 환산을 진행할 수 있게 된다.

의의 및 주장

본 논문은 최악의 경우 가정으로부터 역 다항식 노이즈율(구체적으로 $n^{-1/2}$)을 갖는 LPN의 평균적인 경우의 어려움을 확립하기 위한 경로를 제공한다고 주장한다. 이는 LWE에 비해 달성하기 어려웠던 목표인, 최악의 경우 어려움으로부터 공개 키 암호를 구축하기 위한 중요한 진전이다.

저자들은 다음과 같은 한계점과 겸손한 주장을 명시한다:

• 비표준적 가정: 이 환산은 코드와 그 듀얼를 디코딩하는 문제의 동시 어려움에 의존한다. 이 가정은 비표준적이며 독립적으로 연구된 바 없다. 저자들은 이 가정이 기존의 가정보다 더 약하다고 주장하는 것이 아니라, 통계적 평활화 장벽을 우회하기 위한 특정 접근 방식에 필수적인 조건임을 밝힌다.
• 무작위 vs 최악의 경우 노이즈: 결과적인 디코더 $S$는 최악의 경우 유계 가중치(bounded-weight) 노이즈가 아닌 무작위 베르누이 노이즈에 대해 작동한다. 저자들은 자신의 접근 방식을 최악의 경우 노이즈로 확장하는 것이 결과를 크게 강화하겠지만, 계산적 엔트로피를 추론하기 위한 새로운 도구가 필요할 것이라고 인정한다.
• 부서브 지수 시간: 정리에서 명시된 최악의 경우 문제들(일반적인 코드를 디코딩하고 그 듀얼을 디코딩하는 문제)에 대한 최선의 알고리즘은 부서브 지수 시간(sub-exponential time)으로 실행된다. 따라서 이 환산은 부서브 지수 최악의 경우 어려움 가정을 바탕으로 다항 시간 알고리즘에 대한 LPN의 어려움을 확립한다.

요약하자면, 본 논문은 통계적 요구사항을 계산적 요구사항으로 교환함으로써, 코드와 그 듀얼의 동시 어려움을 수용한다면 공개 키 암호에 충분한 노이즈율에서 LPN의 어려움을 가능하게 하는 "클린 윈-윈(clean win-win)" 환산을 제공한다.