지난해 크립토(CRYPTO 2025)에서 발표된 SQIsign의 첫 완전한 안전성 증명은 최소 엔트로피에 대한 느슨한 경계 때문에 소수 특성 크기에서 제곱근 손실이 발생해, 보안강도 레벨 I 기준 2^64회의 서명 질의만으로도 증명이 무의미해지는 한계가 있었다. 이 짧은 논문은 SQIsign의 최소 엔트로피가 사실은 O(1/p)로 최적임을 보여, 완전한 λ비트 보안까지는 아니지만 기대 비트 보안의 3분의 2를 보존하는 개선된 결과를 제시한다. 저자들은 이 손실이 SQIsign의 영지식 시뮬레이션 과정에서 발생하는 정보이론적 손실에서 비롯된 것임을 밝히고, 현재 파라미터에서 완전한 λ비트 보안을 얻으려면 새로운 증명 기법이 필요하다고 지적한다.
- •SQIsign 첫 완전 안전성 증명(CRYPTO 2025)의 느슨한 최소엔트로피 경계로 인한 한계 지적
- •SQIsign의 최소 엔트로피가 실제로는 O(1/p)로 최적임을 증명
- •완전한 λ비트 보안은 아니지만 기대 비트 보안의 3분의 2를 보존
- •손실 원인이 영지식 시뮬레이션의 정보이론적 손실임을 규명, 새 증명 기법 필요성 제기
0단 자동
AI가 규칙대로 쓰고 그대로 게시했습니다. 사람이 따로 보지 않았습니다.
- 규칙 판
- 규칙 판 도입 이전 기사입니다.
- 남기는 것
- 규칙 판 · 모델 · 시각
- 판 기록
- 아직 없습니다.
A Note on the Security Proof of SQIsign
- 1.SQIsign의 기존 완전한 보안증명(CRYPTO 2025)이 느슨한 최소엔트로피 경계로 2^64회 질의 시 사실상 무의미해짐을 지적
- 2.SQIsign의 최소엔트로피가 사실 최적(O(1/p))임을 보이며 기대 비트보안의 3분의 2까지는 복구
- 3.완전한 λ비트 보안 증명에는 미달하며, 영지식 시뮬레이션 단계의 정보이론적 손실이 근본 원인임을 지목
왜 중요한가?
SQIsign은 NIST 후속 공모에 오른 유력한 격자 대안 서명 후보 중 하나로, 그 보안증명의 허점과 개선 여지가 드러난 것은 표준화 심사와 실제 파라미터 선택에 직접 영향을 준다.
언급 프로젝트
SQIsign의 보안 증명에 대한 이번 분석은 양자 내성 서명 알고리즘의 실제 보안 강도 평가에 중대한 영향을 미칩니다. 이는 국내에서 양자 내성 암호 시스템 도입을 고려할 때, 예상되는 보안 수준을 정확하게 파악하고 잠재적 취약점에 대비하는 데 필수적인 정보가 될 것입니다. 특히 국가 주요 인프라 및 금융 시스템의 보안 표준 수립에 있어 이러한 세밀한 검토가 중요합니다.
본문 미리보기
Aardal et al. (CRYPTO 2025) provided the first complete security proof of SQIsign; however, their reduction incurs a square-root loss in the prime characteristic due to the application of a loose bound on the min-entropy. For instance, at NIST security level I, an adversary making $2^{64}$ signing queries renders the security proof vacuous. In this note, we show that the min-entropy of SQIsign is optimal, namely $\mathcal{O}(1/p)$. Although this improvement does not yield full $\lambda$-bit secu
전체 내용이 궁금하다면?
원문을 직접 읽어보세요
이 글이 만들어진 과정
- 11:24AI 초안
