🔢 mathematics

Notes on the LVP and CVP in $p$ -adic Fields

이 논문은 $p$ -adic 체의 비아르키메데스 성질과 최대 순서 및 $p$ -근의 구조를 활용하여 $p$ -adic 격자의 직교 기저를 다항 시간 내에 계산하고, 이를 통해 최장 벡터 문제 (LVP) 와 최단 벡터 문제 (CVP) 를 효율적으로 해결하는 알고리즘을 제안합니다.

원저자: Chi Zhang, Mingqian Yao

게시일 2026-04-13

📖 3 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Chi Zhang, Mingqian Yao

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

🌍 배경: 평범한 세상 vs. p-진수 세상

우리가 일상에서 사용하는 공간 (유클리드 공간) 은 '평범한 세상'입니다. 여기서 두 점 사이의 거리는 피타고라스 정리처럼 직선으로 재고, 삼각형의 변의 길이는 항상 두 변의 합보다 짧습니다.

하지만 이 논문이 다루는 **'p-진수 세상'**은 완전히 다릅니다.

비유: 이 세상의 거리 법칙은 **"큰 소리가 들리면 작은 소리는 무시된다"**는 원칙입니다.
- 예를 들어, 100 원짜리 동전과 1 원짜리 동전을 합치면, 100 원짜리 동전의 크기에만 영향을 받고 1 원은 아예 존재하지 않는 것처럼 취급됩니다. (수학적으로는 $|a+b| \le \max(|a|，|b|)$ )
이 '비아르키메데스 (non-Archimedean)'라는 이상한 법칙 때문에, 평범한 세상에서 쓰던 거리 계산법 (LLL 알고리즘 등) 은 여기서 통하지 않습니다.

🏰 문제: 암호의 성벽을 뚫는 열쇠

최근 연구자들은 이 'p-진수 세상'의 특이한 성질을 이용해 **새로운 암호 (공개키 암호 및 전자서명)**를 만들었습니다.

암호의 원리: "이 복잡한 p-진수 공간에서 '가장 긴 벡터'나 '가장 가까운 점'을 찾는 것은 매우 어렵다"는 점을 이용했습니다. 마치 미로에서 가장 긴 길을 찾거나, 특정 지점에 가장 가까운 숨겨진 보물을 찾는 것처럼요.
과거의 생각: "이 문제는 해결하기 너무 어려워서 암호로 쓰기에 안전하다"고 믿었습니다.

⚔️ 이 논문의 핵심: "정렬된 나침반"을 찾아내다

저자 (장치, 요밍첸) 는 이 암호가 사실은 약점이 있다고 발견했습니다. 그들은 p-진수 공간에서 **'직교 기저 (Orthogonal Basis)'**라는 특별한 도구를 찾아내는 초고속 알고리즘을 개발했습니다.

🧩 비유: 어지러운 책상 정리하기

상황: p-진수 공간은 마치 물건이 뒤죽박죽 섞여 있어 방향을 잡기 힘든 어지러운 방 같습니다. 여기서 '가장 긴 물건'이나 '가장 가까운 물건'을 찾으려면 모든 것을 뒤져야 해서 시간이 엄청 걸립니다.
해결책: 이 논문은 **"이 방을 정리하면 모든 물건이 서로 직각으로 배치되어, 가장 긴 것과 가장 가까운 것을 한눈에 볼 수 있다"**는 사실을 증명했습니다.
- 직교 기저 (Orthogonal Basis): 마치 방의 벽과 바닥, 천장이 완벽하게 수직으로 맞춰져 있어, 어떤 물건의 위치를 'x 축, y 축, z 축'으로만 딱딱 구분할 수 있게 해주는 정렬된 나침반입니다.
방법:
- 이 논문은 **'최대 순서 (Maximal Order)'**라는 수학적 구조와 **'p-근 (p-radical)'**이라는 도구를 이용해, 어떻게 하면 이 '정렬된 나침반'을 순식간에 (다항 시간 안에) 만들 수 있는지 보여줍니다.
- 마치 복잡한 미로를 한 번에 직선으로 뚫어주는 터널을 파는 것과 같습니다.

🛠️ 결과: 암호는 무너졌다

이 '정렬된 나침반'을 만들 수 있게 되면:

가장 긴 벡터 찾기 (LVP): 방에서 가장 긴 물건을 찾는 게 아니라, 나침반의 축을 따라 가장 긴 것만 보면 되므로 순간적으로 해결됩니다.
가장 가까운 벡터 찾기 (CVP): 목표 지점과 가장 가까운 물건을 찾는 것도 마찬가지로 순간적입니다.

결론: 이 논문의 알고리즘은 기존에 제안된 p-진수 기반 암호 체계가 사실상 안전하지 않다는 것을 증명했습니다. 암호를 만든 사람들이 "이 문제는 어렵다"고 생각했지만, 알고 보니 "이 문제를 쉽게 풀 수 있는 비법 (직교 기저)"이 존재했던 것입니다.

💡 미래: 어떻게 해야 할까?

이 논문의 마지막 장에서는 흥미로운 제안을 합니다.

문제: 만약 암호 설계자가 "수학적인 최소 다항식 (field definition)"을 공개하지 않고, 오직 **"거리 측정기 (Oracle)"**만 준다면 어떨까요?
제안: "거리 측정기"만으로는 '정렬된 나침반'을 찾을 수 없는 새로운 암호를 만들 수 있을지 연구해 보자고 합니다. 즉, 거리만 알려주고 방향은 숨기는 새로운 암호 체계를 고민해야 한다는 뜻입니다.

📝 한 줄 요약

"p-진수라는 이상한 세상에서 암호를 지키기 위해 '가장 긴/가까운 것 찾기' 게임을 만들었는데, 이 논문은 그 게임의 규칙을 바꿔서 '정리된 나침반'을 찾아내는 비법을 공개함으로써, 기존 암호가 쉽게 뚫릴 수 있음을 증명했습니다."

이 연구는 암호학의 새로운 지평을 열었으며, 양자 컴퓨터 시대에 대비한 더 안전한 암호를 설계하기 위한 중요한 경고이자 길잡이가 되었습니다.

논문 요약: p-진수 체 (p-adic Fields) 에서의 LVP 및 CVP 해결에 대한 고찰

저자: Chi Zhang, Mingqian Yao (중국 과학원 수학 및 시스템 과학 연구소)

1. 연구 배경 및 문제 제기

배경: 최근 p-진수 격자 (p-adic lattice) 를 기반으로 한 공개키 암호 체계와 서명 방식이 제안되었습니다 (Deng et al., 2021). 이러한 체계는 유클리드 공간의 격자 문제 (SVP, CVP) 를 p-진수 공간으로 확장한 **최장 벡터 문제 (LVP)**와 **가장 가까운 벡터 문제 (CVP)**의 난이도에 기반합니다.
문제점: 기존 연구에서는 LVP 와 CVP 가 어렵다고 가정되었으나, Zhang (2025) 은 완전히 분기된 (totally ramified) 필드에서 LVP 를 다항 시간으로 해결하는 알고리즘을 제안하며 기존 암호 체계의 보안이 취약할 수 있음을 보였습니다.
핵심 과제: 이전 연구들은 p-진수 체가 주어졌을 때 **최대 순서 (Maximal Order)**를 다항 시간으로 계산할 수 있다는 점 (Round 2/4 알고리즘 등) 과 p-진수 격자가 직교 기저 (Orthogonal Basis) 를 가질 수 있다는 사실을 충분히 활용하지 못했습니다. 본 논문은 이 두 가지를 결합하여 일반적인 p-진수 체에서 LVP 와 CVP 를 다항 시간으로 해결하는 알고리즘을 제시합니다.

2. 방법론 (Methodology)

논문의 핵심은 p-진수 체 $K$ 위에서 **직교 기저 (Orthogonal Basis)**를 효율적으로 구성하고, 이를 이용해 격자 문제를 단순화하는 것입니다.

최대 순서 (Maximal Order) 계산:
- 주어진 최소 다항식 (Minimal Polynomial) 을 통해 p-진수 체 $K = \mathbb{Q}_p(\theta)$ 를 정의합니다.
- p-근 (p-radical) 개념을 활용하여 초기 순서 $O = \mathbb{Z}_p[\theta]$ 에서 시작해 최대 순서 $O_K$ 를 반복적으로 확장합니다 (Theorem 3.3).
- $O/pO$에서의 p-근 계산과 사상 (Map) 의 커널 (Kernel) 계산을 통해 $O_K$ 의 기저를 다항 시간 내에 구합니다.
직교 기저 구성:
- 최대 순서 $O_K$ 의 p-근에서 **균일화자 (Uniformizer, $\pi$ )**를 찾습니다. 이는 p-진수 절댓값이 최대인 원소입니다.
- 잔류체 (Residue Field) $k = O_K/\pi O_K$ 의 기저 $\{s_1, \dots, s_f\}$ 를 구성합니다 ( $f$ 는 잔류 차수).
- Theorem 4.3에 따라, $\{s_i \pi^j \mid 1 \le i \le f, 0 \le j \le e-1\}$ (여기서 $e$ 는 분기 지수) 집합이 $K$ 의 직교 기저가 됨을 증명합니다. 이는 p-진수 노름의 비아르키메데스 성질 ( $|v+w|_p \le \max(|v|_p, |w|_p)$ ) 을 기반으로 합니다.
LVP 및 CVP 알고리즘:
- 구해진 직교 기저를 사용하여 격자 벡터를 표현하면, 노름 계산이 각 성분의 최대값으로 단순화됩니다.
- Algorithm 1 (LVP): 직교 기저를 이용해 격자 벡터들의 노름을 비교하고, 두 번째로 긴 벡터를 찾는 다항 시간 알고리즘을 제시합니다.
- Algorithm 2 (CVP): 목표 벡터 $t$ 에 대해 격자 내 가장 가까운 벡터를 찾는 알고리즘을 제시합니다. 이는 직교 기저를 통한 투사 (projection) 와 잔여체 연산을 통해 효율적으로 수행됩니다.

3. 주요 기여 (Key Contributions)

알고리즘적 혁신: p-진수 그람 - 슈미트 직교화 (Gram-Schmidt) 와 잔류체 계산을 통합하여, p-진수 체에서 LVP 와 CVP 를 해결하는 결정론적 다항 시간 알고리즘을 설계했습니다.
보안 취약성 규명: 필드가 최소 다항식으로 완전히 명시된 경우, 기존 p-진수 격자 기반 암호 체계 (Deng et al. [5]) 가 직교 기저를 통해 다항 시간 내에 공격받을 수 있음을 증명했습니다. 이는 해당 암호 체계의 보안 강도를 근본적으로 약화시킵니다.
노름의 특성화 (Characterization of Norms): $\mathbb{Q}_p$ 위의 벡터 공간에서 정의된 모든 노름은 특정 행렬과 양의 실수들을 통해 표현될 수 있음을 증명 (Theorem 7.1) 하여, 노름의 구조적 이해를 넓혔습니다.
구체적 예시: $Q_2(\sqrt{5})$ (실제로는 $X^3-3X^2+3X-5$ 의 근을 가지는 체) 에 대한 구체적인 예시를 통해 알고리즘의 실행 가능성을 검증했습니다.

4. 결과 (Results)

시간 복잡도: 제안된 알고리즘은 입력 격자의 차수 $n$ 과 소수 $p$ 의 로그 ( $\log p$ ) 에 대해 **다항 시간 (Polynomial Time)**으로 실행됩니다.
공격 성공: Zhang et al. [13] 이 제안한 "잔류 차수가 큰" 방법을 사용하여 패치하려는 시도가 있었으나, 필드가 알려져 있다면 최대 순서와 균일화자를 통해 여전히 직교 기저를 유도할 수 있어 근본적인 취약점이 해결되지 않음을 보였습니다.
예외 조건: 필드가 오직 최소 다항식이 아닌, 노름을 오라클 (Oracle) 로만 제공하는 경우 (직교 기저가 드러나지 않는 경우) 는 여전히 LVP/CVP 해결이 어렵다고 추정됩니다.

5. 의의 및 결론 (Significance)

암호학적 함의: 본 연구는 p-진수 격자 기반 암호 (Post-Quantum Cryptography 후보 중 하나) 가 필드가 명시된 환경에서는 안전하지 않을 수 있음을 시사합니다. 이는 해당 암호 체계의 설계 시 필드 표현 방식이나 노름 정의에 대한 재검토가 필요함을 의미합니다.
이론적 기여: 비아르키메데스 기하학 (Non-Archimedean Geometry) 에서 격자 문제의 계산적 복잡성에 대한 이해를 심화시켰으며, p-진수 체의 대수적 구조 (최대 순서, p-근, 잔류체) 와 계산 이론을 효과적으로 결합한 프레임워크를 제시했습니다.
향후 방향: 필드를 완전히 공개하지 않고 노름만 오라클로 제공하는 방식이나, 직교 기저를 찾기 어려운 노름 구조를 찾는 것이 향후 안전한 암호 체계 설계의 핵심 과제로 제시되었습니다.

핵심 결론: 이 논문은 p-진수 체에서 최대 순서와 직교 기저를 다항 시간으로 계산할 수 있음을 증명함으로써, 기존에 제안된 p-진수 격자 기반 암호 체계가 다항 시간 공격에 취약함을 보였습니다. 이는 p-진수 기반 암호학의 안전성 기준을 재정의하는 중요한 결과입니다.