International Association
for Cryptologic Research

Amortized bootstrapping offers a way to simultaneously refresh many ciphertexts of a fully homomorphic encryption scheme, at a total cost comparable to that of refreshing a single ciphertext. An amortization method for FHEW-style cryptosystems was first proposed by (Micciancio and Sorrell, ICALP 2018), who showed that the amortized cost of bootstrapping $n$ FHEW-style ciphertexts can be reduced from $\tilde O(n)$ basic cryptographic operations to just $\tilde O(n^{\epsilon})$, for any constant $\epsilon>0$. However, despite the promising asymptotic saving, the algorithm was rather inpractical due to a large constant (exponential in $1/\epsilon$) hidden in the asymptotic notation. In this work, we propose an alternative amortized boostrapping method with much smaller overhead, still achieving $O(n^\epsilon)$ asymptotic amortized cost, but with a hidden constant that is only linear in $1/\epsilon$, and with reduced noise growth. This is achieved following the general strategy of (Micciancio and Sorrell), but replacing their use of the Nussbaumer transform, with a much more practical Number Theoretic Transform, with multiplication by twiddle factors implemented using ring automorphisms. A key technical ingredient to do this is a new ``scheme switching'' technique proposed in this paper which may be of independent interest.

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.

Comparison of two numbers is one of the most frequently used operations, but it has been a challenging task to efficiently compute the comparison function in homomorphic encryption~(HE) which basically support addition and multiplication. Recently, Cheon et al.~(Asiacrypt~2019) introduced a new approximate representation of the comparison function with a rational function, and showed that this rational function can be evaluated by an iterative algorithm. Due to this iterative feature, their method achieves a logarithmic computational complexity compared to previous polynomial approximation methods; however, the computational complexity is still not optimal, and the algorithm is quite slow for large-bit inputs in HE implementation. In this work, we propose new comparison methods with \emph{optimal} asymptotic complexity based on \emph{composite polynomial} approximation. The main idea is to systematically design a constant-degree polynomial $f$ by identifying the \emph{core properties} to make a composite polynomial $f\circ f \circ \cdots \circ f$ get close to the sign function (equivalent to the comparison function) as the number of compositions increases. We additionally introduce an acceleration method applying a mixed polynomial composition $f\circ \cdots \circ f\circ g \circ \cdots \circ g$ for some other polynomial $g$ with different properties instead of $f\circ f \circ \cdots \circ f$. Utilizing the devised polynomials $f$ and $g$, our new comparison algorithms only require $\Theta(\log(1/\epsilon)) + \Theta(\log\alpha)$ computational complexity to obtain an approximate comparison result of $a,b\in[0,1]$ satisfying $|a-b|\ge \epsilon$ within $2^{-\alpha}$ error. The asymptotic optimality results in substantial performance enhancement: our comparison algorithm on $16$-bit encrypted integers for $\alpha = 16$ takes $1.22$ milliseconds in amortized running time based on an approximate HE scheme HEAAN, which is $18$ times faster than the previous work.

We propose a new method to compare numbers which are encrypted by Homomorphic Encryption (HE). Previously, comparison and min/max functions were evaluated using Boolean functions where input numbers are encrypted bit-wise. However, the bit-wise encryption methods require relatively expensive computations for basic arithmetic operations such as addition and multiplication.In this paper, we introduce iterative algorithms that approximately compute the min/max and comparison operations of several numbers which are encrypted word-wise. From the concrete error analyses, we show that our min/max and comparison algorithms have $$\varTheta (\alpha )$$ and $$\varTheta (\alpha \log \alpha )$$ computational complexity to obtain approximate values within an error rate $$2^{-\alpha }$$, while the previous minimax polynomial approximation method requires the exponential complexity $$\varTheta (2^{\alpha /2})$$ and $$\varTheta (\sqrt{\alpha }\cdot 2^{\alpha /2})$$, respectively. Our algorithms achieve (quasi-)optimality in terms of asymptotic computational complexity among polynomial approximations for min/max and comparison operations. The comparison algorithm is extended to several applications such as computing the top-k elements and counting numbers over the threshold in encrypted state.Our method enables word-wise HEs to enjoy comparable performance in practice with bit-wise HEs for comparison operations while showing much better performance on polynomial operations. Computing an approximate maximum value of any two $$\ell $$-bit integers encrypted by HEAAN, up to error $$2^{\ell -10}$$, takes only 1.14 ms in amortized running time, which is comparable to the result based on bit-wise HEs.