## CryptoDB

### Jung Hee Cheon

#### Affiliation: Seoul National University, KR

#### Publications

**Year**

**Venue**

**Title**

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.

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.

2009

EPRINT

Reducing RFID Reader Load with the Meet-in-the-Middle Strategy
Abstract

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.

2006

EPRINT

Analysis of Privacy-Preserving Element Reduction of Multiset
Abstract

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

EPRINT

BROADCAST ENCRYPTION $\pi$
Abstract

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

Skipping, Cascade, and Combined Chain Schemes for Broadcast Encryption
Abstract

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

Use of Sparse and/or Complex Exponents in Batch Verification of Exponentiations
Abstract

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

EPRINT

A New ID-based Signature with Batch Verification
Abstract

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

Timed-Release and Key-Insulated Public Key Encryption
Abstract

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

EPRINT

A Polynomial Time Algorithm for the Braid Diffie-Hellman Conjugacy Problem
Abstract

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

A Cryptanalysis of the Original Domingo-Ferrer's Algebraic Privacy Homomophism
Abstract

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

An Identity-Based Signature from Gap Diffie-Hellman Groups
Abstract

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

A Universal Forgery of Hess's Second ID-based Signature against the Known-message Attack
Abstract

In this paper we propose a universal forgery attack of Hess's second
ID-based signature scheme against the known-message attack.

2002

EPRINT

Diffie-Hellman Problems and Bilinear Maps
Abstract

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.

#### Program Committees

- PKC 2019
- Crypto 2017
- Asiacrypt 2016
- Asiacrypt 2015
- Asiacrypt 2014
- Eurocrypt 2013
- Asiacrypt 2013
- Asiacrypt 2012
- Asiacrypt 2011
- Crypto 2011
- PKC 2010
- PKC 2009
- PKC 2008
- Eurocrypt 2007
- PKC 2007
- Asiacrypt 2007

#### Coauthors

- Jae Choon Cha (3)
- 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)
- Jeongdae Hong (1)
- Dowon Hong (1)
- Jin Hong (2)
- Nicholas J. Hopper (1)
- Jung Yeon Hwang (1)
- Nam-Su Jho (3)
- Byungheup Jun (2)
- Ju-Sung Kang (1)
- Jonathan Katz (1)
- Jinsu Kim (1)
- Sungwook Kim (1)
- Yongdae Kim (2)
- Miran Kim (3)
- Myung-Hwan Kim (3)
- Jiseung Kim (3)
- Minkyu Kim (2)
- Andrey Kim (2)
- Daeho Kim (1)
- Jeong Han Kim (1)
- Dongwoo Kim (2)
- Duhyeong Kim (2)
- Ki Hyoung Ko (2)
- Kristin E. Lauter (1)
- Dong Hoon Lee (1)
- Sangjin Lee (2)
- Changmin Lee (7)
- Dong Hoon Lee (3)
- Hun Hee Lee (1)
- Keewoo Lee (1)
- Moon Sung Lee (1)
- Tancrède Lepoint (1)
- Seongan Lim (1)
- Brice Minaud (1)
- Hyun Soo Nam (1)
- Ivan Osipkov (1)
- Choonsik Park (2)
- Sung-Mo Park (1)
- Sangwoo Park (1)
- Hansol Ryu (4)
- Jae Hong Seo (3)
- Yongsoo Song (2)
- Damien Stehlé (3)
- Mehdi Tibouchi (1)
- Gene Tsudik (1)
- Jeong Hyun Yi (1)
- Eun Sun Yoo (3)
- HyoJin Yoon (1)
- Hyo Jin Yoon (1)
- Aaram Yun (1)