International Association
for Cryptologic Research

CKKS is a homomorphic encryption (HE) scheme that supports approximate arithmetic over complex numbers. While it is widely used in privacy-preserving machine learning (PPML) protocols, the approximate nature of the scheme makes it challenging to formally define the security guarantees of those protocols. In particular, in a sender-receiver protocol, where the sender performs homomorphic evaluation using a private circuit, characterizing the sender's privacy remains an important open problem. Moreover, there are currently no known methods for handling malicious receivers due to the absence of a zero-knowledge argument of knowledge (ZKAoK) for the CKKS scheme. In this paper, we address these open challenges. First, we introduce a new security definition, called Differentially Private Homomorphic Evaluation (DPHE), to formalize sender privacy in CKKS-based protocols. Next, we present a general compilation method that transforms a plain CKKS protocol into a DPHE protocol. Finally, we construct a zero-knowledge argument of knowledge (ZKAoK) for CKKS to achieve the DPHE property in the presence of malicious receivers, and provide concrete benchmarks of our ZKAoK implementation. To the best of our knowledge, this is the first work to formally address security and privacy issues in CKKS-based protocols through the lens of differential privacy. We also remark that our ZKAoK is the first construction to ensure the well-formedness of CKKS public keys and ciphertexts.

Polynomial commitment is a crucial cryptographic primitive in constructing zkSNARKs. Most practical constructions to date are either vulnerable against quantum adversaries or lack homomorphic properties, which are essential for recursive proof composition and proof batching. Recently, lattice-based constructions have drawn attention for their potential to achieve all the desirable properties, though they often suffer from concrete inefficiency or rely on newly introduced assumptions requiring further cryptanalysis. In this paper, we propose a novel construction of a polynomial commitment scheme based on standard lattice-based assumptions. Our scheme achieves a square-root proof size and verification complexity, ensuring concrete efficiency in proof size, proof generation, and verification. Additionally, it features a transparent setup and publicly verifiability. When compared with Brakedown (CRYPTO 2023), a recent code-based construction, our scheme offers comparable performance across all metrics. Furthermore, its proof size is approximately 4.1 times smaller than SLAP (EUROCRYPT 2024), a recent lattice-based construction.

Lattice-based homomorphic encryption (HE) schemes are based on the noisy encryption technique, where plaintexts are masked with some random noise for security. Recent advanced HE schemes rely on a decomposition technique to manage the growth of noise, which involves a conversion of a ciphertext entry into a short vector followed by multiplication with an evaluation key. Prior to this work, the decomposition procedure turns out to be the most time-consuming part, as it requires discrete Fourier transforms (DFTs) over the base ring for efficient polynomial arithmetic. In this paper, an expensive decomposition operation over a large modulus is replaced with relatively cheap operations over a ring of integers with a small bound. Notably, the cost of DFTs is reduced from quadratic to linear with the level of a ciphertext without any extra noise growth. We demonstrate the implication of our approach by applying it to the key-switching procedure. Our experiments show that the new key-switching method achieves a speedup of 1.2--2.3 or 2.1--3.3 times over the previous method, when the dimension of a base ring is $2^{15}$ or $2^{16}$, respectively.

In the last decade, zero-knowledge proof of knowledge protocols have been extensively studied to achieve active security of various cryptographic protocols. However, the existing solutions simply seek zero-knowledge for both message and randomness, which is an overkill in many applications since protocols may remain secure even if some information about randomness is leaked to the adversary. We develop this idea to improve the state-of-the-art proof of knowledge protocols for RLWE-based public-key encryption and BDLOP commitment schemes. In a nutshell, we present new proof of knowledge protocols without using noise flooding or rejection sampling which are provably secure under a computational hardness assumption, called Hint-MLWE. We also show an efficient reduction from Hint-MLWE to the standard MLWE assumption. Our approach enjoys the best of two worlds because it has no computational overhead from repetition (abort) and achieves a polynomial overhead between the honest and proven languages. We prove this claim by demonstrating concrete parameters and compare with previous results. Finally, we explain how our idea can be further applied to other proof of knowledge providing advanced functionality.