FrodoKEM: Learning with Errors 키 캡슐화

이 C 라이브러리는 잘 연구된 LWE(Learning with Errors) 문제 [1,3]를 기반으로 하는 IND-CCA 안전 키 캡슐화(KEM) 프로토콜인 FrodoKEM을 구현합니다. LWE 문제는 일반적이고 "대수적으로 구조화되지 않은" 격자에 대한 난해성 추측 문제와 밀접한 관련이 있습니다. 이 패키지에는 Python 참조 구현도 포함되어 있습니다. FrodoKEM은 양자 컴퓨터 공격에 대해 안전할 것으로 추측됩니다.

FrodoKEM은 두 가지 주요 변형으로 구성됩니다:

• 키 쌍의 재사용에 제한을 두지 않는 표준 변형(간단히 FrodoKEM이라고 함) - 즉, 단일 공개 키에 많은 수의 암호문이 암호화될 수 있는 애플리케이션에 적합합니다.
• 단일 공개 키에 많은 암호문이 암호화되지 않는 애플리케이션에 적합한 임시(ephemeral) 변형(eFrodoKEM이라고 함).

eFrodoKEM과 달리 표준 FrodoKEM은 비밀 및 오류 행렬 샘플링을 위한 시드를 생성할 때 확장된 시드를 사용하며, 캡슐화 및 역캡슐화의 해시 계산 중 하나에 추가 솔트(salt)를 포함합니다. 이러한 대응 조치는 표준 FrodoKEM을 일부 다중 암호문 공격으로부터 보호합니다. 이 두 변형에 대한 자세한 내용은 [3]을 참조하십시오.

구체적으로, 이 라이브러리는 공개 행렬 "A" 생성을 위해 AES128을 사용하는 다음 KEM 방식을 포함합니다:

• FrodoKEM-640-AES 및 eFrodoKEM-640-AES: AES128의 양자 후 보안 수준에 해당.
• FrodoKEM-976-AES 및 eFrodoKEM-976-AES: AES192의 양자 후 보안 수준에 해당.
• FrodoKEM-1344-AES 및 eFrodoKEM-1344-AES: AES256의 양자 후 보안 수준에 해당.

그리고 공개 행렬 "A" 생성을 위해 SHAKE128을 사용하는 다음 KEM 방식도 포함합니다:

• FrodoKEM-640-SHAKE 및 eFrodoKEM-640-SHAKE: AES128의 양자 후 보안 수준에 해당.
• FrodoKEM-976-SHAKE 및 eFrodoKEM-976-SHAKE: AES192의 양자 후 보안 수준에 해당.
• FrodoKEM-1344-SHAKE 및 eFrodoKEM-1344-SHAKE: AES256의 양자 후 보안 수준에 해당.

"eFrodoKEM" 라벨은 임시 변형에 해당합니다.

이 라이브러리는 실험 목적으로 FrodoKEM 팀과 Microsoft Research에 의해 개발되었습니다.

목차

• common 폴더: 난수 함수, AES 및 SHA-3 구현.
• eFrodoKEM 폴더: eFrodoKEM의 C 및 Python3 구현.
• estimates 폴더: [3]에 보고된 FrodoKEM의 암호분석 추정치.
• FrodoKEM 폴더: 표준 FrodoKEM의 C 및 Python3 구현.
• LICENSE: MIT 라이선스 파일.
• README.md: 이 readme 파일.

지원 플랫폼

FrodoKEM 라이브러리는 Windows, Linux 또는 macOS를 실행하는 x64, x86, ARM, PowerPC 및 s390x 프로세서를 포함한 광범위한 플랫폼에서 지원되며, 리틀엔디언 및 빅엔디언 형식을 모두 지원합니다. Microsoft Visual Studio, GNU GCC 및 clang으로 라이브러리를 테스트했습니다.

라이선스

이 소프트웨어는 MIT 라이선스에 따라 사용이 허가됩니다. 자세한 내용은 LICENSE 파일을 참조하십시오. Python3 구현은 Creative Commons Zero v1.0 Universal 라이선스에 따라 사용이 허가됩니다. 다른 라이선스로 허가된 일부 타사 모듈이 포함되어 있습니다. 특히:

• common/aes/aes_c.c: 퍼블릭 도메인
• common/aes/aes_ni.c: 퍼블릭 도메인
• common/sha3/fips202.c: 퍼블릭 도메인
• common/sha3/fips202x4.c: 퍼블릭 도메인
• common/sha3/keccak4x: 이 폴더의 모든 파일은 퍼블릭 도메인(CC0)이며, 다음을 제외합니다.
• common/sha3/keccak4x/brg_endian.h - Brian Gladman이 저작권을 보유하며 BSD 3-clause 라이선스가 적용됩니다.
• <FrodoKEM_variant>/tests/ds_benchmark.h: 퍼블릭 도메인
• <FrodoKEM_variant>/tests/PQCtestKAT_kem<#>.c: Lawrence E. Bassham이 저작권 보유
• <FrodoKEM_variant>/tests/PQCtestKAT_kem<#>_shake.c: Lawrence E. Bassham이 저작권 보유
• <FrodoKEM_variant>/tests/rng.c: Lawrence E. Bassham이 저작권 보유

참고문헌

[1] Erdem Alkim, Joppe W. Bos, Léo Ducas, Karen Easterbrook, Brian LaMacchia, Patrick Longa, Ilya Mironov, Michael Naehrig, Valeria Nikolaenko, Chris Peikert, Ananth Raghunathan, and Douglas Stebila, "FrodoKEM: Learning With Errors Key Encapsulation". NIST 양자 후 표준화 프로젝트 제출물, 2021-2023. FrodoKEM의 라운드 3 사양은 여기에서 확인할 수 있습니다.

[2] Joppe W. Bos, Craig Costello, Léo Ducas, Ilya Mironov, Michael Naehrig, Valeria Nikolaenko, Ananth Raghunathan, and Douglas Stebila, "Frodo: Take off the ring! Practical, quantum-secure key exchange from LWE". ACM CCS 2016, 2016. 사전 인쇄 버전은 여기에서 확인할 수 있습니다.

[3] Lewis Glabush, Patrick Longa, Michael Naehrig, Chris Peikert, Douglas Stebila, and Fernando Virdia, "FrodoKEM: A CCA-Secure Learning With Errors Key Encapsulation Mechanism". IACR Communications in Cryptology (게재 예정), 2025.

기여

이 프로젝트는 Microsoft 오픈 소스 행동 강령을 채택했습니다. 자세한 내용은 행동 강령 FAQ를 참조하거나 추가 질문이나 의견이 있으면 [email protected]으로 문의하십시오.