## CryptoDB

### Ryo Nishimaki

#### Affiliation: NTT Secure Platform Labs, Japan

#### Publications

**Year**

**Venue**

**Title**

2019

PKC

Leakage-Resilient Identity-Based Encryption in Bounded Retrieval Model with Nearly Optimal Leakage-Ratio
Abstract

We propose new constructions of leakage-resilient public-key encryption (PKE) and identity-based encryption (IBE) schemes in the bounded retrieval model (BRM). In the BRM, adversaries are allowed to obtain at most
$$\ell $$
-bit leakage from a secret key and we can increase
$$\ell $$
only by increasing the size of secret keys without losing efficiency in any other performance measure. We call
$$\ell /|\mathsf {sk}|$$
leakage-ratio where
$$|\mathsf {sk}|$$
denotes a bit-length of a secret key. Several PKE/IBE schemes in the BRM are known. However, none of these constructions achieve a constant leakage-ratio under a standard assumption in the standard model. Our PKE/IBE schemes are the first schemes in the BRM that achieve leakage-ratio
$$1-\epsilon $$
for any constant
$$\epsilon >0$$
under standard assumptions in the standard model.As previous works, we use identity-based hash proof systems (IB-HPS) to construct IBE schemes in the BRM. It is known that a parameter for IB-HPS called the universality-ratio is translated into the leakage-ratio of the resulting IBE scheme in the BRM. We construct an IB-HPS with universality-ratio
$$1-\epsilon $$
for any constant
$$\epsilon >0$$
based on any inner-product predicate encryption (IPE) scheme with compact secret keys. Such IPE schemes exist under the d-linear, subgroup decision, learning with errors, or computational bilinear Diffie-Hellman assumptions. As a result, we obtain IBE schemes in the BRM with leakage-ratio
$$1-\epsilon $$
under any of these assumptions. Our PKE schemes are immediately obtained from our IBE schemes.

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

EUROCRYPT

Designated Verifier/Prover and Preprocessing NIZKs from Diffie-Hellman Assumptions
📺
Abstract

In a non-interactive zero-knowledge (NIZK) proof, a prover can non-interactively convince a verifier of a statement without revealing any additional information. Thus far, numerous constructions of NIZKs have been provided in the common reference string (CRS) model (CRS-NIZK) from various assumptions, however, it still remains a long standing open problem to construct them from tools such as pairing-free groups or lattices. Recently, Kim and Wu (CRYPTO’18) made great progress regarding this problem and constructed the first lattice-based NIZK in a relaxed model called NIZKs in the preprocessing model (PP-NIZKs). In this model, there is a trusted statement-independent preprocessing phase where secret information are generated for the prover and verifier. Depending on whether those secret information can be made public, PP-NIZK captures CRS-NIZK, designated-verifier NIZK (DV-NIZK), and designated-prover NIZK (DP-NIZK) as special cases. It was left as an open problem by Kim and Wu whether we can construct such NIZKs from weak paring-free group assumptions such as DDH. As a further matter, all constructions of NIZKs from Diffie-Hellman (DH) type assumptions (regardless of whether it is over a paring-free or paring group) require the proof size to have a multiplicative-overhead $$|C| \cdot \mathsf {poly}(\kappa )$$|C|·poly(κ), where |C| is the size of the circuit that computes the $$\mathbf {NP}$$NP relation.In this work, we make progress of constructing (DV, DP, PP)-NIZKs with varying flavors from DH-type assumptions. Our results are summarized as follows:DV-NIZKs for $$\mathbf {NP}$$NP from the CDH assumption over pairing-free groups. This is the first construction of such NIZKs on pairing-free groups and resolves the open problem posed by Kim and Wu (CRYPTO’18).DP-NIZKs for $$\mathbf {NP}$$NP with short proof size from a DH-type assumption over pairing groups. Here, the proof size has an additive-overhead $$|C|+\mathsf {poly}(\kappa )$$|C|+poly(κ) rather then an multiplicative-overhead $$|C| \cdot \mathsf {poly}(\kappa )$$|C|·poly(κ). This is the first construction of such NIZKs (including CRS-NIZKs) that does not rely on the LWE assumption, fully-homomorphic encryption, indistinguishability obfuscation, or non-falsifiable assumptions.PP-NIZK for $$\mathbf {NP}$$NP with short proof size from the DDH assumption over pairing-free groups. This is the first PP-NIZK that achieves a short proof size from a weak and static DH-type assumption such as DDH. Similarly to the above DP-NIZK, the proof size is $$|C|+\mathsf {poly}(\kappa )$$|C|+poly(κ). This too serves as a solution to the open problem posed by Kim and Wu (CRYPTO’18).
Along the way, we construct two new homomorphic authentication (HomAuth) schemes which may be of independent interest.

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

Simple and Generic Constructions of Succinct Functional Encryption
Abstract

We propose simple and generic constructions of succinct functional encryption. Our key tool is exponentially-efficient indistinguishability obfuscator (XIO), which is the same as indistinguishability obfuscator (IO) except that the size of an obfuscated circuit (or the running-time of an obfuscator) is slightly smaller than that of a brute-force canonicalizer that outputs the entire truth table of a circuit to be obfuscated. A “compression factor” of XIO indicates how much XIO compresses the brute-force canonicalizer. In this study, we propose a significantly simple framework to construct succinct functional encryption via XIO and show that XIO is a powerful enough to achieve cutting-edge cryptography. In particular, we prove the followings:Single-key weakly succinct secret-key functional encryption (SKFE) is constructed from XIO (even with a bad compression factor) and one-way function.Single-key weakly succinct public-key functional encryption (PKFE) is constructed from XIO with a good compression factor and public-key encryption.Single-key weakly succinct PKFE is constructed from XIO (even with a bad compression factor) and identity-based encryption.
Our new framework has side benefits. Our constructions do not rely on any number theoretic or lattice assumptions such as decisional Diffie-Hellman and learning with errors assumptions. Moreover, all security reductions incur only polynomial security loss. Known constructions of weakly succinct SKFE or PKFE from XIO with polynomial security loss rely on number theoretic or lattice assumptions.

2016

JOFC

2012

ASIACRYPT

#### Program Committees

- Crypto 2019
- PKC 2018

#### Coauthors

- Masayuki Abe (5)
- Nuttapong Attrapadung (2)
- Nir Bitansky (1)
- Nishanth Chandran (2)
- Melissa Chase (4)
- Bernardo David (5)
- Dennis Hofheinz (1)
- Shuichi Katsumata (1)
- Fuyuki Kitagawa (2)
- Markulf Kohlweiss (4)
- Feng-Hao Liu (2)
- Toshihide Matsuda (1)
- Takahiro Matsuda (2)
- Miyako Ohkubo (5)
- Jiaxin Pan (1)
- Alain Passelègue (1)
- Samuel Ranellucci (1)
- Keisuke Tanaka (3)
- Alain Tapp (1)
- Daniel Wichs (4)
- Keita Xagawa (4)
- Shota Yamada (3)
- Takashi Yamakawa (4)
- Mark Zhandry (2)