## CryptoDB

### Jung Hee Cheon

#### Publications

Year
Venue
Title
2021
PKC
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
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}$.
2020
ASIACRYPT
2020
ASIACRYPT
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
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
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
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
EUROCRYPT
2018
CRYPTO
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.
2017
ASIACRYPT
2016
EUROCRYPT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EUROCRYPT
2015
EUROCRYPT
2013
EUROCRYPT
2012
TCC
2012
PKC
2010
JOFC
2009
EPRINT
In almost any RFID system, a reader needs to identify, and optionally authenticate, a multitude of tags. If each tag has a unique secret, identification and authentication are trivial, however, the reader (or a back-end server) needs to perform a brute-force search for each tag-reader interaction. In this paper, we suggest a simple, efficient and secure technique that reduces reader computation to $O(\sqrt N \cdot \log N)$. Our technique is based on the well-known meet-in-the-middle'' strategy used in the past to attack certain symmetric ciphers.
2009
PKC
2008
PKC
2008
ASIACRYPT
2007
PKC
2006
EUROCRYPT
2006
EPRINT
Among private set operations, the privacy preserving element reduction of a multiset can be an important tool for privacy enhancing technology as itself or in the combination with other private set operations. Recently, a protocol, over-threshold-set-union-protocol, for a privacy preserving element reduction method of a multiset was proposed by Kissner and Song in Crypto 2005. In this paper, we point out that there is a mathematical flaw in their polynomial representation of element reduction of a multiset and the resulting protocol error from the flaw in the polynomial representation of a multiset. We correct their polynomial representation of a multiset and propose an over-threshold-set-operation-protocol based on the corrected representation. Our over-threshold-set-operation-protocol can be combined with a privacy preserving set operation and outputs those elements appears over the predetermined threshold number times in the resulting multiset of set operation.
2005
EUROCRYPT
2005
EPRINT
We propose a new broadcast encryption scheme $\pi$ based on the idea of one key per each punctured interval'. Let $N$ and $r$ be the numbers of total users and revoked users, respectively. In our scheme with $p$-punctured $c$-intervals, the transmission overhead is asymptotically {\normalsize$\frac r{p+1}$} as $r$ grows. We also introduce two variants of our scheme to improve the efficiency for small $r$. Our scheme is very flexible with two parameters $p$ and $c$. We may take $p$ as large as possible if a user device allows a large key storage, and set $c$ as small as possible if the storage size and the computing power is limited. Our scheme also possesses another remarkable feature that any number of new users can join at any time without key refreshment, which is not possible in other known practical schemes.
2005
EPRINT
We develop a couple of new methods to reduce transmission overheads in broadcast encryption. The methods are based on the idea of assigning {\it one key per each partition using one-way key chains} after partitioning the users. One method adopts {\it skipping chains} on partitions containing up to $p$ revoked users and the other adopts {\it cascade chains} on partitions with layer structure. The scheme using the former reduces the transmission overhead down to $\frac r{p+1}$ asymptotically as $r$ grows, and the scheme using the latter keeps the transmission overhead very small when $r$ approaches 0, where $r$ is the number of revoked users. Combining the two schemes, we propose a new broadcast encryption scheme with least transmission overhead. Our schemes also possess a remarkable feature that any number of new users can join at any time without key update, which is not available for most of known practical schemes.
2005
EPRINT
Modular exponentiation in an abelian group is one of the most frequently used mathematical primitives in modern cryptography. {\em Batch verification} is to verify many exponentiations simultaneously. We propose two fast batch verification algorithms. The first one makes use of exponents with small weight, called {\em sparse exponents}, which is asymptotically 10 times faster than the individual verification and twice faster than the previous works without security loss. The second one is applied only to elliptic curves defined over small finite fields. Using sparse Frobenius expansion with small integer coefficients, we propose a complex exponent test which is four times faster than the previous works. For example, each exponentiation in one batch requires asymptotically 9 elliptic curve additions in some elliptic curves for $2^{80}$ security.
2004
FSE
2004
EPRINT
An identity (ID)-based signature scheme allows any pair of users to communicate securely and to verify each other's signatures without exchanging public key certificates. We have several ID-based signatures based on the discrete logarithm problem. While they have an advantage that the system secret can be shared by several parties through threshold schemes, they have a critical disadvantage in efficiency. To enhance the efficiency of verification, we propose a new ID-based signature scheme that allows batch verification of multiple signatures. The verification cost of the proposed signature scheme for $k$ signatures is almost constant with minimal security loss and when a new signature by a different signer is added to the batch verification, the additional cost is almost a half of that of a single signature. We prove that the proposed signature scheme is secure against existential forgery under adaptively chosen message and ID attack in the random oracle model and show why other ID-based signature schemes are hard to achieve these properties.
2004
EPRINT
In this paper we consider two security notions related to Identity Based Encryption: Key-insulated public key encryption, introduced by Dodis, Katz, Xu and Yung; and Timed-Release Public Key cryptography, introduced independently by May and Rivest, Shamir and Wagner. We first formalize the notion of secure timed-release public key encryption, and show that, despite several differences in its formulation, it is equivalent to strongly key-insulated public key encryption (with optimal threshold and random access key updates). Next, we introduce the concept of an authenticated timed-release cryptosystem, briefly consider generic constructions, and then give a construction based on a single primitive which is efficient and provably secure.
2003
CRYPTO
2003
PKC
2003
EPRINT
We propose the first polynomial time algorithm for the braid Diffie-Hellman conjugacy problem (DHCP) on which the braid key exchange scheme and the braid encryption scheme are based~\cite{KLCHKP01}. We show the proposed method solves the DHCP for the image of braids under the Lawrence-Krammer representation and the solutions play the equivalent role of the original key for the DHCP of braids. Given a braid index $n$ and a canonical length $\ell$, the complexity is about $2^{-2}\ell^3 n^{4\tau+2}\log n$ bit operations, where $\tau=\log_27\approx 2.8$ (Theoretically, it can be reduced to $O(\ell^3 n^{8.3}\log n)$ using $\tau=2.376$). Further, we show that the generalization into the decomposition problem causes only 8 times of the complexity.
2003
EPRINT
We propose a cryptanalysis of the original Domingo-Ferrer's algebraic privacy homomorphism. We show that the scheme over $\Z_n$ can be broken by $d+1$ known plaintexts in $O(d^3\log^2 n)$ time when it has $d$ times expansion through the encryption. Furthermore even when the public modulus $n$ is kept secret, it can be broken by $d+2$ known plaintexts in time at most $O(d^5\log^2(dn))$.
2002
EPRINT
In this paper we propose an identity(ID)-based signature scheme using gap Diffie-Hellman (GDH) groups. Our scheme is proved secure against existential forgery on adaptively chosen message and ID attack under the random oracle model. Using GDH groups obtained from bilinear pairings, as a special case of our scheme, we obtain an ID-based signature scheme that shares the same system parameters and the same private/public key pairs with the ID-based encryption scheme (BF-IBE) by Boneh and Franklin, and is as efficient as the BF-IBE. Combining our signature scheme with the BF-IBE yields a complete solution of an ID-based public key system. It can be an alternative for certificate-based public key infrastructures, especially when efficient key management and moderate security are required.
2002
EPRINT
In this paper we propose a universal forgery attack of Hess's second ID-based signature scheme against the known-message attack.
2002
EPRINT
We investigate relations among the discrete logarithm (DL) problem, the Diffie-Hellman (DH) problem and the bilinear Diffie-Hellman (BDH) problem when we have an efficient computable non-degenerate bilinear map $e:G\times G \rightarrow H$. Under a certain assumption on the order of $G$, we show that the DH problem on $H$ implies the DH problem on $G$, and both of them are equivalent to the BDH problem when $e$ is {\it weak-invertible}. Moreover, we show that given the bilinear map $e$ an injective homomorphism $f:H\rightarrow G$ enables us to solve the DH problem on $G$ efficiently, which implies the non-existence a {\it self-bilinear} map $e:G\times G \rightarrow G$ when the DH problem on $G$ is hard. Finally we introduce a sequence of bilinear maps and its applications.
2001
ASIACRYPT
2001
CRYPTO
2000
CRYPTO
1999
EUROCRYPT
1998
PKC

#### Program Committees

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