FHE is actively deployed, yet its IND-CPA(-D) security relies on the assumptions of its security game, hard to satisfy in practice. Reaction attacks, where an adversary only sees whether the client accepts the decryption, exploit this gap in exact schemes like TFHE and BGV. We extend and enhance this attack to CKKS, recovering the secret key with nearly information-theoretically optimal queries. Secure deployment, not only for CKKS but for all FHE schemes, must thus enforce these assumptions, e.g., by blocking reaction leakage or using verifiable FHE.

최근 들어 동형암호의 상용화가 활발히 진행되고 있으나, IND-CPA(-D) 안전성은 안전성 모델의 가정이 지켜질 때만 보장되므로 실제로 이를 만족하기는 까다롭습니다. 복호화 결과에 대한 클라이언트의 수용 여부만 관찰하는 reaction attacks은 TFHE나 BGV 같은 exact 동형암호에서 이 간극을 파고들어 왔습니다. 본 연구는 이 어택을 CKKS로 확장 및 개선하여, 정보 이론적 최적치에 가까운 쿼리 수만으로 비밀키를 복구할 수 있음을 보입니다. 따라서 CKKS 뿐만아리아 모든 동형암호 스킴을 안전하게 상용화하려면 사용자의 반응 누출을 차단하거나 Verifiable FHE를 도입하는 등 안전성 모델의 가정을 준수하여야 합니다.

Extending our IND-CPA-D attacks from ACM CCS 2024, we present three new attacks on BFV and BGV. The first extends the bootstrapping failure attacks on DM/CGGI and CKKS to BGV/BFV, over the non-power-of-two cyclotomic rings used in HElib. The second and third are the first to exploit the heuristic nature of noise analysis: the O(√N)-type savings commonly used to set parameters assume random-like, independent inputs, which no longer holds when the adversary chooses what to compute. By crafting plaintexts for BFV plaintext-ciphertext multiplications, the second attack recovers the secret key in OpenFHE within minutes to a few hours; the third skews the ciphertext mask in ciphertext-ciphertext multiplications to break IND-CPA-D.

이 논문에서는 ACM CCS 2024에서 발표한 IND-CPA-D 어택을 확장하여, BFV와 BGV 동형암호 스킴에 대한 세 개의 새로운 어택을 제시합니다. 첫 번째 어택은 DM/CGGI와 CKKS에 대한 부트스트래핑 실패 어택을 HElib이 사용하는 non-power-of-two 다항식 환 위에서의 BGV/BFV 어택으로 확장합니다. 두 번째와 세 번째 어택은 처음으로 휴리스틱 노이즈 분석을 공략합니다: 동형암호 파라미터 설정에 널리 쓰이는 O(√N) 수준의 노이즈 절감은 입력이 랜덤하고 서로 독립이라는 가정 하에서 사용되어야 하지만, 공격자가 연산 회로를 고를 수 있는 IND-CPA-D 환경에서는 이 가정이 성립하지 않습니다. 두 번째 어택은 BFV 평문-암호문 곱셈에 맞춤 제작한 평문을 사용해 OpenFHE에서 수 분에서 수 시간 만에 비밀키를 완벽하게 복구하고, 세 번째 어택은 암호문-암호문 곱셈에서 암호문의 mask를 한쪽으로 치우치게 만들어 IND-CPA-D 안전성을 깨뜨립니다.

In this paper, we present a novel and efficient high-precision CKKS bootstrapping method. We introduce an Integer Cleaning technique based on Discrete-CKKS, along with a Thrifty approach for digit-cleaning. By incorporating these techniques into the EvalRound+ framework, we achieve effective high-precision bootstrapping. Our Grafting-based implementation demonstrates a 1.6× improvement in 80-bit precision CKKS bootstrapping.

이 논문에서는 효율적인 고정밀 CKKS 부트스트래핑을 새롭게 제안합니다. 우리는 Discrete-CKKS 기반의 동형 Integer Cleaning 기법과 효율적인 digit 클리닝 기법인 Thrifty Approach를 도입하여, 정수 노이즈를 효과적으로 제거하고 모듈러스와 성능 효율성을 동시에 달성합니다. 이들 기법을 EvalRound+ 프레임워크에 적용하여 매우 효과적인 부트스트래핑을 제안하며, Grafting 기반의 구현으로 80비트 정밀도의 CKKS 부트스트래핑에서 약 1.6배 성능 향상을 입증하였습니다.

In this paper, we revisit the arithmetic structure of the CKKS FHE scheme and introduce Grafting, a technique that decouples the scale factor from the modulus. This enables optimized RNS packing and more flexible rescaling, while also reducing public key sizes and execution time. Our experimental results demonstrate 1.92× faster bootstrapping, 1.89× faster Bit-CKKS bootstrapping, and a 62% reduction in public key size.

이 논문에서는 CKKS FHE 스킴의 산술 구조를 재설계하여, 스케일 팩터와 모듈러스 간의 의존성을 분리하는 Grafting 기법을 소개합니다. 이 기법은 최적화된 RNS 패킹과 보다 유연한 리스케일링을 가능하게 하며, 공개키 크기를 줄이고, 동형 연산을 가속화합니다. 구현을 통해 확인한 결과, 제안한 방법은 부트스트래핑에서 1.92배, Bit-CKKS 부트스트래핑에서 1.89배 더 빠른 성능을 달성하였으며, 공개키 크기를 62% 감소시켰습니다.

This work is partly included in my PhD dissertation. It also receives the Excellence Award at 2025 Korean National Cryptography Contest.

이 연구는 제 박사학위논문에도 수록되어 있으며, 2025년 한국국가암호공모전에서 최우수상을 수상할 예정입니다.

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.

이 논문에서는 이전까지 Approximate FHE 스킴에만 해당되는 것으로 여겨졌던 IND-CPA^D 안전성에 대한 어택을 Exact FHE 스킴에 확장 적용하여 그 취약성을 입증하였습니다. 우리는 스킴의 정확성, 특히 non-negligible한 부정확성이 안전성을 심각하게 위협한다는 점을 발견하였으며, BFV/BGV, DM/CGGI, Exact CKKS 스킴의 비밀 키를 효율적으로 복구할 수 있었습니다. 이러한 취약점은 지수함수적으로 작은 부정확성를 보장하는 파라미터를 사용함으로써 해결될 수 있습니다.

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

이 논문은 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. 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) 알고리즘을 선정하는 것을 목표로 진행되었습니다.

The selected schemes will, in the near future, become part of the Korean Standard (KS).

선정된 스킴들은 한국 표준 (KS) 양자내성암호 알고리즘이 될 예정입니다.