대수적 공격에서 중요성이 커지는 산술화 지향(AO) 프리미티브 분석을 위해, 이 논문은 여러 변수를 동시에 제거할 수 있는 딕슨 결과식(Dixon resultant)을 효율적이고 유연한 도구로 재조명한다. 기존 그뢰브너 기저 방법은 순서 변경에 FGLM이 필요해 영차원 아이디얼을 요구하고, 실베스터 결과식은 한 번에 변수 하나만 제거할 수 있어 유연성이 떨어진다. 연구진은 격자경로 계수법으로 딕슨 행렬 크기의 개선된 상한을 도출하고 여러 행렬식 계산 모델에서 복잡도를 분석했으며, 결정 가능계에서는 딕슨 결과식이 그뢰브너 기저의 실용적 대안이 되고 특히 미결정계의 매개변수적 소거에 적합함을 보였다(과결정계는 그뢰브너 기저가 여전히 유리). 오픈소스 C 구현 DRSolve는 무작위 생성된 결정 가능계 실험에서 최신 그뢰브너 기저 솔버 Magma·msolve와 경쟁력이 있었고, 저변수·고차수 영역에서 특히 유리했다. Poseidon, Vision, XHash12 등 AO 프리미티브에 소거 전략 세 가지를 적용해 다수 사례에서 복잡도를 낮췄다.
- •여러 변수를 동시에 제거할 수 있는 딥슨 결과식을 암호분석에 재도입
- •격자경로 계수법으로 딥슨 행렬 크기의 개선된 상한을 도출
- •오픈소스 C 구현 DRSolve가 저변수/고차수 영역에서 Magma·msolve와 경쟁력 갖음
- •Poseidon·Vision·XHash12 등 AO 프리미티브에 적용해 복잡도 감소 입증
0단 자동
AI가 규칙대로 쓰고 그대로 게시했습니다. 사람이 따로 보지 않았습니다.
- 규칙 판
- 규칙 판 도입 이전 기사입니다.
- 남기는 것
- 규칙 판 · 모델 · 시각
- 판 기록
- 아직 없습니다.
Efficient Polynomial System Solving via Dixon Resultants: Applications to AO Primitives
본문 미리보기
Solving multivariate polynomial systems is a fundamental problem in cryptanalysis, with increasing relevance in algebraic attacks on arithmetization-oriented (AO) primitives. Current approaches include Gröbner bases and the Sylvester resultant. However, Gröbner basis methods typically rely on FGLM to change the order, which requires a zero-dimensional ideal, whereas the Sylvester resultant eliminates only one variable at a time, limiting its flexibility in multivariate elimination. We revisit
전체 내용이 궁금하다면?
원문을 직접 읽어보세요
이 글이 만들어진 과정
- 11:25AI 초안
