On the Hardness of some Vandermonde Knapsack problems

출처:IACR ePrint (암호학)

AI 인사이트

개발자

1.2의 거듭제곱 사이클로토믹 링에서 부분 반더몬드(PV) 냅색 문제에 대한 새로운 공격 제시
2.Das-Joux 공격과 결합해 기존 알려진 것보다 더 많은 비율의 키가 취약함을 입증
3.vSIS 커밋먼트 문제의 정수 변형으로도 공격을 확장, 특정 파라미터 영역에서 취약성 확인

왜 중요한가?

PV 냅색과 vSIS는 효율적인 격자 기반(포스트양자) 암호 구성의 핵심 가정인데, 이 연구는 특정 파라미터 선택이 실제로는 안전하지 않을 수 있음을 보여 프로토콜 설계자에게 파라미터 선택에 대한 즉각적 경고를 제공한다.

본문 미리보기

The Vandermonde Knapsack problem comprises a family of algebraic variants of the Knapsack problem. This includes the Partial Vandermonde $(\mathsf{PV})$ Knapsack problem (DCC’15, ACNS’14, ACISP’18, DCC’20, Indocrypt'25), the Vanishing $\mathsf{SIS}$ $(\mathsf{vSIS})$-based commitment problem (Crypto’23, PKC'25), and related assumptions. These problems have played an important role in enabling efficient lattice-based cryptographic constructions. Recently, two independent works by Boudgoust, Gach

전체 내용이 궁금하다면?

원문을 직접 읽어보세요

원문 보기