○ 고려대학교 정보보호대학원 이창민 교수 연구팀의 논문이 암호학 분야 세계 최고 권위 국제학술대회인 CRYPTO 2026 발표 논문으로 선정됨. CRYPTO 2026은 2026년 8월 17일-20일 미국 산타바바라에서 개최될 예정이며, 국제암호학회 IACR이 주관함
- 논문제목: Asynchronous Lagrange-Based Threshold FHE with Smaller Modulus Overhead
- 저자 정보: 김원, 이창민(교신저자), 이정환, Alain Passelègue, Damien Stehlé
- 학회 홈페이지: https://crypto.iacr.org/2026/
○ CRYPTO(International Cryptology Conference)는 국제암호학회 IACR이 주관하는 암호학 분야 세계 최고 권위의 국제학술대회로, BK21 (인정 IF 4), 한국정보과학회 기준 최우수 학회로 분류됨
○ 이번에 선정된 논문은 정보보호대학원 김원, 이정환, 이창민 교수와 CryptoLab Inc. 소속 Alain Passelègue, Damien Stehlé가 함께 수행한 국제 공동연구 성과임. 논문은 Shamir Secret Sharing 기반 t-out-of-n Threshold Fully Homomorphic Encryption(ThFHE)을 비동기(asynchronous) 환경에서 재고찰하고, 분산 복호화 과정에서 발생하는 모듈러스 증가 문제를 개선하는 새로운 분석 및 최적화 기법을 제시함
○ 본 논문은 기존 Shamir Secret Sharing 기반 Threshold FHE에서 핵심 병목으로 지적되어 온 Lagrange reconstruction noise amplification 문제를 정밀 분석함. 기존 방식에서는 분산 복호화 과정에서 Lagrange 계수가 noise를 크게 증폭시켜, 복호화 정확성을 유지하기 위해 ciphertext modulus를 크게 설정해야 하는 문제가 있었음. 본 연구는 이러한 modulus overhead를 결정하는 수학적 조건을 correctness와 simulation-security 관점에서 엄밀히 도출하고, Lagrange 계수의 크기를 줄일 수 있는 interpolation point 선택 및 최적화 방법을 제안함. 분석 및 실험 결과, 제안 기법은 기존 parameterization 대비 분산 복호화에 필요한 추가 modulus bit를 크게 줄일 수 있음을 보임. 예를 들어 공유 파티 수 n = 512인 경우, 참여자 수 t = n/2에서는 기존 대비 약 33%의 modulus overhead 감소를 달성하고, t가 n에 가까운 t = 500인 경우에는 최대 90% 수준의 감소를 달성함
○ 이번 연구는 비동기 환경의 Threshold FHE에서 Shamir Secret Sharing의 실용성을 저해하던 modulus overhead 문제를 크게 완화했다는 점에서 학술적 의의가 큼. ciphertext modulus overhead가 암호문의 크기를 증가시키고 연산 효율성을 저해하는 등 치명적인 병목을 야기한다는 점에서, Threshold FHE의 실용성을 크게 향상시킨 연구로 평가됨. 또한 기존 분석의 한계를 보완하고, BFV, BGV, CKKS 등 다양한 RLWE 기반 FHE scheme에 적용 가능한 일반적 분석 틀을 제시함으로써, 향후 대규모 보안 계산 및 분산 키 관리 시스템에서 다양한 Threshold FHE 기법의 실용화 가능성을 높인 성과로 평가됨
○ 본 논문이 암호학 분야 세계 최고 권위 학회인 CRYPTO 2026에 채택된 것은 정보보호대학원의 동형암호 및 임계 암호 연구 역량이 국제적으로 인정받은 성과로 평가됨
○ 논문 초록: We study t-out-of-n threshold fully homomorphic encryption (ThFHE) based on Shamir secret sharing (SSS) in the asynchronous setting. A central bottleneck for SSS-based ThFHE is that Lagrange reconstruction during distributed decryption can amplify noise, forcing a substantially larger ciphertext modulus to maintain correctness.
In this work, we revisit SSS-based ThFHE and give a rigorous analysis of the correctness and simulation-security constraints that govern parameter choices. We then compare families of Lagrange interpolation points through the lens of these constraints.
Our main contribut ions are analytic bounds that closely track empirical behavior and significantly reduce the modulus overhead required for distributed decryption. For example, for n = 512, our analysis reduces this modulus overhead (in bits) by 30% for t = n/2 and by up to 90% for t close to n, compared to prior parameterizations.
