중국과학기술대 연구진이 임의의 완전계수 격자에서 유클리드 최단벡터문제(SVP)를 2^(0.7314n+o(n)) 시간, 2^(n/2+o(n)) 공간에 푸는 새로운 무작위 고전 알고리즘을 제시했다. 이는 기존 ADRS(STOC 2015)의 2^(n+o(n)) 고전 상한을 개선했으며, 큐램 유무에 따라 각각 2^(0.9497n)과 2^(0.8345n)이던 기존 최량 양자 알고리즘 상한도 능가한다. 핵심 아이디어는 소수 지표를 갖는 무작위 슈퍼격자를 구성해 ADRS의 이산 가우스 샘플러를 적용한 뒤, 원래 격자에 속하는 가장 짧은 벡터를 걸러내는 방식이다. 이 결과는 격자 기반 암호의 안전성 파라미터 산정에 사용되는 SVP 난이도 추정치에 영향을 줄 수 있는 이론적 진전이다.
- •SVP를 2^(0.7314n+o(n)) 시간에 푸는 새 고전 알고리즘, 기존 2^(n+o(n)) 상한(ADRS, STOC 2015) 개선
- •큐램 유무 상관없이 기존 최량 양자 알고리즘 상한(각각 2^0.9497n, 2^0.8345n)도 능가
- •소수 지표의 무작위 슈퍼격자를 구성해 이산 가우스 샘플링 후 최단벡터를 걸러내는 방식
- •격자 기반 암호의 안전 파라미터 산정에 쓰이는 SVP 난이도 추정에 영향을 줄 수 있는 이론적 결과
0단 자동
AI가 규칙대로 쓰고 그대로 게시했습니다. 사람이 따로 보지 않았습니다.
- 규칙 판
- 규칙 판 도입 이전 기사입니다.
- 남기는 것
- 규칙 판 · 모델 · 시각
- 판 기록
- 아직 없습니다.
Solving the Shortest Vector Problem in $2^{0.7314n+o(n)}$ Time via Discrete Gaussian Sampling on Superlattices
- 1.정확한 SVP를 2^{0.7314n} 시간·2^{n/2} 공간에 푸는 고전 확률 알고리즘 제시
- 2.ADRS(STOC 2015)의 고전 2^n 한계를 크게 개선, QRAM 포함 최선 양자 알고리즘(2^{0.8345n})도 추월
- 3.소수 지수 슈퍼격자에 이산 가우시안 샘플러를 적용해 원래 격자의 최단벡터를 선별하는 방식
- 4.분석은 쌍대 격자와 Kabatiansky-Levenshtein 구충진 한계로 가우시안 질량을 통제
왜 중요한가?
고전 알고리즘이 최선의 양자 알고리즘을 앞지른 이례적 결과로, 격자 기반 PQC(ML-KEM 등)의 보안 수준 산정에 쓰이는 SVP 난이도 상수가 바뀌면 파라미터 재평가 논의로 이어질 수 있다.
본문 미리보기
We give a classical randomized algorithm for the exact Euclidean Shortest Vector Problem (SVP) on arbitrary full-rank lattices. It runs in $2^{0.7314n+o(n)}$ time and$2^{n/2+o(n)}$ space. More precisely, it returns a shortest vector with high probability and runs in $$ 2^{E_0n+o(n)} \quad\text{time and}\quad 2^{n/2+o(n)} \quad\text{space}, \qquad E_0=0.73133754\ldots . $$ This improves the $2^{n+o(n)}$ classical bound of Aggarwal, Dadush, Regev, and Stephens-Davidowitz (AD
전체 내용이 궁금하다면?
원문을 직접 읽어보세요
이 글이 만들어진 과정
- 10:58AI 초안
