Tight Post-Quantum Multi-Key Security of the FX Construction↗ (원문, 새 창)

FX 구성(FX construction)은 Kilian과 Rogaway가 DESX를 일반화해 제안한 블록암호용 키 길이 확장 기법으로, 양자 컴퓨팅 공격자에 대한 안전성을 높이는 데 쓰인다. 최근 Shiba와 Iwata는 2026년 ToSC 논문에서 n비트 블록과 κ비트 내부 키를 가진 FX가 양자 이상적 암호 모델에서 약 2^((n+κ-log₂μ)/3) 질의까지 안전함을 보였는데, 이 논문은 완전 적응형 공격자에 대해 이 한계를 μ(독립적으로 키가 설정된 인스턴스 수)와 무관하게 약 2^((n+κ)/3)으로 개선했다. 오프라인 사이먼 알고리즘 기반 공격이 단일 키 인스턴스를 공략해 이 한계와 지수적으로 일치함을 보여, FX를 깨는 데 필요한 질의 복잡도의 지수가 이 매개변수 영역에서 키 인스턴스 수와 무관함을 입증했다.

• FX 구성: Kilian·Rogaway가 DESX를 일반화해 제안한 블록암호 키 길이 확장 기법
• Shiba·Iwata(ToSC 2026)의 양자 이상적 암호 모델 안전성 한계를 완전 적응형 공격자 대상으로 개선
• 개선된 한계는 약 2^((n+κ)/3) 질의로, 독립 키 인스턴스 수 μ와 무관하게 성립
• 오프라인 사이먼 알고리즘 기반 공격이 단일 인스턴스에서 이 한계와 지수적으로 일치함을 확인