🔢 mathematics

Cryptanalysis of the Legendre Pseudorandom Function over Extension Fields

이 논문은 확장체 $\mathbb{F}_{p^r}$ 상의 단일 차수 레전드르 의사난수 함수 (PRF) 에 대해, 수동 공격 모델에서는 새로운 '차분 서명' 기법으로, 능동 공격 모델에서는 기하급수적 시퀀스를 이용한 테이블 충돌 공격으로 각각 키를 효율적으로 복원하는 방법을 제시하고, 이를 방어하기 위해 2 차 이상의 고차 키 변형이 필수적임을 증명합니다.

원저자: Daksh Pandey

게시일 2026-04-07

📖 3 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Daksh Pandey

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

1. 배경: 왜 '확장된 땅'으로 갔을까? (PRF 와 확장 체)

원래 상황 (소수 필드 $\mathbb{F}_p$ ):
예전에는 암호를 만들 때 '소수 (Prime number)'라는 작은 마을을 사용했습니다. 여기서는 숫자를 더할 때 10 이 넘으면 10 자리로 넘어가는 **'올림 (Carry)'**이 발생했습니다. 이 '올림' 현상 때문에 해커들이 특정 패턴을 찾아내는 것이 매우 어려웠습니다.
새로운 시도 (확장 필드 $\mathbb{F}_{p^r}$ ):
하지만 더 많은 데이터를 빠르게 처리하려면 마을을 크게 확장해야 했습니다. 그래서 '다항식 (Polynomial)'이라는 새로운 언어를 도입했습니다.
- 비유: 마치 숫자 10 을 더할 때 10 이 넘으면 10 자리로 넘어가는 대신, 각 자리수끼리만 따로 더하고 10 이 넘으면 버리는 방식으로 바꾼 것입니다.
- 문제점: 이렇게 하면 '올림'이 사라져서 계산은 빨라졌지만, 해커들이 생각할 때 "아, 이 규칙은 너무 단순해 보이는데?"라는 생각이 들게 만들었습니다.

2. 첫 번째 공격: "무질서한 줄거리"의 비밀 (수동 공격)

해커들은 처음에 "확장된 땅에서는 숫자가 더해질 때 올림이 없어서, 연속된 숫자 패턴이 깨져서 (Fracture) 해독이 안 되겠구나"라고 생각했습니다. 마치 줄을 서서 번호를 매길 때, 갑자기 번호가 뒤죽박죽 섞여서 패턴을 찾을 수 없을 것 같다고 말입니다.

논문의 발견:
하지만 저자는 **"아니, 그 패턴이 깨진 게 아니라, 아주 규칙적으로 반복되는 '주름'이 생겼을 뿐이야"**라고 지적했습니다.
비유 (지문 분류기):
해커는 깨진 숫자 줄을 보고 "이건 1 번 패턴, 저건 2 번 패턴"이라고 **모양 (Shape)**별로 분류했습니다. 마치 흩어진 퍼즐 조각을 모양별로 통에 담는 것처럼요.
- 이 '모양 통 (Differential Signature)'에 숫자들을 넣으면, 원래의 비밀 열쇠 (Key) 를 찾아낼 수 있는 단서가 모여듭니다.
- 결과: 해커는 이 방법을 통해 수동적으로 (사용자가 모르게) 비밀 열쇠를 찾아냈습니다.

3. 두 번째 공격: "기하학적 춤"으로 방어 뚫기 (능동 공격)

수동 공격도 위험했지만, 해커가 더 적극적으로 서버에 질문을 던지는 경우 (선택 질의 공격) 는 어떨까요?

공격 방법:
해커는 "숫자를 1, 2, 3, 4... 순서로 더하는 게 아니라, 기하급수적으로 (1, 2, 4, 8, 16...) 커지는 숫자"를 요청했습니다.
비유 (마법 지팡이):
이 기하급수적인 숫자들은 '올림'이 사라진 확장된 땅에서도 **곱셈의 마법 (Homomorphism)**을 유지합니다.
- 마치 해커가 "비밀 열쇠를 가진 사람, 이 기하학적 춤을 추면 열쇠가 어디에 숨어 있는지 알려주세요"라고 명령한 것과 같습니다.
- 이 춤을 추면, 복잡한 암호가 단순한 '이동 (Shift)' 문제로 변해버립니다.
결과: 해커는 이 방법을 통해 매우 빠르게 (O( $p^r/M$ )) 비밀 열쇠를 찾아냈습니다. 기존에 안전하다고 생각했던 방어선이 완전히 무너진 것입니다.

4. 결론 및 해결책: "단순한 열쇠는 안 됩니다"

이 논문의 결론은 매우 명확합니다.

현재 상태: 1 차 다항식 (단순한 선형 구조) 으로 만든 레전드르 암호는, 확장된 땅 ( $\mathbb{F}_{p^r}$ ) 에서는 완전히 안전하지 않습니다. 해커가 수동적으로나 능동적으로나 쉽게 뚫을 수 있습니다.
해결책:
- 비유: 단순한 직선 모양의 자물쇠 (1 차) 는 쉽게 부러집니다. 하지만 **곡선이나 복잡한 모양 (2 차 이상, $d \ge 2$ )**으로 자물쇠를 만들면 해커가 "이동"이나 "분류"로 뚫기가 훨씬 어려워집니다.
- 제안: 앞으로는 단순한 1 차 다항식이 아니라, 2 차 이상의 복잡한 다항식을 사용하여 암호를 만들어야 합니다. 그래야 해커가 아무리 clever 한 수를 써도, 복잡한 곡선 때문에 열쇠를 찾을 수 없게 됩니다.

요약

이 논문은 **"새로운 암호 기술이 계산 속도를 위해 단순한 규칙 (확장 필드) 을 도입했지만, 그 단순함 때문에 해커에게 뚫리기 쉬운 약점이 생겼다"**는 것을 증명했습니다. 해커는 패턴 분류와 기하학적 춤이라는 두 가지 방법으로 이 약점을 공격했고, 따라서 우리는 더 복잡하고 구불구불한 (고차 다항식) 암호를 만들어야 안전하다고 경고합니다.

1. 문제 제기 (Problem Statement)

배경: 레전드르 의사난수 함수 (Legendre PRF) 는 다자간 계산 (MPC) 과 영지식 증명 (ZKP) 프로토콜에서 곱셈 복잡도가 낮아 매우 효율적인 암호 원시 (primitive) 로 주목받고 있습니다. 기존에는 소수 필드 ( $\mathbb{F}_p$ ) 상에서의 보안성이 광범위하게 연구되었습니다.
도전 과제: 최근 특정 암호 프로토콜의 처리량 (throughput) 을 최적화하기 위해 연산을 확장 필드 (Extension Fields, $\mathbb{F}_{p^r}$ ) 로 확장하려는 시도가 늘고 있습니다.
핵심 질문: 소수 필드에서의 안전성을 가진 레전드르 PRF 를 확장 필드 ( $\mathbb{F}_{p^r}$ ) 에 적용할 때, 다항식 입력 인코딩의 구조적 특성 (특히 '캐리 없는 덧셈') 이 기존 공격 기법을 어떻게 변화시키며, 여전히 안전한지 여부가 명확하지 않았습니다. 본 논문은 단일 차수 ( $d=1$ ) 레전드르 PRF 에 대한 최초의 포괄적인 암호 분석을 수행합니다.

2. 방법론 (Methodology)

저자는 두 가지 주요 위협 모델 (Threat Model) 하에서 공격 기법을 개발했습니다.

A. 수동 공격 모델 (Passive Threat Model)

가정: 공격자는 서버가 생성한 순차적인 카운터 ( $n$ ) 기반의 키스트ream 을 관찰합니다.
구조적 분석:
- 확장 필드 $\mathbb{F}_{p^r}$ 에서 정수 $n$ 을 다항식으로 인코딩할 때, 계수별 덧셈 (coefficient-wise addition) 이 수행되므로 정수 덧셈의 '캐리 (carry)' 현상이 발생합니다. 이를 "No-carry fracture(캐리 없는 균열)" 라고 명명했습니다.
- 이 균열은 기존의 슬라이딩 윈도우 충돌 공격 (sliding-window collision attacks) 을 무력화하는 것처럼 보이지만, 실제로는 결정론적으로 주기적 (deterministically periodic) 인 패턴을 생성합니다.
공격 기법 (Differential Signature):
- 공격자는 입력 시퀀스의 차분 (differential) 패턴을 분석하여 "Differential Signature(차분 서명)" 을 정의합니다.
- 이 서명을 기반으로 균열된 시퀀스 윈도우들을 구조적 모양 (shape) 에 따라 그룹화 (bucketing) 합니다.
- 이를 통해 공격자는 수동적으로 키를 복원할 수 있습니다.

B. 능동 공격 모델 (Active Chosen-Query Threat Model)

가정: 공격자는 서버에 원하는 입력을 선택하여 쿼리할 수 있습니다.
공격 기법 (Geometric Sequence Attack):
- 공격자는 덧셈의 한계를 우회하기 위해 기하급수적 시퀀스 (Geometric Sequence) 를 생성합니다. 즉, $\mathbb{F}_{p^r}^*$ 의 원시 원소 (primitive generator) $g(x)$ 를 사용하여 $g^i$ 형태의 입력을 쿼리합니다.
- 레전드르 기호의 승법 동형성 (Multiplicative Homomorphism) 을 활용합니다.
- 이를 통해 $L(g^i + K)$ 식을 비밀 키 $K$ 에 의존하는 상수와 보편적인 참조 시퀀스의 이동 (shift) 으로 분해 (factoring) 할 수 있습니다.
- 이 구조를 이용해 최첨단 테이블 충돌 공격 (Table Collision Attack) 을 확장 필드에 직접 적용하여 키를 추출합니다.

3. 주요 기여 (Key Contributions)

구조적 취약점 규명: 확장 필드에서의 다항식 인코딩이 생성하는 "No-carry fracture"가 방어 메커니즘이 아니라, 오히려 결정론적인 주기성을 통해 공격을 용이하게 만든다는 것을 증명했습니다.
새로운 수동 공격 알고리즘: "Differential Signature" 버킷팅 기법을 도입하여, 캐리 없는 균열을 우회하고 $O(U \cdot p^r/M)$ 연산으로 비밀 키를 복원하는 방법을 제시했습니다. ( $U$ : 유니시티 거리, $M$ : 관찰된 비트 수)
능동 공격의 최적화: 기하급수적 쿼리 구조를 통해 승법 동형성을 유도하고, 이를 통해 키 복원 복잡도를 $O(p^r/M)$ 으로 낮추는 공격을 정립했습니다. 이는 기존 소수 필드 공격의 일반화입니다.
보안 한계 설정: 단일 차수 ( $d=1$ ) 레전드르 PRF 는 확장 필드에서 수동 및 능동 모델 모두에서 완전히 깨졌음을 증명하고, 안전한 사용을 위해 고차수 키 변형 ( $d \ge 2$ ) 이 필수적임을 규명했습니다.

4. 결과 (Results)

수동 공격: 공격자는 관찰된 키스트림을 분석하여 차분 서명 패턴을 매칭함으로써, $O(U \cdot p^r/M)$ 시간 복잡도로 비밀 키를 복원할 수 있습니다.
능동 공격: 기하급수적 쿼리를 통해 공격자는 키를 순수한 지수 이동 (exponent shift) 문제로 환원시켜, $O(p^r/M)$ 시간 복잡도로 키를 추출합니다. 이는 이론적 하한선에 도달하는 효율적인 공격입니다.
고차수 변형의 필요성: 2 차 이상 ( $d \ge 2$ ) 의 다항식을 사용하는 경우, 위 공격 기법들이 대수적으로 분해되지 않아 무력화됩니다. 하지만 여전히 MITM(Meet-in-the-Middle) 공격 등에 취약할 수 있으므로, $d \ge 3$ 또는 $4$ 를 권장합니다.

5. 의의 (Significance)

실무적 경고: 현재 MPC 및 ZKP 프로토콜에서 성능 향상을 위해 확장 필드 ( $\mathbb{F}_{p^r}$ ) 를 도입하려는 시도가 증가하고 있는데, 본 논문은 단일 차수 ( $d=1$ ) 레전드르 PRF 를 확장 필드에 사용하는 것은 절대적으로 안전하지 않다고 경고합니다.
표준화 및 설계 지침: 향후 레전드르 PRF 를 확장 필드 환경에 배포할 때는 반드시 고차수 다항식 ( $d \ge 2$ ) 을 사용하여 대수적 구조를 복잡하게 만들어야 함을 수학적으로 입증했습니다.
이론적 발전: 다항식 인코딩의 "캐리 없는" 특성이 생성하는 구조적 패턴을 분석하고, 이를 역이용하는 새로운 암호 분석 기법 (Differential Signature, Geometric Sequence Factorization) 을 제시하여 확장 필드 기반 PRF 연구의 새로운 지평을 열었습니다.

결론적으로, 본 논문은 확장 필드 환경에서의 레전드르 PRF 가 기존에 생각했던 것보다 훨씬 취약하며, 안전한 사용을 위해서는 단순한 필드 확장이 아닌 키의 다항식 차수 증가가 필수적임을 명확히 보여줍니다.