## CryptoDB

### Takahiro Matsuda

#### Affiliation: AIST, Japan

#### Publications

**Year**

**Venue**

**Title**

2019

PKC

Improved Security Evaluation Techniques for Imperfect Randomness from Arbitrary Distributions
Abstract

Dodis and Yu (TCC 2013) studied how the security of cryptographic primitives that are secure in the “ideal” model in which the distribution of a randomness is the uniform distribution, is degraded when the ideal distribution of a randomness is switched to a “real-world” (possibly biased) distribution that has some lowerbound on its min-entropy or collision-entropy. However, in many constructions, their security is guaranteed only when a randomness is sampled from some non-uniform distribution (such as Gaussian in lattice-based cryptography), in which case we cannot directly apply the results by Dodis and Yu.In this paper, we generalize the results by Dodis and Yu using the Rényi divergence, and show how the security of a cryptographic primitive whose security is guaranteed when the ideal distribution of a randomness is a general (possibly non-uniform) distribution Q, is degraded when the distribution is switched to another (real-world) distribution R. More specifically, we derive two general inequalities regarding the Rényi divergence of R from Q and an adversary’s advantage against the security of a cryptographic primitive. As applications of our results, we show (1) an improved reduction for switching the distributions of distinguishing problems with public samplability, which is simpler and much tighter than the reduction by Bai et al. (ASIACRYPT 2015), and (2) how the differential privacy of a mechanism is degraded when its randomness comes from not an ideal distribution Q but a real-world distribution R. Finally, we show methods for approximate-sampling from an arbitrary distribution Q with some guaranteed upperbound on the Rényi divergence (of the distribution R of our sampling methods from Q).

2019

PKC

Adaptively Single-Key Secure Constrained PRFs for $\mathrm {NC}^1$
Abstract

We present a construction of an adaptively single-key secure constrained PRF (CPRF) for $$\mathbf {NC}^1$$ assuming the existence of indistinguishability obfuscation (IO) and the subgroup hiding assumption over a (pairing-free) composite order group. This is the first construction of such a CPRF in the standard model without relying on a complexity leveraging argument.To achieve this, we first introduce the notion of partitionable CPRF, which is a CPRF accommodated with partitioning techniques and combine it with shadow copy techniques often used in the dual system encryption methodology. We present a construction of partitionable CPRF for $$\mathbf {NC}^1$$ based on IO and the subgroup hiding assumption over a (pairing-free) group. We finally prove that an adaptively single-key secure CPRF for $$\mathbf {NC}^1$$ can be obtained from a partitionable CPRF for $$\mathbf {NC}^1$$ and IO.

2019

PKC

Lattice-Based Revocable (Hierarchical) IBE with Decryption Key Exposure Resistance
Abstract

Revocable identity-based encryption (RIBE) is an extension of IBE that supports a key revocation mechanism, which is an indispensable feature for practical cryptographic schemes. Due to this extra feature, RIBE is often required to satisfy a strong security notion unique to the revocation setting called decryption key exposure resistance (DKER). Additionally, hierarchal IBE (HIBE) is another orthogonal extension of IBE that supports key delegation functionalities allowing for scalable deployments of cryptographic schemes. So far, R(H)IBE constructions with DKER are only known from bilinear maps, where all constructions rely heavily on the so-called key re-randomization property to achieve the DKER and/or hierarchal feature. Since lattice-based schemes seem to be inherently ill-fit with the key re-randomization property, no construction of lattice-based R(H)IBE schemes with DKER are known.In this paper, we propose the first lattice-based RHIBE scheme with DKER without relying on the key re-randomization property, departing from all the previously known methods. We start our work by providing a generic construction of RIBE schemes with DKER, which uses as building blocks any two-level standard HIBE scheme and (weak) RIBE scheme without DKER. Based on previous lattice-based RIBE constructions without DKER, our result implies the first lattice-based RIBE scheme with DKER. Then, building on top of our generic construction, we construct the first lattice-based RHIBE scheme with DKER, by further exploiting the algebraic structure of lattices. To this end, we prepare a new tool called the level conversion keys, which enables us to achieve the hierarchal feature without relying on the key re-randomization property.

2019

CRYPTO

CCA Security and Trapdoor Functions via Key-Dependent-Message Security
📺
Abstract

We study the relationship among public-key encryption (PKE) satisfying indistinguishability against chosen plaintext attacks (IND-CPA security), that against chosen ciphertext attacks (IND-CCA security), and trapdoor functions (TDF). Specifically, we aim at finding a unified approach and some additional requirement to realize IND-CCA secure PKE and TDF based on IND-CPA secure PKE, and show the following two main results.As the first main result, we show how to achieve IND-CCA security via a weak form of key-dependent-message (KDM) security. More specifically, we construct an IND-CCA secure PKE scheme based on an IND-CPA secure PKE scheme and a secret-key encryption (SKE) scheme satisfying one-time KDM security with respect to projection functions (projection-KDM security). Projection functions are very simple functions with respect to which KDM security has been widely studied. Since the existence of projection-KDM secure PKE implies that of the above two building blocks, as a corollary of this result, we see that the existence of IND-CCA secure PKE is implied by that of projection-KDM secure PKE.As the second main result, we extend the above construction of IND-CCA secure PKE into that of TDF by additionally requiring a mild requirement for each building block. Our TDF satisfies adaptive one-wayness. We can instantiate our TDF based on a wide variety of computational assumptions. Especially, we obtain the first TDF (with adaptive one-wayness) based on the sub-exponential hardness of the constant-noise learning-parity-with-noise (LPN) problem.

2018

CRYPTO

Constrained PRFs for $\mathrm{NC}^1$ in Traditional Groups
📺
Abstract

We propose new constrained pseudorandom functions (CPRFs) in traditional groups. Traditional groups mean cyclic and multiplicative groups of prime order that were widely used in the 1980s and 1990s (sometimes called “pairing free” groups). Our main constructions are as follows.
We propose a selectively single-key secure CPRF for circuits with depth$$O(\log n)$$(that is,NC$$^1$$circuits) in traditional groups where n is the input size. It is secure under the L-decisional Diffie-Hellman inversion (L-DDHI) assumption in the group of quadratic residues $$\mathbb {QR}_q$$ and the decisional Diffie-Hellman (DDH) assumption in a traditional group of order qin the standard model.We propose a selectively single-key private bit-fixing CPRF in traditional groups. It is secure under the DDH assumption in any prime-order cyclic group in the standard model.We propose adaptively single-key secure CPRF for NC$$^1$$ and private bit-fixing CPRF in the random oracle model.
To achieve the security in the standard model, we develop a new technique using correlated-input secure hash functions.

2018

PKC

Related Randomness Security for Public Key Encryption, Revisited
Abstract

Motivated by the history of randomness failures in practical systems, Paterson, Schuldt, and Sibborn (PKC 2014) introduced the notion of related randomness security for public key encryption. In this paper, we firstly show an inherent limitation of this notion: if the family of related randomness functions is sufficiently rich to express the encryption function of the considered scheme, then security cannot be achieved. This suggests that achieving security for function families capable of expressing more complex operations, such as those used in random number generation, might be difficult. The current constructions of related randomness secure encryption in the standard model furthermore reflect this; full security is only achieved for function families with a convenient algebraic structure. We additionally revisit the seemingly optimal random oracle model construction by Paterson et al. and highlight its limitations.To overcome this difficulty, we propose a new notion which we denote related refreshable randomness security. This notion captures a scenario in which an adversary has limited time to attack a system before new entropy is added. More specifically, the number of encryption queries with related randomness the adversary can make before the randomness is refreshed, is bounded, but the adversary is allowed to make an unbounded total number of queries. Furthermore, the adversary is allowed to influence how entropy is added to the system. In this setting, we construct an encryption scheme which remains secure in the standard model for arbitrary function families of size $$2^p$$2p (where p is polynomial in the security parameter) that satisfy certain collision-resistant and output-unpredictability properties. This captures a rich class of functions, which includes, as a special case, circuits of polynomial size. Our scheme makes use of a new construction of a (bounded) related-key attack secure pseudorandom function, which in turn is based on a new flavor of the leftover hash lemma. These technical results might be of independent interest.

2016

ASIACRYPT

2015

EPRINT

2015

EPRINT

2015

ASIACRYPT

2012

CRYPTO

#### Program Committees

- PKC 2019
- TCC 2019
- Asiacrypt 2019
- PKC 2017
- Asiacrypt 2017
- Asiacrypt 2016

#### Coauthors

- Nuttapong Attrapadung (2)
- Keita Emura (1)
- Goichiro Hanaoka (16)
- Shuichi Katsumata (1)
- Yutaka Kawai (1)
- Fuyuki Kitagawa (2)
- Kanta Matsuura (4)
- Takao Murakami (1)
- Ryo Nishimaki (2)
- Satsuya Ohata (1)
- Go Ohtake (1)
- Jacob C. N. Schuldt (2)
- Kenta Takahashi (1)
- Atsushi Takayasu (1)
- Keisuke Tanaka (4)
- Yuyu Wang (2)
- Shota Yamada (3)
- Takashi Yamakawa (2)
- Zongyang Zhang (1)