Learning with Quantization and Worst Case Lattice Problems↗ (원문, 새 창)

이 논문은 MAMBA 제안에서 동기를 얻어, 공개 디더(dither)를 사용하는 '양자화를 통한 학습(Learning with Quantization, LWQ)'의 최악 경우 난이도를 연구한다. Lyu 등의 무작위화된 극좌표 격자 양자화기를 이용해 2의 거듭제곱 모듈러스를 갖는 명시적 패밀리를 구성했고, 탐색 버전에서는 균일하게 선택된 비밀을 역다항식 확률로 복원하는 알고리즘이 임의 n차원 격자의 GapSVP와 SIVP를 근사비 O(n log n), O(n(log n)²)로 양자 다항시간에 푸는 알고리즘을 유도함을 보였다. 더 강한 매개변수 조건 하에서는 결정 환원도 가능해 근사비 O(n(log n)³), O(n(log n)⁴)에 대응하는 결과를 얻었다. 다만 MAMBA Frost에서 쓰이는 구간 균일 오차를 갖는 LWE로의 확장은 결정론적 양자화 경계로 인한 장애물이 있어 완전한 환원에는 이르지 못했다.

• MAMBA 제안에서 쓰이는 공개 디더 기반 양자화 학습(LWQ)의 최악 경우 난이도 분석
• Lyu 등의 무작위 극좌표 격자 양자화기로 2의 거듭제곱 모듈러스 명시적 패밀리 구성
• 탐색 문제 복원 알고리즘이 GapSVP·SIVP를 근사비 O(n log n), O(n(log n)²)로 양자 다항시간에 해결함을 입증
• 더 강한 조건에서는 결정 환원도 가능, MAMBA Frost의 구간 균일 오차 LWE로의 확장은 완전한 환원에 이르지 못함