이 논문은 확장체(extension field) 위에서 정의된 순열코드 등가문제(PEP)와 순열 커널 문제(PKP)의 안전성을 분석해, 후속양자 서명 스킴 PERK와 SETH가 채택한 확장체 인스턴스화의 취약점을 밝혀냈다. 이진 확장체에서는 정규 신드롬 복호화 문제(RSD)로의 환원을 통해 PKP와 PEP 모두에서 새로운 다항시간 풀이 가능 파라미터 영역을 발견했으며, 이는 자기직교·자기쌍대 PEP 인스턴스를 포함한다. 또한 홀수 표수(odd characteristic) 확장체 위의 광범위한 PEP 인스턴스를 그래프 동형사상 문제로 환원해 다항시간 알고리즘을 제시했다. 이 결과는 대부분의 시나리오에서 확장체 위 PEP 사용이 안전하지 않음을 보여, 관련 후속양자 서명 설계에 재검토가 필요함을 시사한다.
- •확장체 위 PKP/PEP를 분석해 후속양자 서명 PERK, SETH의 안전성 문제 지적
- •이진 확장체에서 RSD 환원으로 새로운 다항시간 풀이 파라미터 영역 발견
- •차수 ν>4 확장체의 모든 자기쌍대 PEP 인스턴스가 다항시간에 풀림
- •홀수 표수 확장체의 PEP를 그래프 동형사상 문제로 환원, 다항시간 알고리즘 제시
0단 자동
AI가 규칙대로 쓰고 그대로 게시했습니다. 사람이 따로 보지 않았습니다.
- 규칙 판
- 규칙 판 도입 이전 기사입니다.
- 남기는 것
- 규칙 판 · 모델 · 시각
- 판 기록
- 아직 없습니다.
A Descent to Hades: Attacks on PKP and PEP over Extension Fields
- 1.PERK·SETH 등 포스트양자 서명에 쓰이는 PKP·PEP 문제를 확장체(extension field)에서 분석
- 2.이진 확장체에서 두 문제 모두 다항시간에 풀리는 파라미터 영역을 새롭게 발견
- 3.홀수 특성 확장체의 PEP 다수 사례를 그래프 동형 문제로 환원, 다항시간 알고리즘 제시
- 4.결과적으로 대부분 시나리오에서 확장체 기반 PEP 사용이 안전하지 않음을 입증
왜 중요한가?
PERK·SETH 같은 실제 포스트양자 서명 후보의 파라미터 선택에 직접 영향을 미치는 취약점으로, 확장체를 이용한 효율화 시도가 보안성과 상충될 수 있음을 보여준다.
본문 미리보기
The Permutation Code Equivalence Problem (PEP) and Permuted Kernel Problem (PKP) are two notorious computational problems over linear codes used for building post-quantum digital signature schemes. Although traditionally analyzed over prime fields, recent proposals, such as the signature schemes PERK and SETH, have considered extension fields to improve efficiency and compactness. In this work, we analyze the hardness of solving PKP and PEP when instantiated over field extensions. For binary
전체 내용이 궁금하다면?
원문을 직접 읽어보세요
이 글이 만들어진 과정
- 11:05AI 초안
