In this paper, we revisit the arithmetic structure of CKKS FHE scheme and introduce Grafting, a technique that decouples the scale factor from the modulus. This enables optimized RNS packing and flexible rescaling, while reducing public key sizes and execution time. Our latest experiments show 1.92× faster bootstrapping, 1.89× faster Bit-CKKS bootstrspping, and 62% smaller public keys.

This work is part of my doctoral dissertation.

이 논문에서는 CKKS FHE 스킴의 기초 산술 구조를 재설계하는 Grafting이라는 기법을 소개합니다. 이 기법은 스케일 팩터와 암호문 모듈러스를 분리해, RNS 패킹 최적화와 유연한 rescaling을 가능하게 하며, 공개 키 크기와 동형 연산 실행 시간까지도 줄여줍니다. 가장 최근 업데이트된 실험 결과에서, 부트스트래핑 속도는 1.92배 빨라졌고, Bit-CKKS의 이진 게이트 부트스트래핑은 1.89배 향상되었으며, 공개 키 크기는 62% 감소했습니다.

이 연구는 제 박사학위논문에도 수록되어 있습니다.

In this paper, we address the IND-CPA^D insecurity of exact FHE schemes, which was previously believed to apply only to approximate FHEs. We identify vulnerabilities arising from non-negligible incorrectness, where the probability of incorrect evaluation is not exponentially small. Our attacks efficiently recover secret keys from BFV/BGV, DM/CGGI, and the exact variant of CKKS, exposing vulnerabilities in current parameter choices.

This paper received the Grand prize at the Korean National Cryptography Contest in 2024.

이 논문은 Exact FHE 스킴들의 IND-CPA^D 안전성에 대해 다루며, 기존에는 Approximate FHE 스킴에만 적용된다고 여겨졌던 IND-CPA^D 공격을 Exact FHE 스킴에도 적용한 연구입니다. 우리는 스킴의 정확성, 특히 non-negligible한 부정확성이 안전성을 심각하게 위협한다는 점을 발견하였으며, 실제로 BFV/BGV, DM/CGGI, Exact CKKS 스킴에서 작은 파라미터들을 바탕으로, 비밀 키를 효율적으로 복구하는 공격을 구현하였습니다. 이러한 취약점은 실제 쓰이는 파라미터로도 자연스럽게 확장되며, 지수적으로 작은 부정확도를 보장하는 파라미터를 사용함으로써 해결될 수 있습니다.

이 논문은 2024년 한국국가암호공모전에서 대상을 수상하였습니다.

After 3 years of tremendous efforts—public evaluations, numerous improvements, and security validations—HAETAE and SMAUG-T were selected as the final winners of the KpqC Competition in January 2025. The competition aims to select Quantum-secure Digital Signatures and KEM candidates for Korean Standards, similar to NIST's PQC standardization process. These schemes will, in the near future, become part of the Korean Standard (KS). As a main contributor to both schemes, I am truly proud of the progress we've made.

지난 2021년 11월부터 시작된 한국양자내성암호 공모에서 약 3년 간의 공개적인 평가, 알고리즘 및 구현의 수정과 개선, 안전성 검증 등을 거쳐 2025년 1월, 제가 제출한 HAETAE와 SMAUG-T 알고리즘이 최종 우승자로 선정되었습니다. 이 공모는 NIST의 PQC 표준화 과정과 유사하게, 한국 양자내성암호 표준 제정을 위한 전자서명 (Digital Signatures) 및 키 캡슐화 메커니즘 (KEM) 후보를 선정하는 것을 목표로 진행되었으며, 선정된 스킴들은 한국 표준 (KS) 양자내성암호 알고리즘이 될 예정입니다.