NIST의 포스트 양자 암호(post-quantum cryptography, PQC) 프로젝트에 제출된 다수의 안들 중, NewHope는 링 학습 부호 오류(Ring-Learning with errors, Ring-LWE) 문제에 기반한 유망한 키 캡슐화 메커니즘(key encapsulation mechanism, KEM)이다. NewHope는 Fujisaki-Okamoto 변환을 적용하여 IND-선택 평문 공격에 안전한 공개키 암호화를 IND-선택 암호문 공격에 안전한 KEM으로 만드는 방식이므로, 복호 실패율(decryption failure rate, DFR)을 정확히 계산해야 복호 실패를 악용하는 공격에 대한 내성을 보장할 수 있다. 그러나 NewHope의 현재 DFR에 대한 상계(upper bound, UB)는 압축 잡음, NewHope의 인코딩/디코딩의 영향, centered binomial distribution에 대한 근사 효과가 충분히 고려되지 않기 때문에 다소 느슨하다. 또한 NewHope는 Ring-LWE 기반 암호이므로, 오차 계수들 간의 오차 의존성이 존재하여 DFR의 정확한 계산이 어렵다. 본 논문에서는 제약 완화(constraint relaxation)와 연합 부정식(union bound)을 사용하여, 기존 UB보다 훨씬 더 타이트한 DFR에 대한 UB를 도출한다. 특히, 위에서 언급한 요인들이 모두 새로운 UB의 도출에 반영되며 centered binomial distribution은 근사되지 않는다. 오차 의존성 역시 고려되기 때문에, 새로운 UB는 기존 UB보다 실제 DFR에 훨씬 더 가깝다. 더 나아가, 새로운 UB는 Chernoff-Cramer bound를 사용하여 매개변수화함으로써 NewHope의 매개변수에 대해 새로운 UB의 계산을 용이하게 한다. 새로운 UB가 PQC의 DFR 요구 수준보다 훨씬 낮기 때문에, 이 DFR 여유분을 NewHope 개선에 활용할 수 있다. 그 결과, NewHope의 보안 수준과 대역폭 효율은 각각 7.2%와 5.9% 향상된다.

*본 초록은 AI를 통해 원문을 번역한 내용입니다. 정확한 내용은 하기 원문에서 확인해주세요.