격자 암호 체계의 보안 증명과 환원

암호 방식의 보안 증명은 해당 방식을 깨는 것이 어떤 기저 난제의 해결을 의미한다는 점을 보이는 형식적인 수학적 논증입니다. 이 증명이 절대적인 보안을 보장하는 것은 아닙니다. 대신 방식에 대한 효율적인 공격자를 기저 난제를 해결하는 효율적인 알고리즘으로 변환할 수 있음을 보입니다. 기저 난제를 실행 불가능한 문제로 간주한다면 해당 방식은 안전합니다.

Regev의 2005년 획기적인 증명은 판정 LWE를 해결하는 다항 시간 알고리즘을 사용하여 n차원 격자에서 최악 경우의 GapSVP(Gap Shortest Vector Problem)를 해결할 수 있음을 보입니다. 이 환원은 양자 환원으로, 양자 표본 추출 절차를 사용하여 LWE 해결 알고리즘을 격자 해결 알고리즘으로 변환합니다. 이는 양자 계산을 가정할 때 LWE가 최악 경우의 격자 문제만큼은 어렵다는 뜻입니다.

Regev의 환원은 긴밀하지 않습니다. 환원에 포함된 다항식 인자 때문에 증명이 보장하는 보안 수준은 알려진 최선의 공격이 시사하는 수준보다 다소 낮습니다. 실제 매개변수를 선택할 때 암호학자들은 환원이 보수적이므로 이론적 환원 한계보다 격자 추정기를 통해 알려진 최선의 공격이 제공하는 구체적 보안을 사용합니다.

LWE 기반 암호화 방식은 혼성 논증을 통해 IND-CPA(선택 평문 공격에 대한 구별 불가능성)를 만족한다고 증명됩니다. 이 증명은 IND-CPA 구별기가 존재하면 LWE 구별기를 만들 수 있음을 보입니다. 첫 번째 혼성 단계에서는 실제 암호문을 균등 무작위 문자열로 바꿉니다. LWE 가정에 따라 두 암호문을 구별할 수 없으므로, 기본적인 격자 암호화를 위한 깔끔한 보안 증명이 성립합니다.

TLS에서 사용하는 키 캡슐화 메커니즘에는 IND-CPA 보안만으로는 충분하지 않으며, IND-CCA2(선택 암호문 공격) 보안이 필요합니다. Fujisaki-Okamoto(FO) 변환은 임의의 IND-CPA 방식을 Random Oracle Model(ROM)에서 IND-CCA2 KEM으로 변환합니다. ML-KEM은 기저 모듈 LWE 암호화에 FO 변환의 변형을 적용하여 실제 배포에 필요한 CCA2 보안을 제공합니다.

Random Oracle Model(ROM)은 해시 함수를 진정한 무작위 함수로 모델링합니다. FO 변환에 대한 증명을 비롯한 많은 보안 증명은 ROM을 필요로 합니다. 실제로 SHA-3와 같은 해시 함수는 진정한 무작위 오라클이 아니므로, ROM 증명만으로는 표준 모델에서의 보안을 보장할 수 없습니다. 그럼에도 ROM 증명은 암호학계에서 강력한 보안 근거로 널리 받아들여지고 있습니다.

표준 모델 증명은 해시 함수에 대해 어떠한 이상화도 가정하지 않으므로 ROM 증명보다 엄밀하게 강력합니다. 대부분의 실용적인 격자 방식은 ROM 증명을 사용합니다. 격자 기반 KEM에 대한 표준 모델의 CCA2 증명은 훨씬 복잡하고 구체적인 매개변수도 더 나쁘기 때문입니다. NIST는 ML-KEM에 대한 ROM 기반 증명을 목표로 하는 보안 수준에 충분한 것으로 판단하여 받아들였습니다.

ML-KEM의 보안 증명은 두 단계로 진행됩니다. 먼저 기저 모듈 LWE 암호화가 M-LWE 가정에 따라 IND-CPA 보안을 만족함을 보입니다. 다음으로 Fujisaki-Okamoto 변환, 구체적으로는 Kyber에서 사용되는 T 변환과 U 변환을 적용하여 이를 양자 ROM(QROM)에서 IND-CCA2 보안으로 강화합니다. QROM은 공격자가 무작위 오라클에 중첩 상태로 질의하는 경우까지 처리합니다.

Albrecht, Player, Scott가 개발한 격자 추정기는 LWE 기반 방식의 구체적 보안을 계산하는 표준 도구입니다. 이 도구는 알려진 최선의 격자 공격(BKZ와 체질 또는 열거)의 비용을 모델링하고, 주어진 매개변수(n, q, sigma)에 대한 예상 비트 보안을 출력합니다. 새로운 알고리즘과 하드웨어 비용 모델이 발표될 때마다 정기적으로 업데이트됩니다.

Block Korkine-Zolotarev(BKZ) 알고리즘은 현재 가장 실용적인 격자 축소 알고리즘입니다. 블록 크기가 beta인 BKZ는 최선의 체질 알고리즘을 사용할 때 대략 2^{0.292*beta} 게이트 연산의 복잡도로 짧은 벡터를 찾습니다. ML-KEM-768의 경우 예상 고전 보안은 약 180비트이고 양자 보안은 약 164비트로, 목표로 하는 192비트보다 충분히 높습니다.

점근적 보안 증명은 충분히 큰 매개변수에 대해 방식이 안전하다는 점을 보이지만, 실제로 "충분히 크다"는 것이 어느 정도인지는 구체적으로 제시하지 않습니다. 구체적 보안 분석은 선택한 매개변수에 대한 최선의 공격에 실제로 필요한 비용을 추정하여 이 간극을 메웁니다. 양자 내성 표준화는 구체적 보안 분석에 크게 의존하며, 향후 30년 동안 예상되는 양자 하드웨어의 공격을 견딜 수 있도록 매개변수를 선택합니다.

ML-KEM에서 격자 암호화의 IND-CPA 보안을 IND-CCA2 보안으로 강화하는 데 사용하는 변환은 무엇입니까?

격자 방식의 보안 증명은 해당 방식의 보안을 LWE 또는 SVP의 난이도로 환원합니다. Regev의 환원은 LWE가 최악 경우의 격자 문제만큼은 어렵다는 점을 보장합니다. Fujisaki-Okamoto 변환은 ROM에서 IND-CPA 보안을 IND-CCA2 보안으로 강화합니다. 구체적 보안은 BKZ 복잡도 모델을 사용하는 격자 추정기로 평가합니다. 환원의 긴밀성에 간극이 있으므로, 실제 매개변수는 환원 한계만이 아니라 공격 비용 추정에 의존합니다.