새로운 암호화 알고리즘의 스트레스 테스트: XJTLU 연구, Crypto 2026 채택

시안교통리버풀대학교(XJTLU)의 Jintai Ding 교수가 칭화대학교, Ethereum Foundation, 룩셈부르크 대학교 연구원들과 공동 저술한 논문이 2026 International Cryptology Conference (Crypto 2026)에 채택되었다. “Graeffe-Based Attacks on Poseidon and NTT Lower Bounds”라는 제목의 이 논문은 8월 19일 컨퍼런스에서 Ding 교수가 발표했다.

Crypto는 International Association for Cryptologic Research (IACR)에서 주최한다. Eurocrypt, Asiacrypt와 함께 암호학 분야의 3대 컨퍼런스 중 하나로 꼽히며, 전 세계 연구자들이 최첨단 연구 결과를 발표하는 주요 장이다.

Poseidon이란 무엇인가?

Poseidon은 영지식 증명(zero-knowledge proofs)과 같은 애플리케이션을 위해 구축된 새로운 해시 함수이다. 평이하게 설명하자면, 해시 함수는 데이터의 “디지털 지문”을 생성한다. 입력값의 아주 작은 부분만 바뀌어도 출력값이 완전히 달라진다. 모바일 결제, 온라인 뱅킹 및 많은 인증 시스템이 그 핵심을 이 기능에 의존한다. 영지식 증명은 한 당사자가 다른 당사자에게 기본 정보를 공개하지 않고도 어떤 진술이 사실임을 증명할 수 있게 해준다.

수년간 연구되고 배포된 SHA-2 및 SHA-3와 같은 성숙한 해시 함수와 달리, Poseidon은 비교적 신기술이어서 보안 경계에 대한 지속적인 분석과 검증이 필요하다. 암호학에서 연구자들은 일상적으로 알고리즘을 “공격”한다. 이것은 실제 사이버 침해를 의미하는 것이 아니라, 연구자들이 알고리즘이 깨질 수 있는 조건을 테스트하고 취약점을 조사하기 위해 수학적 방법을 설계하는 보안 분석의 한 형태이다.

이 과정은 단계적으로 강화되는 일련의 스트레스 테스트로 이해하는 것이 가장 좋다. 방법이 강력할수록 연구자들은 알고리즘이 무엇을 견뎌낼 수 있는지 더 정확하게 판단할 수 있으며, 보안 경계가 더 명확해진다.

약 8,000배 더 빠름

바로 이 지점에서 새로운 연구가 등장한다. 연구진은 다항식의 근을 찾는 고전적인 방법인 그레페 변환(Graeffe transform)을 Poseidon의 암호 분석에 도입하여 보안 분석의 효율성을 획기적으로 향상시켰다.

실험 결과에 따르면, 새로운 접근 방식은 이전 방식보다 계산당 최대 약 8,000배 더 빠르게 실행되며, 메모리 사용량은 약 22배 적다. 이를 바탕으로 연구진은 이전에 해결되지 않았던 여러 보안 챌린지 사례를 해결했으며, 솔버 코드를 GitHub에 오픈 소스로 공개했다.