## CryptoDB

### Jung Hee Cheon

#### Publications

**Year**

**Venue**

**Title**

2022

EUROCRYPT

Limits of Polynomial Packings for $\mathbb{Z}_{p^k}$ and $\mathbb{F}_{p^k}$
Abstract

We formally define polynomial packing methods and initiate a unified study of related concepts in various contexts of cryptography. This includes homomorphic encryption (HE) packing and reverse multiplication-friendly embedding (RMFE) in information-theoretically secure multi-party computation (MPC). We prove several upper bounds and impossibility results on packing methods for $\mathbb{Z}_{p^k}$ or $\mathbb{F}_{p^k}$-messages into $\mathbb{Z}_{p^t}[x]/f(x)$ in terms of (i) packing density, (ii) level-consistency, and (iii) surjectivity. These results have implications on recent development of HE-based MPC over $\mathbb{Z}_{2^k}$ secure against actively corrupted majority and provide new proofs for upper bounds on RMFE.

2021

PKC

Adventures in Crypto Dark Matter: Attacks and Fixes for Weak Pseudorandom Functions
📺
Abstract

A weak pseudorandom function (weak PRF) is one of the most important cryptographic primitives for its efficiency although it has lower security than a standard PRF.
Recently, Boneh et al. (TCC'18) introduced two types of new weak PRF candidates, which are called a basic Mod-2/Mod-3 and alternative Mod-2/Mod-3 weak PRF.
Both use the mixture of linear computations defined on different small moduli to satisfy conceptual simplicity, low complexity (depth-2 ${\sf ACC^0}$) and MPC friendliness. In fact, the new candidates are conjectured to be exponentially secure against any adversary that allows exponentially many samples, and a basic Mod-2/Mod-3 weak PRF is the only candidate that satisfies all features above. However, none of the direct attacks which focus on basic and alternative Mod-2/Mod-3 weak PRFs use their own structures.
In this paper, we investigate weak PRFs from two perspectives; attacks, fixes.
We first propose direct attacks for an alternative Mod-2/Mod-3 weak PRF and a basic Mod-2/Mod-3 weak PRF when a circulant matrix is used as a secret key.
For an alternative Mod-2/Mod-3 weak PRF, we prove that the adversary's advantage is at least $2^{-0.105n}$, where $n$ is the size of the input space of the weak PRF. Similarly, we show that the advantage of our heuristic attack to the weak PRF with a circulant matrix key is larger than $2^{-0.21n}$, which is contrary to the previous expectation that `structured secret key' does not affect the security of a weak PRF. Thus, for an optimistic parameter choice $n = 2\lambda$ for the security parameter $\lambda$, parameters should be increased to preserve $\lambda$-bit security when an adversary obtains exponentially many samples.
Next, we suggest a simple method for repairing two weak PRFs affected by our attack while preserving the
parameters.

2021

CRYPTO

MHz2k: MPC from HE over $\mathbb{Z}_{2^k}$ with New Packing, Simpler Reshare, and Better ZKP
📺
Abstract

We propose a multi-party computation (MPC) protocol over $\mathbb{Z}_{2^k}$ secure against actively corrupted majority from somewhat homomorphic encryption. The main technical contributions are: (i) a new efficient packing method for $\mathbb{Z}_{2^k}$-messages in lattice-based somewhat homomorphic encryption schemes, (ii) a simpler reshare protocol for level-dependent packings, (iii) a more efficient zero-knowledge proof of plaintext knowledge on cyclotomic rings $\Z[X]/\Phi_M(X)$ with $M$ being a prime. Integrating them, our protocol shows from 2.2x upto 4.8x improvements in amortized communication costs compared to the previous best results.
Our techniques not only improve the efficiency of MPC over $\mathbb{Z}_{2^k}$ considerably, but also provide a toolkit that can be leveraged when designing other cryptographic primitives over $\mathbb{Z}_{2^k}$.

2021

TCHES

Over 100x Faster Bootstrapping in Fully Homomorphic Encryption through Memory-centric Optimization with GPUs
📺
Abstract

Fully Homomorphic encryption (FHE) has been gaining in popularity as an emerging means of enabling an unlimited number of operations in an encrypted message without decryption. A major drawback of FHE is its high computational cost. Specifically, a bootstrapping step that refreshes the noise accumulated through consequent FHE operations on the ciphertext can even take minutes of time. This significantly limits the practical use of FHE in numerous real applications.By exploiting the massive parallelism available in FHE, we demonstrate the first instance of the implementation of a GPU for bootstrapping CKKS, one of the most promising FHE schemes supporting the arithmetic of approximate numbers. Through analyzing CKKS operations, we discover that the major performance bottleneck is their high main-memory bandwidth requirement, which is exacerbated by leveraging existing optimizations targeted to reduce the required computation. These observations motivate us to utilize memory-centric optimizations such as kernel fusion and reordering primary functions extensively.Our GPU implementation shows a 7.02× speedup for a single CKKS multiplication compared to the state-of-the-art GPU implementation and an amortized bootstrapping time of 0.423us per bit, which corresponds to a speedup of 257× over a single-threaded CPU implementation. By applying this to logistic regression model training, we achieved a 40.0× speedup compared to the previous 8-thread CPU implementation with the same data.

2020

ASIACRYPT

Efficient Homomorphic Comparison Methods with Optimal Complexity
📺
Abstract

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.

2019

JOFC

Cryptanalysis of the CLT13 Multilinear Map
Abstract

In this paper, we describe a polynomial time cryptanalysis of the (approximate) multilinear map proposed by Coron, Lepoint, and Tibouchi in Crypto13 (CLT13). This scheme includes a zero-testing functionality that determines whether the message of a given encoding is zero or not. This functionality is useful for designing several of its applications, but it leaks unexpected values, such as linear combinations of the secret elements. By collecting the outputs of the zero-testing algorithm, we construct a matrix containing the hidden information as eigenvalues, and then recover all the secret elements of the CLT13 scheme via diagonalization of the matrix. In addition, we provide polynomial time algorithms to directly break the security assumptions of many applications based on the CLT13 scheme. These algorithms include solving subgroup membership, decision linear, and graded external Diffie–Hellman problems. These algorithms mainly rely on the computation of the determinants of the matrices and their greatest common divisor, instead of performing their diagonalization.

2019

CRYPTO

Statistical Zeroizing Attack: Cryptanalysis of Candidates of BP Obfuscation over GGH15 Multilinear Map
📺
Abstract

We present a new cryptanalytic algorithm on obfuscations based on GGH15 multilinear map. Our algorithm, statistical zeroizing attack, directly distinguishes two distributions from obfuscation while it follows the zeroizing attack paradigm, that is, it uses evaluations of zeros of obfuscated programs.Our attack breaks the recent indistinguishability obfuscation candidate suggested by Chen et al. (CRYPTO’18) for the optimal parameter settings. More precisely, we show that there are two functionally equivalent branching programs whose CVW obfuscations can be efficiently distinguished by computing the sample variance of evaluations.This statistical attack gives a new perspective on the security of the indistinguishability obfuscations: we should consider the shape of the distributions of evaluation of obfuscation to ensure security.In other words, while most of the previous (weak) security proofs have been studied with respect to algebraic attack model or ideal model, our attack shows that this algebraic security is not enough to achieve indistinguishability obfuscation. In particular, we show that the obfuscation scheme suggested by Bartusek et al. (TCC’18) does not achieve the desired security in a certain parameter regime, in which their algebraic security proof still holds.The correctness of statistical zeroizing attacks holds under a mild assumption on the preimage sampling algorithm with a lattice trapdoor. We experimentally verify this assumption for implemented obfuscation by Halevi et al. (ACM CCS’17).

2019

ASIACRYPT

Numerical Method for Comparison on Homomorphically Encrypted Numbers
Abstract

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.

2018

CRYPTO

Cryptanalyses of Branching Program Obfuscations over GGH13 Multilinear Map from the NTRU Problem
📺
Abstract

In this paper, we propose cryptanalyses of all existing indistinguishability obfuscation (iO) candidates based on branching programs (BP) over GGH13 multilinear map for all recommended parameter settings. To achieve this, we introduce two novel techniques, program converting using NTRU-solver and matrix zeroizing, which can be applied to a wide range of obfuscation constructions and BPs compared to previous attacks. We then prove that, for the suggested parameters, the existing general-purpose BP obfuscations over GGH13 do not have the desired security. Especially, the first candidate indistinguishability obfuscation with input-unpartitionable branching programs (FOCS 2013) and the recent BP obfuscation (TCC 2016) are not secure against our attack when they use the GGH13 with recommended parameters. Previously, there has been no known polynomial time attack for these cases.Our attack shows that the lattice dimension of GGH13 must be set much larger than previous thought in order to maintain security. More precisely, the underlying lattice dimension of GGH13 should be set to $$n=\tilde{\varTheta }( \kappa ^2 \lambda )$$n=Θ~(κ2λ) to rule out attacks from the subfield algorithm for NTRU where $$\kappa $$κ is the multilinearity level and $$\lambda $$λ the security parameter.

#### Program Committees

- Asiacrypt 2021
- PKC 2019
- Crypto 2017
- Asiacrypt 2016 (Program chair)
- Asiacrypt 2015 (Program chair)
- Asiacrypt 2014
- Asiacrypt 2013
- Eurocrypt 2013
- Asiacrypt 2012
- Crypto 2011
- Asiacrypt 2011
- PKC 2010
- PKC 2009
- PKC 2008
- Asiacrypt 2007
- Eurocrypt 2007
- PKC 2007

#### Coauthors

- Jung Ho Ahn (1)
- Jae Choon Cha (2)
- Seongtaek Chee (1)
- Wonhee Cho (2)
- Jean-Sébastien Coron (1)
- Pierre-Alain Fouque (1)
- Kyoohyung Han (3)
- Jae Woo Han (2)
- Minki Hhan (2)
- Jin Hong (2)
- Jung Yeon Hwang (1)
- Nam-Su Jho (1)
- Byungheup Jun (1)
- Wonkyung Jung (1)
- Ju-Sung Kang (1)
- Jonathan Katz (1)
- Jinsu Kim (1)
- Sangpyo Kim (1)
- Sungwook Kim (1)
- Miran Kim (2)
- Myung-Hwan Kim (1)
- Jiseung Kim (3)
- Minkyu Kim (2)
- Andrey Kim (2)
- Daeho Kim (1)
- Jeong Han Kim (1)
- Dongwoo Kim (3)
- Duhyeong Kim (2)
- Ki Hyoung Ko (2)
- Dong Hoon Lee (1)
- Sangjin Lee (2)
- Changmin Lee (5)
- Dong Hoon Lee (1)
- Younho Lee (1)
- Hun Hee Lee (1)
- Keewoo Lee (3)
- Moon Sung Lee (1)
- Tancrède Lepoint (1)
- Brice Minaud (1)
- Choonsik Park (2)
- Sung-Mo Park (1)
- Sangwoo Park (1)
- Hansol Ryu (3)
- Jae Hong Seo (2)
- Yongsoo Song (2)
- Damien Stehlé (3)
- Mehdi Tibouchi (1)
- Jeong Hyun Yi (1)
- Eun Sun Yoo (1)
- Aaram Yun (1)