Yiming Gao, Xuyuan Han, Honggang Hu는 NIST 3라운드 격자 후보와 관련된 문제 계열에서 비밀 복구를 위한 증명 가능한 고전 준지수 알고리즘을 제시했다. 다만 현재 명시된 매개변수 설정의 구체적 보안성이 낮아진다는 점을 입증한 결과는 아니라고 논문은 명시한다.

논문 PDF는 Kyber/ML-KEM, FrodoKEM, SABER, NTRU LPRime, Dilithium/ML-DSA 계열을 다룬다. 다항식 크기의 모듈러스와 다중로그 크기의 계수 범위에서는 짧은 비밀 성분을 기대 시간 및 메모리 복잡도 $2^{(1/2+o(1))n/\ln\ln n}$으로 복구한다고 보고한다.

잡음이 있거나 반올림된 선형 관계에서는 좌표별 추측으로 만든 비교 벡터의 제곱 유클리드 노름에 정확한 간격이 생기는 점을 이용한다. 가우시안 표본 목록 하나로 다른 좌표를 모두 열거하지 않고 이진 탐색을 통해 각 비밀 좌표를 식별하는 방식이다. 논문은 소수 모듈러스와 2의 거듭제곱 모듈러스에서 구조화된 공개 연산자에 대한 새로운 기하학적 경계로 필요한 표본 보장을 세웠다. 이 구성은 Ducas, Engelberts, Loyer가 CRYPTO 2025에서 제시한 Wagner 방식의 가우시안 표본 추출과 Han, Gao, Hu의 2026년 저오차 결정형 LWE 알고리즘을 바탕으로 한다.

NTRU 유형의 몫 관계에는 아핀 슬라이스 탐색을 적용한다. 일부 좌표를 고정해 공개 격자의 슬라이스로 후보 쌍을 제한하고, 추정한 가우시안 질량을 바탕으로 다음 좌표를 선택한다. 명시된 모듈러스 범위에서는 Falcon 키 생성 품질 조건이 필요한 질량 경계를 제공하며, 알고리즘은 높은 확률로 동등한 서명 키를 시간과 메모리 복잡도 $2^{O(n/\ln\ln n)}$에 복구한다. 같은 탐색으로 순환형 NTRU-HPS/HRSS의 짧은 키 핵심부도 복구한다.

논문은 이 결과가 NIST 3라운드 격자 후보 7개와 관련된 문제 계열에 준지수 알고리즘을 제시한다고 결론짓는다. 연구진은 그럼에도 현재 지정된 매개변수 설정의 구체적 보안성 저하를 입증한 것은 아니라고 선을 긋는다.

논문은 2026년 10월 6일 접수됐고 10월 8일 수정됐다. 이전 버전도 공개돼 있으며, 짧은 URL과 CC BY 라이선스가 제공된다. 논문의 PDF와 공격 및 암호분석 분야 분류를 확인할 수 있다.

```

@misc{cryptoeprint:2026/2386,

author = {Yiming Gao and Xuyuan Han and Honggang Hu},

title = {Provable Subexponential Algorithms for {NIST} Third-Round Lattice Families},

howpublished = {Cryptology {ePrint} Archive, Paper 2026/2386},

year = {2026},

url = {https://eprint.iacr.org/2026/2386}

}

```