💻 computer science

Pseudorandom Functions in $\mathsf{NC}^1$ from LWE/LPN/CDH (Or: How to Build PRFs in $\mathsf{NC}^1$ , Generically)

이 논문은 약한 PRF를 최소한의 깊이 오버헤드로 강한 PRF로 변환하는 일반적인 변환을 소개하며, 이를 통해 LWE, LPN, CDH를 포함한 표준 가정들로부터 $\mathsf{NC}^1$ -계산 가능한 PRF의 구축을 가능하게 함으로써 저깊이 암호학 분야의 오래된 미해결 문제들을 해결한다.

원저자: Youlong Ding, Aayush Jain, Ilan Komargodski

게시일 2026-08-27

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Youlong Ding, Aayush Jain, Ilan Komargodski

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

디지털 세상에서 보안은 종종 의사난수 함수(pseudorandom function)라고 불리는 특별한 종류의 수학적 도구에 의존합니다. 이 기계는 비밀 코드와 데이터 조각을 입력받아, 이를 지켜보는 누구에게도 완전히 무작위인 것처럼 보이는 숫자 문자열을 내뱉습니다. 만약 이 기계가 제대로 작동한다면, 기계가 작동하는 모습을 여러 번 보았더라도 그 출력값과 진정한 무작위 수열 사이의 차이를 구별할 수 없습니다. 이러한 도구들은 온라인 뱅킹부터 개인 메시지에 이르기까지 모든 것을 보호하는 보이지 않는 자물쇠와 열쇠입니다. 수십 년 동안 연구자들은 이 기계들이 가능한 한 가장 빠르게 작동하도록, 즉 매우 적은 단계로 작동하도록 만드는 방법을 연구해 왔습니다. 컴퓨터 과학의 언어로 이는 매우 얕은 회로(shallow circuit)로 구축함을 의미하며, 이를 통해 현대의 프로세서에서 계산이 거의 즉각적으로 이루어지도록 합니다. 이 도구들이 더 빠르고 단순할수록, 보안 투표나 개인 데이터 공유와 같은 복잡한 시스템에서 더 효율적으로 사용할 수 있습니다.

오랫동안 우리는 빠르고 얕은 기계를 만드는 능력에 있어 고집스러운 간극을 마주해 왔습니다. 우리는 매우 강력하고 복잡한 수학적 가정을 사용하여 이를 만드는 법은 알고 있었지만, 그러한 방식은 깊고 느린 회로를 필요로 했습니다. 반대로 얕은 회로를 만들 수는 있었지만, 그것은 더 약하거나 덜 검증된 가정, 혹은 매우 특수하고 경직된 수학적 구조에 의존해야만 했습니다. 이는 마치 문을 열 수 있는 열쇠는 있지만 너무 무거워서 들고 다니기 힘들거나, 열쇠는 가볍지만 오직 하나의 이상한 자물쇠에만 맞는 것과 같았습니다. 목표는 가장 표준적이고 신뢰할 수 있는 자물쇠들을 사용하면서도, 어떤 문이든 열 수 있는 가벼운 열쇠를 찾는 것이었습니다. 이 과제는 거의 30년 동안 지속되며 디지털 세상을 안전하게 보호하는 효율성을 제한해 왔습니다.

한 연구팀이 이제 더 약하고 만들기 쉬운 도구를 속도를 늦추지 않고도 강력하고 안전한 도구로 변환하는 새로운 일반적 방법을 통해 이 간극을 메웠습니다. "Pseudorandom Functions in NC1 from LWE/LPN/CDH"라는 제목의 논문에 발표된 이들의 연구는, 가장 근본적이고 널리 신뢰받는 세 가지 수학적 가정을 사용하여 이처럼 빠르고 얕은 기계를 구축하는 것이 가능하다는 것을 보여줍니다. 연구진은 복잡한 함수를 더 작은 계산들의 트리(tree)를 통해 구축하는 오래된 아이디어인 GGM 구성을 개선함으로써 이 성과를 달。냈습니다. 전통적인 방식은 매 걸음마다 동일한 노력이 필요한 긴 복도를 걷는 것과 같아서 전체 여정이 길고 느려졌습니다. 새로운 방법은 복도의 형태를 바꿉니다. 과정이 트리 내부로 깊숙이 들어갈수록, 각 단계에서 요구되는 작업량이 기하급수적으로 줄어듭니다. 처음 몇 단계는 무겁지만, 이후의 단계들은 매우 빠르게 점점 더 가벼워져서 전체적인 노력의 총합이 작게 유지됩니다. 이 "테이퍼링(tapering, 점진적 감소)" 기술 덕분에 연구진은 전체 과정을 얕고 빠른 회로의 범위 안에 유지할 수 있었습니다.

이 새로운 방법이 작동함을 증old하기 위해, 연구팀은 해결하기 어려운 것으로 알려진 세 가지 특정 수학적 문제에 이를 적용했습니다. 첫 번째는 노이즈가 섞인 데이터 세트에서 숨겨진 패턴을 찾는 것과 관련된 '오류를 포함한 학습(Learning With Errors, LWE)' 문제입니다. 이 문제로부터 빠른 기계를 구축하려는 이전의 시도들은 매우 큰 숫자를 사용하는 더 복잡한 버전의 수학을 필요로 했습니다. 새로운 연구는 훨씬 작은 숫자를 사용하는 표준 버전만으로도 충분하다는 것을 보여줍니다. 두 번째 문제는 무작위로 뒤집힌 비트 스트림에서 숨겨진 패턴을 찾는 '노이즈를 포함한 패리티 학습(Learning Parity with Noise, LPN)'입니다. 연구진은 이 방법이 기존에 필요했던 특수하고 구조화된 버전 없이도 표준 버전과 함께 작동함을 입증했습니다. 세 번째는 현대 인터넷 보안의 초석이자 비밀 키 교환에 사용되는 '연산 디피-헬먼(Computational Diffie-Hellman, CDH)' 가정입니다. 수십 년 동안 이 가정으로부터 빠른 기계를 만드는 유일한 방법은 더 강력하고 제한적인 버전의 문제에 의존해 왔습니다. 새로운 구성은 표준 버전만으로도 충분하다는 것을 증명합니다.

이 연구의 중요성은 그 일반성과 표준적인 가정들에 대한 의존성에 있습니다. 약하고 얕은 도구를 속도를 늦추지 않고도 강력하고 안전한 것으로 업그레이드할 수 있음을 보여줌으로써, 연구진은 가장 기초적이고 잘 연구된 수학적 문제들로부터 빠르고 안전한 함수를 구축할 수 있는 능력을 열어주었습니다. 이는 해당 분야의 여러 오랜 질문들을 해결하며, 미래의 암호 시스템을 위한 새롭고 유연한 청사진을 제공합니다. 연구진은 단순히 이것이 가능할 수도 있다고 제안한 것이 아니라, 구체적이고 단계적인 구성법과 그것이 작동한다는 엄격한 증명을 제공했습니다. 그들은 결과물인 기계의 깊이가 시작점이 된 도구의 깊이와 본질적으로 동일함을 보여줌으로써, 속도의 이점을 유지하면서도 필요한 보안성을 확보했습니다.

이 성과는 우리가 가장 흔하고 신뢰할 수 있는 수학적 토대를 사용하여, 속도를 희생하지 않고도 이러한 필수적인 보안 도구들을 구축할 수 있게 되었음을 의미합니다. 이는 효율성을 위해 이전에 필수적이라고 생각되었던 특수하고 복잡한 변형 모델들을 사용할 필요를 없애줍니다. 그 결과, 더 넓은 범위의 기술에 배포될 수 있는 더 빠르고 효율적인 암호화 방법을 가능하게 하여, 미래의 디지털 보안을 위한 더욱 견고하고 다재다능한 토대를 마련했습니다. 이 연구는 약하고 빠른 도구와 강하고 빠른 도구 사이의 장벽이 허물어졌음을 보여주는 결정적인 증거이며, 효율적인 암호 설계의 새로운 시대를 여는 문을 열었습니다.

기술 요약: LWE/LPN/CDH로부터의 NC1 내 의사난수 함수(Pseudorandom Functions)

1. 문제 정의

낮은 병렬 복잡도(구체적으로, 다항 크기 및 로그 깊이 회로에 의해 계산 가능한 클래스인 NC1 내)를 갖는 의사난수 함수(PRF)의 구축은 암호학계의 오랜 미해결 과제였다. PRG(의사난수 생성기)로부터 GGM 변환을 통해 일반적인 PRF를 구축할 수 있지만, 이 방법은 본질적으로 순차적이다. 기반이 되는 PRG가 로그 깊이 내에서 계산 가능하더라도, 결과물인 PRF는 $\omega(\log n)$ 의 깊이를 요구하므로 NC1 범위를 벗어나게 된다.

본 연구 이전에는 알려진 NC1 계산 가능 PRF가 매우 드물었으며, 매우 특수한 대수적 구조나 강력한 가정들에 의존했다:

Naor-Reingold (1997, 2004): 결정적 디피-헬먼(DDH) 및 소인수 분해로부터 $TC_0 \subseteq NC1$ 내의 PRF를 구축하였다.
Banerjee-Peikert-Rosen (2012): Ring-LWE로부터 $TC_0$ 내의 PRF를 구축했으나, 초다항식(super-polynomial) 모듈러스-대-노이즈 비율을 요구했다.
Ding-Jain-Komargodski (2025): SeededLPN 또는 Ring-LPN과 같은 구조화된 변형 LPN으로부터 PRF를 구축하였다.

핵본질적인 과제는 구조화된 변형(structured variants)이나 초다항식 파라미터에 의존하지 않고, 표준 가정(다항식 모듈러스-대-노이즈 비율을 갖는 LWE, 표준 LPN, 그리고 CDH)으로부터 NC1 계산 가능한 PRF를 달성하는 것이다.

2. 방법론

본 논문은 두 갈래의 접근 방식, 즉 약한 PRF(WPRF)에서 강한 PRF로의 일반적인 깊이 보존 변환과, 표준 가정으로부터의 새로운 깊이 효율적 WPRF(또는 Synthesizer) 구축을 도입한다.

2.1 Tapering-GGM: 일반적인 변환

저자들은 GGM 트리 구축을 새롭게 변형한, WPRF를 강한 PRF로 업그레이드하면서 평가 회로의 깊이를 보존하는 Tapering-GGM을 제안한다.

테이퍼링 메커니즘 (The Tapering Mechanism): 표준 GGM 트리에서는 상태 크기가 일정하게 유지되며, 깊이가 트리 레벨 수( $\ell \cdot d_{WPRF}$ )에 따라 선형적으로 누적된다. Tapering-GGM에서는 각 레벨에서 상태 크기가 기하급수적으로 줄어든다. 레벨 $i$ 에서의 보안 파라미터를 $\lambda^{(i)}$ 라고 할 때, 저자들은 $\lambda^{(i)} = \lambda^{2^{-i+1}}$ 로 정의한다. 결과적으로, 레벨 $i$ 에서의 WPRF 호출 깊이 $d(\lambda^{(i)})$ 는 기하급수적으로 감소한다.
깊이 분석: 기초 WPRF의 깊이가 $d(\lambda) = \Theta(\log \lambda)$ 라면, Tapering-GGM 구축의 총 깊이는 다음과 같다:
$d_{total} = O(\log \lambda) + \sum_{i=1}^{\ell} d(\lambda^{(i)}) \approx O(\log \lambda) + \sum_{i=1}^{\ell} \log(\lambda^{2^{-i+1}}) = O(\log \lambda)$
이러한 기하급수적 감소는 총 깊이가 $O(d(\lambda))$ 가 되도록 보장하여, 입력 WPRF가 NC1에 있다면 구축물 또한 NC1 내에 머물게 한다.
보안 과제 및 해결책:
- 과제: 트리가 깊어질수록 보안 파라미터 $\lambda^{(i)}$ 가 작아져(sub-polynomial), 기반 WPRF의 계산적 보안을 깨뜨릴 수 있다.
- 해결책 1 (해싱): 입력은 먼저 쌍별 독립 해시 함수(pairwise independent hash function)를 통해 해싱된다. 이를 통해 높은 확률로 공격자의 쿼리가 상위 $O(\log_\Delta q)$ 레벨 내에서 서로 다른 경로로 "파쇄(shattered)"되어, 보안 파라미터가 여전히 다항식 수준을 유지하도록 한다.
- 해결책 2 (키 균일성): 파쇄 지점 아래의 레벨들에 대해서는 정보 이론적 보안에 의존한다. 저자들은 WPRF가 키 균일(key-uniform)(1-wise independent)할 것을 요구한다. 파쇄 레벨에서의 상태가 의사난수라면, 이후의 키 균일 변환들의 합성은 하위 레벨 WPRF의 계산적 난이도와 무관하게 해당 상태를 완벽하게 균등한 출력으로 매핑한다.

2.2 깊이 효율적 WPRF 구축

저자들은 새로운 WPRF 구축을 통해 Tapering-GGM 프레임워크를 구체화한다.

LWE (Learning With Errors)로부터:
- 저자들은 다항식 모듈러스-대-노이즈 비율 ( $\alpha = n^{-\epsilon}$ )을 갖는 표준 LWE로부터 최초의 NC1 WPRF를 구축한다.
- 핵심 기술 도구: $O(\text{poly}(\log \log \lambda))$ 깊이로 계산 가능한 Rounded Gaussian Sampler를 사용한다. 이들은 $\ln, \cos$ 에 대한 저깊이 다항식 근사와 제곱근에 대한 뉴턴 반복법을 사용하여 Box-Muller 변환을 근사한다.
- 구축: Kim [Kim20]에서 영감을 받은 **체이닝 패러다임(chaining paradigm)**을 채택한다. 이 구축은 레이어별로 마스킹된 LWE 내적을 계산한다. 한 레이어 출력의 고차 비트(high-order bits)는 다음 레이어의 오차 분포를 결정론적으로 샘플링한다. 오차 샘플러의 유계성(boundedness)은 안정성을 보장하며, 이를 통해 하이브리드 증명을 진행할 수 있게 한다.
LPN (Learning Parity with Noise)로부터:
- 저자들은 표준 LPN(임의의 역다항식 노이즈)으로부터 NC1 내의 WPRF를 제공하는 최근의 결과인 Ding, Jain, and Komargodski [DJK25]를 활용한다.
- 이를 Tapering-GGM과 결려, 구조화된 변형(예: Ring-LPN)의 필요 없이 표준 LPN으로부터 최초의 NC1 PRF를 얻는다.
CDH (Computational Diffie-Hellman)로부터:
- 저자들은 Tapering-GGM이 WPRF보다 더 약한 프리미티브인 Synthesizer(입력 풀이 공격자로부터 숨겨진 형태)를 실제로 요구한다는 점에 주목한다.
- 저자들은 Naor-Reingold의 Synthesizer 구축 [NR95, NR99]을 사용하여 이를 구현하며, 이는 CDH 가정 하에 NC1에서 계산 가능하다. 이는 DDH 기반의 기존 구축을 개선한 최초의 NC1 PRF를 제공한다.

3. 주요 기여

일반적인 깊이 보존 변환: 깊이 $d(\lambda) = \Omega(\log \lambda)$ 로 계산 가능한 임의의 WPRF(또는 Synthesizer)를 깊이 $O(d(\lambda))$ 인 강한 PRF로 변환하는 블랙박스 변환을 제공한다. 이는 NC1 PRF를 가로막던 일반적인 장벽을 해결한다.
표준 LWE로부터의 NC1 PRF: 다항식 모듈러스-대-노이즈 비율 $\alpha = n^{-\epsilon}$ 을 갖는 LWE로부터 PRF를 구축하는 최초의 사례로, Vaikuntanathan의 강의 노트에 명시된 공개된 문제를 해결한다. 이는 GapSVP의 어려움에 기반한다.
표준 LPN으로부터의 NC1 PRF: 구조화된 변형(Ring-LPN 또는 Sparse LPN 등)의 필요성을 제거하고, 표준 LPN 가정으로부터 NC1 내의 PRF를 구축하는 최초의 사례를 제시한다.
CDH로부터의 NC1 PRF: DDH라는 더 강한 가정에 의존했던 30년 된 Naor-Reingold의 결과를 개선하여, CDH 가정으로부터 NC1 내의 PRF를 구축하는 최초의 사례를 제시한다.
저깊이 가우시안 샘플러 (Low-Depth Gaussian Sampler): LWE 기반 WPRF의 핵심 구성 요소인 Rounded Gaussian 오차를 $O(\text{poly}(\log \log \lambda))$ 깊이로 샘플링하는 새로운 결정론적 회로를 제공한다.

4. 결과

본 논문은 다음과 같은 구체적인 결과를 확립한다:

정리: 만약 NC1 내에 WPRF가 존재한다면, NC1 내에 PRF가 존재한다.
따름정리 (LWE): 노이즈-대-모듈러스 비율 $\alpha = n^{-\epsilon}$ 에 대해 LWE 가정이 성립한다고 가정하면, NC1 내에 PRF가 존재한다.
따름정리 (LPN): 노이즈 확률 $\mu = n^{-\epsilon}$ 에 대해 LPN 가정이 성립한다고 가정하면, NC1 내에 PRF가 존재한다.
따름정리 (CDH): CDH 가정이 성립한다고 가정하면, NC1 내에 PRF가 존재한다.
따름정리 (GapSVP): GapSVP가 $\tilde{O}(n^{1+\epsilon})$ 인자 내에서 근사하기 어렵다고 가정하면, NC1 내에 PRF가 존재한다.

5. 의의

본 논문은 암호학적 프리미티브의 복잡도에 관한 여러 오랜 미해결 과제들을 해결한다고 주장한다. PRF 평가의 깊이를 GGM 변환의 순차적 특성으로부터 분리함으로써, 저자들은 병렬 효율성을 희생하지 않고도 광범위한 표준 가정으로부터 강력한 PRF를 구축할 수 있음을 입증한다.

구체적으로, 본 연구는:

NC1 PRF를 위해 Ring-LWE 및 초다항식 파라미터에 의존하던 것을 제거하고, 다항식 파라미터를 갖는 표준 LWE로 이동했다.
구조화된 LPN 변형에 대한 의존성을 제거하고, 표준 LPN으로 이동했다.
CDH 기반 PRF의 어려움 가정을 DDH에서 CDH로 약화시켰다.
기존의 로그 깊이 WPRF 후보들(예: [ABG+14], [AR16])을 로그 깊이 PRF로 업그레이드할 수 있는 일반적인 프레임워크(Tapering-GGM)를 제공한다.

저자들은 이 연구가 암호학의 병렬 복잡도를 이해하는 데 있어 근본적인 단계이며, 안전한 계산 프로토콜, 학습 이론(PRF-versus-learning 연결 관계를 통한), 그리고 메타 복잡도(meta-complexity)에 시사하는 바가 크다고 강조한다.