Reaction Attack on CKKS Deployments with Asymptotically Optimal Query Complexity

The gist The attack recovers ternary secrets in query complexity that tightly matches theoretical lower bounds for CKKS deployments exposing decoded-slot validity responses and C2S rotation keys.

Reaction Attack on CKKS Deployments with Asymptotically Optimal Query Complexity

The paper studies a protocol-level reaction leakage in CKKS deployments where public coefficient-to-slot (C2S) evaluation keys are combined with a client’s 1-bit validity response, showing that a malicious evaluator can recover a ternary secret key using asymptotically optimal O(H) reaction queries, where H is the entropy of the secret key The attack does not break RLWE or CKKS IND-CPA security instead it exploits the interaction between client-side validity reactions and public homomorphic linear transformations A shift of a public encryption key yields a ciphertext whose plaintext is a function of the secret key; the public C2S layer then repacks this information to construct a ciphertext whose validity depends strictly on whether a targeted secret coefficient matches a guessed value Furthermore, each submitted query is independently randomized with a fresh encryption of zero, so that each resulting malicious ciphertext appears entirely distinct, thereby allowing the attack to simply evade trivial detection mechanisms on the client side

Reaction Attack Mechanism

The core of the attack involves transforming a single-bit validity reaction into a one-bit decryption oracle This oracle reveals strictly whether a submitted ciphertext satisfies the client’s validity predicate, which is observable to the malicious server S The paper illustrates this by showing that if a guess for the secret key element matches, the modified ciphertext stays within the admissible range, while an incorrect guess causes it to exceed the threshold with high probability The attack links each oracle query to a single coefficient of s at a time using pk and rotation keys for C2S

Query Complexity and Optimality

The paper demonstrates that a single-bit validity reaction suffices to recover a CKKS secret key without reusing a fixed target ciphertext The query complexity is asymptotically optimal, achieving O(H log(N/h)) for sparse secrets, which is within a factor of 2/log2 3 < 2 of the oracle-only entropy lower bound For uniform ternary secrets, the attack uses O(N) queries and is within a factor 2/ log2 3 < 2 of the oracle-only entropy lower bound Specifically, for sparse ternary secrets with h non-zero coefficients, a tailored variant further reduces the number of queries in practice

Attack Phases

The attack proceeds in two main phases to recover the secret key s

1. Offline Step (Offline Step) The adversary first performs two public operations that are independent of the oracle queries, starting from pk = (a, b = as + e), it forms ct(1):= (a − ∆, b), which decrypts to ∆s + e under the target key The adversary then applies the public normalized C2S to obtain (ct(2)R, ct(2)I)

2. Online Step (Online Step) The online step is divided into two types of queries: (i) Support queries, which are employed to identify the support set S:= S = the set of indices where sj!= 0, and (ii) Sign queries, which are used to determine the sign associated with each index in S The full secret s is then recovered through these adaptive query sequences

Sparse Secret Optimization

For sparse ternary secrets with Hamming weight h, the attack can be further optimized using a combinatorial Group Testing strategy This strategy allows the identification of all h non-zero coordinates using only O(h log2(N/h)) queries Once the support S is fully recovered, the signs can be extracted directly from the public key without any further oracle queries The sign recovery phase then involves solving a reduced h-dimensional LWE instance via standard lattice reduction algorithms (e.g., LLL)

Countermeasures

The most practical mitigation is to standardize the externally visible response and monitor reactions per key Standardizing the externally visible response removes the reaction signal entirely by returning a consistent protocol response regardless of the admissibility check Bounding and monitoring reactions is a complementary defense where an elevated per-key rejection rate provides a natural aggregate detection vector Other strategies like noise and parameter modifications are deemed impractical because violating the slotmargin condition risks rejecting honest evaluations, and changing rings degrades performance Cryptographic integrity mechanisms like verifiable FHE provide a principled defense but introduce substantial efficiency penalties

Conclusion

The paper concludes that vulnerabilities can emerge strictly at the protocol level, without refuting RLWE or IND-CPA security The most practical defense is to standardize the client’s externally visible response and monitor reactions per key The elevated query volume and rejection rate our attack induces further offer a natural detection vector through aggregate failure-rate analysis

Open Questions

The paper highlights four directions for future work, including formalizing detector models to determine which aggregate heuristics provably prevent key recovery, closing theoretical gaps between the theoretical bound and experimental average for sparse secrets, investigating whether similar reaction attacks threaten other widely deployed RLWE schemes like BGV and BFV, and designing output-validation mechanisms that support legitimate retries without leaking externally exploitable accept/reject bits.

Acknowledgments

Jiseung Kim is supported by the National Research Foundation of Korea (NRF) grant funded by the Korean government (MSIT) (No. RS-2026-25477662), and the Institute of Information & Communications Technology Planning & Evaluation (IITP) grant funded by the Korea government(MSIT) (No. RS-2024-00399491, Development of Privacy-Preserving Multiparty Computation Techniques for Secure Multiparty Data Integration) Changmin Lee is supported by the Korea Internet & Security Agency (KISA) grant funded by the Korean government (PIPC) (No. 2780000036, Masters and Doctoral Program for Advanced Talent Development in Personal Data Protection and Responsible Use) and by Korea University grant K2603241 Song Bian is supported by the National Natural Science Foundation of China (62572020)

References

[1] A. Al Badawi, J. Bates, F. Bergamaschi, D. B. Cousins, S. Erabelli, N. Genise, S. Halevi, H. Hunt, A. Kim, Y. Lee et al., “OpenFHE: Open-source fully homomorphic encryption library,” in Proceedings of the 10th Workshop on Encrypted Computing & Applied Homomorphic Cryptography, 2022, pp. 53–63

[2] M. R. Albrecht, R. Player, and S. Scott, “On the concrete hardness of Learning with Errors,” Journal of Mathematical Cryptology, vol. 9, no. 3, pp. 169–203, 2015

[3] W. Ao and V. N. Boddeti, “AutoFHE: Automated adaption of CNNs for efficient evaluation over FHE,” in 33rd USENIX Security Symposium (USENIX Security 24), 2024, pp. 2173–2190

[4] S. Atapoor, K. Baghery, H. V. L. Pereira, and J. Spiessens, “Verifiable FHE via lattice-based SNARKs,” IACR Communications in Cryptology, 2024

[5] F. Aydin, E. Karabulut, S. Potluri, E. Alkim, and A. Aysu, “RevEAL: Single-trace side-channel leakage of the SEAL homomorphic encryption library,” in 2022 Design, Automation & Test in Europe Conference & Exhibition (DATE). IEEE, 2022, pp. 1527–1532

[6] Y. Bae, J. H. Cheon, G. Hanrot et al., “Fast homomorphic linear algebra with blas,” Journal of Cryptology, vol. 39, no. 25, 2026

[7] F. Bergamaschi, A. Costache, D. Dachman-Soled, H. Kippen, L. LaBuff, and R. Tang, “Revisiting the security of approximate FHE with noise-flooding countermeasures,” in Public-Key Cryptography – PKC 2025. Springer, 2025

[8] D.

1. A malicious evaluator can recover a ternary secret key using asymptotically optimal O(H) reaction queries by exploiting the interaction between client-side validity reactions and public homomorphic linear transformations. This implies that AI systems deployed in outsourcing scenarios, which rely on client-side admissibility checks after FHE evaluation, must adopt defenses that eliminate the one-bit decryption oracle.

2. Implement standardized external protocol responses to remove the reaction signal entirely by return[ing] the same protocol response regardless of the admissibility check, thereby eliminating the one-bit oracle while changing only outward behavior, not the FHE computation. This prevents adversaries from gaining information through observable client reactions.

3. Enforce per-key reaction monitoring and setting a sufficiently small cap on queries to ensure that the projected LWE instance remains solvable by lattice reduction. This defense is justified because a sufficiently small cap will leave enough room for security against key recovery attacks, even if the attack is detectable through an elevated per-key rejection rate and query volume.

4. Utilize specialized group testing strategies to recover sparse secret coefficients with a complexity of O(h log2(N/h)) reaction queries, significantly reducing the query count compared to the baseline N + S approach. This allows AI systems using sparse ternary secrets to maintain high performance while still being vulnerable only for a controlled, predictable number of oracle queries.