## CryptoDB

### Goichiro Hanaoka

#### Affiliation: AIST

#### 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).

2018

PKC

Fast Lattice Basis Reduction Suitable for Massive Parallelization and Its Application to the Shortest Vector Problem
Abstract

The hardness of the shortest vector problem for lattices is a fundamental assumption underpinning the security of many lattice-based cryptosystems, and therefore, it is important to evaluate its difficulty. Here, recent advances in studying the hardness of problems in large-scale lattice computing have pointed to need to study the design and methodology for exploiting the performance of massive parallel computing environments. In this paper, we propose a lattice basis reduction algorithm suitable for massive parallelization. Our parallelization strategy is an extension of the Fukase–Kashiwabara algorithm (J. Information Processing, Vol. 23, No. 1, 2015). In our algorithm, given a lattice basis as input, variants of the lattice basis are generated, and then each process reduces its lattice basis; at this time, the processes cooperate and share auxiliary information with each other to accelerate lattice basis reduction. In addition, we propose a new strategy based on our evaluation function of a lattice basis in order to decrease the sum of squared lengths of orthogonal basis vectors. We applied our algorithm to problem instances from the SVP Challenge. We solved a 150-dimension problem instance in about 394 days by using large clusters, and we also solved problem instances of dimensions 134, 138, 140, 142, 144, 146, and 148. Since the previous world record is the problem of dimension 132, these results demonstrate the effectiveness of our proposal.

2018

ASIACRYPT

Attribute-Based Signatures for Unbounded Languages from Standard Assumptions
Abstract

Attribute-based signature (ABS) schemes are advanced signature schemes that simultaneously provide fine-grained authentication while protecting privacy of the signer. Previously known expressive ABS schemes support either the class of deterministic finite automata and circuits from standard assumptions or Turing machines from the existence of indistinguishability obfuscations.In this paper, we propose the first ABS scheme for a very general policy class, all deterministic Turing machines, from a standard assumption, namely, the Symmetric External Diffie-Hellman (SXDH) assumption. We also propose the first ABS scheme that allows nondeterministic finite automata (NFA) to be used as policies. Although the expressiveness of NFAs are more restricted than Turing machines, this is the first scheme that supports nondeterministic computations as policies.Our main idea lies in abstracting ABS constructions and presenting the concept of history of computations; this allows a signer to prove possession of a policy that accepts the string associated to a message in zero-knowledge while also hiding the policy, regardless of the computational model being used. With this abstraction in hand, we are able to construct ABS for Turing machines and NFAs using a surprisingly weak NIZK proof system. Essentially we only require a NIZK proof system for proving that a (normal) signature is valid. Such a NIZK proof system together with a base signature scheme are, in turn, possible from bilinear groups under the SXDH assumption, and hence so are our ABS schemes.

2016

CRYPTO

2016

ASIACRYPT

2015

EPRINT

2015

EPRINT

2015

EPRINT

2015

ASIACRYPT

2015

ASIACRYPT

2014

CRYPTO

2012

CRYPTO

2010

EPRINT

Between Hashed DH and Computational DH: Compact Encryption from Weaker Assumption
Abstract

In this paper, we introduce
the intermediate hashed Diffie-Hellman (IHDH) assumption
which is weaker than the hashed DH (HDH) assumption (and thus the decisional DH
assumption),
and is stronger than the computational DH assumption.
We then present two public key encryption schemes with short ciphertexts
which are both chosen-ciphertext secure under this assumption.
The short-message scheme has smaller size of ciphertexts
than Kurosawa-Desmedt (KD) scheme,
and
the long-message scheme is a KD-size scheme with arbitrary plaintext length
which is based on a weaker assumption
than the HDH assumption.

2010

EPRINT

On the Security of Pseudorandomized Information-Theoretically Secure Schemes
Abstract

In this article, we discuss a naive method of randomness reduction for cryptographic schemes, which replaces the required perfect randomness with output distribution of a computationally secure pseudorandom generator (PRG). We propose novel ideas and techniques for evaluating the indistinguishability between the random and pseudorandom cases, even against an adversary with computationally unbounded attack algorithm. Hence the PRG-based randomness reduction can be effective even for information-theoretically secure cryptographic schemes, especially when the amount of information received by the adversary is small. In comparison to a preceding result of Dubrov and Ishai (STOC 2006), our result removes the requirement of generalized notion of ``nb-PRGs'' and is effective for more general kinds of protocols. We give some numerical examples to show the effectiveness of our result in practical situations, and we also propose a further idea for improving the effect of the PRG-based randomness reduction.

2008

ASIACRYPT

2008

EPRINT

Efficient Chosen Ciphertext Secure Public Key Encryption under the Computational Diffie-Hellman Assumption
Abstract

Recently Cash, Kiltz, and Shoup showed a variant of the Cramer-Shoup (CS) public key encryption (PKE) scheme whose chosen-ciphertext (CCA) security relies on the computational Diffie-Hellman (CDH) assumption. The cost for this high security is that the size of ciphertexts is much longer than the CS scheme. In this paper, we show how to achieve CCAsecurity under the CDH assumption without increasing the size of ciphertexts. We further show a more efficient scheme under the hashed Diffie-Hellman (HDH) assumption such that the size of ciphertexts is the same as that of the Kurosawa-Desmedt (KD) scheme. Note that the CDH and HDH assumptions are weaker than the decisional Diffie-Hellman assumption which the CS and KD schemes rely on. Both of our schemes are based on a certain broadcast encryption (BE) scheme while the Cash-Kiltz-Shoup scheme is based on a different paradigm which is called the Twin DH problem.
As an independent interest, we also show a generic method of constructing CCA-secure PKE schemes from BE schemes such that the existing CCA-secure constructions can be viewed as special cases.

2007

EPRINT

Formal Security Treatments for IBE-to-Signature Transformation: Relations among Security Notions
Abstract

In a seminal paper of identity based encryption (IBE), Boneh and Franklin [BF01] mentioned an interesting transform from an IBE scheme to a signature scheme, which was observed by Moni Naor. In this paper, we give formal security treatments for this transform and discover several implications and separations among security notions of IBE and transformed signature. For example, we show for such a successful transform, one-wayness of IBE is an essential condition. Additionally, we give a sufficient and necessary condition for converting a semantically secure IBE scheme into an existentially unforgeable signature scheme. Our results help establish strategies on design and automatic security proof of signature schemes from (possibly weak) IBE schemes. We also show some separation results which strongly support that one-wayness, rather than semantic security, of IBE captures an essential condition to achieve secure signature.

2006

EPRINT

A Generic Construction of CCA-Secure Cryptosystems without NIZKP for a Bounded Number of Decryption Queries
Abstract

In this paper, we propose a generic construction of chosen-ciphertext secure cryptosystems against adversaries with a bounded number of decrytion queries from arbitrary semantically secure encryption in a black box manner. Our construction is not only an alternative to the previously known technique, i.e. the Naor-Yung paradigm, but also has some interesting properties. Especially, (1) it does not require non-interactive zero-knowledge proof, and (2) its component ciphertexts can be compressed into only one if the underlying encryption has a certain homomorphic property. Consequently, when applying our construction to the ElGamal encryption, ciphertext overhead of the resulting scheme will be only one group element which is considered optimal since it is the same as the original ElGamal. Disadvantages to previous schemes are that the upper bound of the number of decryption queries (e.g. 2^{30}) has to be known before set-up phase, and the size of public key is large.

2005

EPRINT

Relations Among Notions of Security for Identity Based Encryption Schemes
Abstract

Identity based encryption (IBE) schemes have been flourishing since the very beginning of this century. In IBE it is widely believed that proving the security of a scheme in the sense of IND-ID-CCA2 is sufficient to claim the scheme is also secure in the senses of both SS-ID-CCA2 and NM-ID-CCA2. The justification for this belief is the relations among indistinguishability (IND), semantic security (SS) and non-malleability (NM). But these relations are proved only for conventional public key encryption (PKE) schemes in historical works. The fact is that between IBE and PKE, there exists a difference of special importance, i.e. only in IBE the adversaries can perform a particular attack, namely the chosen identity attack.
This paper shows that security proved in the sense of IND-ID-CCA2 is validly sufficient for implying security in any other sense in IBE. This is to say the security notion, IND-ID-CCA2, captures the essence of security for all IBE schemes. To achieve this intention, we first describe formal definitions of the notions of security for IBE, and then present the relations among IND, SS and NM in IBE, along with rigorous proofs. All of these results are proposed with the consideration of the chosen identity attack.

2005

EPRINT

Efficient Identity-Based Encryption with Tight Security Reduction
Abstract

In a famous paper of Crypto'01, Boneh and Franklin proposed the first identity-based encryption scheme (IBE), around fifteen years after the concept was introduced by Shamir. Their scheme security (more precisely, the notion of resistance against an IND-ID-CCA attacker) relies in the random oracle model. However, the reduction is far from being tight, and notably depends on the number of extractions queries.
In this paper, we present an efficient modification to the Boneh-Franklin scheme that provides a tight reduction. Our scheme is basically an IBE under two keys, one of which is (randomly) detained by the recipient. It can be viewed as a continuation of an idea introduced by Katz and Wang; we will however show how our construction improves this last scheme.
Our scheme features a tight reduction to the list bilinear Diffie-Hellman (LBDH) problem, which can be itself reduced tightly either to the gap bilinear Diffie-Hellman (GBDH) or the decisional bilinear Diffie-Hellman (DBDH) problems. Furthermore, for a relaxed notion of tightness (called weak-tightness) that we introduce and discuss in our paper, we show that there is a weakly tight reduction from our scheme to the computational bilinear Diffie-Hellman (CBDH) problem.
Our scheme is very efficient, as one can precompute most of the quantity involved in the encryption process. Furthermore, the ciphertext size is very short: for proposed parameters, they are |M|+330 bits long.

2004

EPRINT

Identity-Based Hierarchical Strongly Key-Insulated Encryption and Its Application
Abstract

In this paper, we discuss non-interactive updating of decryption keys in identity-based encryption (IBE). IBE is a public key cryptosystem where a public key is an arbitrary string. In practice, key revocation is a necessary and inevitable process and IBE is no exception when it comes to having to manage revocation of decryption keys without losing its merits in efficiency. Our main contribution of this paper is to propose novel constructions of IBE where the decryption key can be renewed without having to make changes to its public key, i.e. user's identity. We achieve this by tactfully extending the hierarchical IBE (HIBE). Regarding security, we address semantic security against adaptive chosen cipher-text attack for a very strong attack environment that models all possible types of key exposures in the random oracle model. Straightforward extension of the HIBE, however, does not achieve our goal and such scheme is completely insecure under our attack model. In addition to this, we show method of constructing (partially collusion resistant) HIBE from arbitrary IBE in the random oracle model. By combining these results, we can construct an IBE with non-interactive key update from only an arbitrary IBE.

2003

EPRINT

On the Security of Multiple Encryption or CCA-security+CCA-security=CCA-security?
Abstract

In a practical system, a message is often encrypted more than once
by different encryptions, here called multiple encryption, to
enhance its security. Additionally, new features may be achieved
by multiple encrypting a message for a scheme, such as the
key-insulated cryptosystems \cite{DKXY02} and anonymous channels
\cite{Cha81}. Intuitively, a multiple encryption should remain
``secure'', whenever there is one component cipher unbreakable in
it. In NESSIE's latest Portfolio of recommended cryptographic
primitives (Feb. 2003), it is suggested to use multiple encryption
with component ciphers based on different assumptions to acquire
long term security. However, in this paper we show this needs
careful discussion. Especially, this may \emph{not} be true
according to (adaptive) chosen ciphertext attack ({\sf CCA}), even
with all component ciphers {\sf CCA} secure. We define an extended
version of {\sf CCA} called \emph{chosen ciphertext attack for
multiple encryption} ({\sf ME-CCA}) to emulate real world partial
breaking of assumptions, and give constructions of multiple
encryption satisfying {\sf ME-CCA} security. Since {\sf CCA}
security seems so stringent, we further relax it by introducing
\emph{weak} {\sf ME-CCA} ({\sf ME-wCCA}), and prove {\sf
IND-ME-wCCA} secure multiple encryption can be acquired from {\sf
IND-gCCA} secure component ciphers. We also study the relation of
various security notions for multiple encryption. We then apply
these results to key-insulated cryptosystem. It is only previously
known in \cite{DKXY02} that a generic construction exists provably
secure against {\sf CPA} attack, however, we prove that this
generic construction is in fact secure against {\sf ME-wCCA} by
choosing all components {\sf IND-CCA} secure. We also give an
efficient generic construction of key-insulated cryptosystem,
which is so far the \emph{first} generic construction provably
secure against {\sf CCA} (in the random oracle model).

1999

ASIACRYPT

#### Program Committees

- Asiacrypt 2018
- Eurocrypt 2016
- PKC 2015
- Crypto 2013
- Asiacrypt 2009
- PKC 2004

#### Coauthors

- Nuttapong Attrapadung (12)
- Benoît Chevallier-Mames (1)
- Ronald Cramer (1)
- Yang Cui (2)
- Keita Emura (3)
- Eiichiro Fujisaki (1)
- Jun Furukawa (1)
- Takeshi Gomi (1)
- Yumiko Hanaoka (4)
- Dennis Hofheinz (1)
- Hideki Imai (16)
- Ai Ishida (1)
- Tetsuya Izu (1)
- Kenji Kashiwabara (1)
- Shuichi Katsumata (1)
- Yutaka Kawai (1)
- Eike Kiltz (1)
- Fuyuki Kitagawa (1)
- Hirotaka Komaki (1)
- Noboru Kunihiro (8)
- Kaoru Kurosawa (3)
- Takahiro Matsuda (16)
- Kanta Matsuura (3)
- Takao Murakami (1)
- Takashi Nishide (1)
- Tsuyoshi Nishioka (1)
- Koji Nuida (2)
- Satsuya Ohata (1)
- Kazuo Ohta (1)
- Go Ohtake (1)
- Eiji Okamoto (1)
- Rafael Pass (1)
- Yusuke Sakai (4)
- Yumi Sakemi (1)
- Bagus Santoso (1)
- Jacob C. N. Schuldt (3)
- Abhi Shelat (1)
- Junji Shikata (8)
- Kazumasa Shinagawa (1)
- Kenta Takahashi (1)
- Masahiko Takenaka (1)
- Keisuke Tanaka (4)
- Tadanori Teruya (1)
- Vinod Vaikuntanathan (1)
- Yuyu Wang (2)
- Yuji Watanabe (1)
- Jian Weng (1)
- Shota Yamada (13)
- Takashi Yamakawa (3)
- Peng Yang (1)
- Masaya Yasuda (1)
- Rui Zhang (5)
- Zongyang Zhang (1)
- Yunlei Zhao (1)
- Yuliang Zheng (4)