Moon Sung LEE

Journal papers

International Conference & Workshop papers

Ph.D. thesis :

Zeroizing Attacks on Indistinguishability Obfuscation over CLT13

Jean-Sebastien Coron, Moon Sung Lee, Tancrede Lepoint, Mehdi Tibouchi


Reference : Public-Key Cryptography - PKC 2017

Abstract : In this work, we describe a new polynomial-time attack on the multilinear maps of Coron, Lepoint, and Tibouchi (CLT13), when used in candidate indistinguishability obfuscation (iO) schemes. More specifically, we show that given the obfuscation of the simple branching program that computes the always zero functionality previously considered by Miles, Sahai and Zhandry (Crypto 2016), one can recover the secret parameters of CLT13 in polynomial time via an extension of the zeroizing attack of Coron et al. (Crypto 2015). Our attack is generalizable to arbitrary oblivious branching programs for arbitrary functionality, and allows (1) to recover the secret parameters of CLT13, and then (2) to recover the randomized branching program entirely. Our analysis thus shows that almost all single-input variants of iO over CLT13 are insecure.

Sparse subset sum problem from Gentry-Halevi's fully homomorphic encryption

Moon Sung Lee


Reference : IET Information Security, 11 (1), 2017

Abstract : In Gentry's fully homomorphic encryption scheme, a sparse subset sum problem (SSSP) is used and a big set is included in the public key. In the implementation of a variant, to reduce the size of the public key, Gentry and Halevi used a specific form of a SSSP constructed from geometric progressions. In this study, the authors solve Gentry and Halevi's sparse subset sum challenges for the first time. Owing to the aggressive choice of parameters, the process is fairly easy and can be done by simply modifying their lattice-based attack. Their experiment shows that even a large challenge can be solved within two days. As a second contribution, considering other attacks such as a hybrid attack combining a meet in the middle attack with a lattice-based attack, they provide a new condition for hard instances of the SSSP from geometric progressions.

Cryptanalysis of GGH15 Multilinear Maps

Jean-Sebastien Coron, Moon Sung Lee, Tancrede Lepoint, Mehdi Tibouchi


Reference : Advances in Cryptology - CRYPTO 2016

Abstract : We describe a cryptanalysis of the GGH15 multilinear maps. Our attack breaks the multipartite key-agreement protocol in polynomial time by generating an equivalent user private key; it also applies to GGH15 with safeguards. We also describe attacks against variants of the GGH13 multilinear maps proposed by Halevi (ePrint 2015/866) aiming at supporting graph-induced constraints, as in GGH15.

The polynomial approximate common divisor problem and its application to the fully homomorphic encryption

Jung Hee Cheon, Hyunsook Hong, Moon Sung Lee, Hansol Ryu


Reference : Information Sciences, 326 (1), 2016

Abstract : We propose and examine the approximate polynomial common divisor problem, which can be viewed as a polynomial analogue to the approximate integer common divisor problem. Since our problem is rather new, we perform extensive cryptanalysis, applying various known attacks against the structurally similar problems. Moreover, we propose a small root finding algorithm for multivariate modular equation system, and apply it to the proposed problem. Those analyses confirm that the proposed problem is difficult with appropriate parameters.
Additionally, we construct a simple somewhat homomorphic encryption scheme, which can efficiently accommodate large message spaces. When the evaluation of a low degree polynomial of very large integers is required, our scheme is more efficient than the recent RLWE-based scheme, YASHE, by Bos et al. (2013). In particular, multiplication is ten times faster when evaluating degree-10 polynomial of 1638-bit integers. We convert this scheme to a leveled fully homomorphic encryption scheme by applying Brakerski's scale invariant technique, and the resulting scheme has features similar to the variant of van Dijk et al.'s scheme by Coron et al. (2014). Our scheme, however, does not use the subset sum, which makes its design much simpler.

Cryptanalysis of the Co-ACD Assumption

Pierre-Alain Fouque, Moon Sung Lee, Tancrede Lepoint, Mehdi Tibouchi


Reference : Advances in Cryptology - CRYPTO 2015

Abstract : At ACM-CCS 2014, Cheon, Lee and Seo introduced a new number-theoretic assumption, the Co-Approximate Common Divisor (Co-ACD) assumption, based on which they constructed several cryptographic primitives, including a particularly fast additively homomorphic encryption scheme. For their proposed parameters, they found that their scheme was the "most efficient of those that support an additive homomorphic property". Unfortunately, it turns out that those parameters, originally aiming at 128-bit security, can be broken in a matter of seconds.
Indeed, this paper presents several lattice-based attacks against the Cheon-Lee-Seo (CLS) homomorphic encryption scheme and of the underlying Co-ACD assumption that are effectively devastating for the proposed constructions. A few known plaintexts are sufficient to decrypt any ciphertext in the symmetric-key CLS scheme, and small messages can even be decrypted without any known plaintext at all. This breaks the security of both the symmetric-key and the public-key variants of CLS encryption as well as the underlying decisional Co-ACD assumption. Moreover, Coppersmith techniques can be used to solve the search variant of the Co-ACD problem and mount a full key recovery on the CLS scheme.

CRT-based fully homomorphic encryption over the integers

Jung Hee Cheon, Jinsu Kim, Moon Sung Lee, Aaram Yun


Reference : Information Sciences, 310, 2015

Abstract : In 1978, Rivest, Adleman and Dertouzos introduced the basic concept of privacy homomorphism that allows computation on encrypted data without decryption. It was an interesting work whose idea precedes the recent development of fully homomorphic encryption, although actual example schemes proposed in the paper are all susceptible to simple known-plaintext attacks.
In this paper, we revisit one of their proposals, in particular the third scheme which is based on the Chinese Remainder Theorem and is ring homomorphic. It is known that only a single pair of known plaintext/ciphertext is needed to break this scheme. However, by exploiting the standard technique to insert an error to a message before encryption, we can cope with this problem. We present a secure modification of their proposal by showing that the proposed scheme is fully homomorphic and secure against the chosen plaintext attacks under the approximate GCD assumption and the sparse subset sum assumption when the message space is restricted to Z_2^k.
Interestingly, the proposed scheme can be regarded as a generalization of the DGHV scheme with larger plaintext space. Our scheme has O(lambda^5) ciphertext expansion overhead while the DGHV has O(lambda^8) for the security parameter lambda. When restricted to the homomorphic encryption scheme with depth of O(log lambda) , the overhead is reduced to O(lambda) . Our scheme can be used in applications requiring a large message space Z_Q for log Q=O(lambda^4) , or SIMD style operations on Z_Q^k for log Q=O(lambda), k=O(lambda^3) , with O(lambda^5) ciphertext size as in the DGHV.

Accelerating Bootstrapping in FHEW using GPUs

Moon Sung Lee, Yongje Lee, Jung Hee Cheon, Yunheung Paek


Reference : Application-specific Systems, Architectures and Processors (ASAP), 2015 IEEE 26th International Conference on

Abstract : Recently, the usage of GPU is not limited to the jobs associated with graphics and a wide variety of applications take advantage of the flexibility of GPUs to accelerate the computing performance. Among them, one of the most emerging applications is the fully homomorphic encryption (FHE) scheme, which enables arbitrary computations on encrypted data. Despite much research effort, it cannot be considered as practical due to the enormous amount of computations, especially in the bootstrapping procedure. In this paper, we accelerate the performance of the recently suggested fast bootstrapping method in FHEW scheme using GPUs, as a case study of a FHE scheme. In order to optimize, we explored the reference code and carried out profiling to find out candidates for performance acceleration. Based on the profiling results, combined with more flexible tradeoff method, we optimized the bootstrapping algorithm in FHEW using GPU and CUDA's programming model. The empirical result shows that the bootstrapping of FHEW ciphertext can be done in less than 0.11 second after optimization.

Batch Fully Homomorphic Encryption over the Integers

Jung Hee Cheon, Jean-Sebastien Coron, Jinsu Kim, Moon Sung Lee, Tancrede Lepoint, Mehdi Tibouchi, Aaram Yun


Reference : Advances in Cryptology - EUROCRYPT 2013

Abstract : We extend the fully homomorphic encryption scheme over the integers of van Dijk et al.(DGHV) into a batch fully homomorphic encryption scheme, i.e. to a scheme that supports encrypting and homomorphically processing a vector of plaintexts as a single ciphertext.
We present two variants in which the semantic security is based on different assumptions. The first variant is based on a new decisional problem, the Decisional Approximate-GCD problem, whereas the second variant is based on the more classical computational Error-Free Approximate-GCD problem but requires additional public key elements.
We also show how to perform arbitrary permutations on the underlying plaintext vector given the ciphertext and the public key. Our scheme offers competitive performance even with the bootstrapping procedure: we describe an implementation of the homomorphic evaluation of AES, with an amortized cost of about 12 minutes per AES ciphertext on a standard desktop computer; this is comparable to the timings presented by Gentry et al.at Crypto 2012 for their implementation of a Ring-LWE based fully homomorphic encryption scheme.

Improved cryptanalysis of a knapsack-based probabilistic encryption scheme

Moon Sung Lee


Reference : Information Sciences, 222, 2013

Abstract : Wang et al. [B. Wang, Q. Wu, Y. Hu, Information Sciences 177 (2007)] proposed a knapsack-based probabilistic encryption scheme with non-binary coefficients which enjoys a high density larger than 1.06 in the worst case. In this work, we successfully attack this scheme by showing that a public key and a restriction on system parameters allow the attacker to recover a secret key in a cubic time complexity using modular equations. This approach is much more efficient than the previous attack by Youssef [A.M. Youssef, Information Sciences 179 (2009)], in which lattice basis reductions are used. Recovering secret keys can be done within 4 h and 4 days when n = 100 and 200, respectively. A simple modification that helps resist known attacks is also discussed.

Cryptanalysis of a public key cryptosystem based on the matrix combinatorial problem

Moon Sung Lee


Reference : Informatica, 24 (2), 2013

Abstract : In this paper, we present a cryptanalysis of a public key cryptosystem based on the matrix combinatorial problem proposed by Wang and Hu (2010). Using lattice-based methods finding small integer solutions of modular linear equations, we recover the secret key of this cryptosystem for a certain range of parameters. In experiments, for the suggested parameters by Wang and Hu, the secret key can be recovered in seconds.

Cryptanalysis of a quadratic compact knapsack public-key cryptosystem

Moon Sung Lee


Reference : Computers & Mathematics with Applications, 62 (9), 2011

Abstract : Recently, Wang and Hu have proposed a high-density quadratic compact knapsack public-key cryptosystem using the Chinese remainder theorem to disguise two secret cargo vectors. The system is claimed to be secure against certain known attacks; however, it has not been demonstrated to fulfill any provable security goals. In this work, we show that this system is not secure. Exploiting the special structure of system parameters, we first show that a candidate list for the secret modulus can be obtained by solving linear equations with small solutions. Next, we show that with this candidate list, all other secrets can be recovered in succession with lattice-based methods by solving certain modular linear equations with small solutions. As a result, recovering a private key can be done in about 11 h for the proposed system parameter n=100 . We also discuss a method to thwart the proposed attack.

Cryptanalysis of the GGH Cryptosystem

Moon Sung Lee, Sang Geun Hahn


Reference : Mathematics in Computer Science, 3 (2), 2010

Abstract : In this correspondence, we show that partial information of plaintext can be used to simplify the decryption problem in the case of the GGH cryptosystem. Combined with Nguyen's previous attack, we solve the numerical GGH challenge of the highest dimension 400, proposed on the Internet by the authors of the cryptosystem. We also discuss how to avoid this attack.