## CryptoDB

### Tatsuaki Okamoto

#### Affiliation: NICT, JP

#### Publications

**Year**

**Venue**

**Title**

2019

PKC

Efficient Attribute-Based Signatures for Unbounded Arithmetic Branching Programs
Abstract

This paper presents the first attribute-based signature (ABS) scheme in which the correspondence between signers and signatures is captured in an arithmetic model of computation. Specifically, we design a fully secure, i.e., adaptively unforgeable and perfectly signer-private ABS scheme for signing policies realizable by arithmetic branching programs (ABP), which are a quite expressive model of arithmetic computations. On a more positive note, the proposed scheme places no bound on the size and input length of the supported signing policy ABP’s, and at the same time, supports the use of an input attribute for an arbitrary number of times inside a signing policy ABP, i.e., the so called unbounded multi-use of attributes. The size of our public parameters is constant with respect to the sizes of the signing attribute vectors and signing policies available in the system. The construction is built in (asymmetric) bilinear groups of prime order, and its unforgeability is derived in the standard model under (asymmetric version of) the well-studied decisional linear (DLIN) assumption coupled with the existence of standard collision resistant hash functions. Due to the use of the arithmetic model as opposed to the boolean one, our ABS scheme not only excels significantly over the existing state-of-the-art constructions in terms of concrete efficiency, but also achieves improved applicability in various practical scenarios. Our principal technical contributions are (a) extending and refining the techniques of Okamoto and Takashima [PKC 2011, PKC 2013], which were originally developed in the context of boolean span programs, to the arithmetic setting; and (b) innovating new ideas to allow unbounded multi-use of attributes inside ABP’s, which themselves are of unbounded size and input length.

2018

PKC

Full-Hiding (Unbounded) Multi-input Inner Product Functional Encryption from the k-Linear Assumption
Abstract

This paper presents two non-generic and practically efficient private key multi-input functional encryption (MIFE) schemes for the multi-input version of the inner product functionality that are the first to achieve simultaneous message and function privacy, namely, the full-hiding security for a non-trivial multi-input functionality under well-studied cryptographic assumptions. Our MIFE schemes are built in bilinear groups of prime order, and their security is based on the standard k-Linear (k-LIN) assumption (along with the existence of semantically secure symmetric key encryption and pseudorandom functions). Our constructions support polynomial number of encryption slots (inputs) without incurring any super-polynomial loss in the security reduction. While the number of encryption slots in our first scheme is apriori bounded, our second scheme can withstand an arbitrary number of encryption slots. Prior to our work, there was no known MIFE scheme for a non-trivial functionality, even without function privacy, that can support an unbounded number of encryption slots without relying on any heavy-duty building block or little-understood cryptographic assumption.

2018

ASIACRYPT

Adaptively Simulation-Secure Attribute-Hiding Predicate Encryption
Abstract

This paper demonstrates how to achieve simulation-based strong attribute hiding against adaptive adversaries for predicate encryption (PE) schemes supporting expressive predicate families under standard computational assumptions in bilinear groups. Our main result is a simulation-based adaptively strongly partially-hidingPE (PHPE) scheme for predicates computing arithmetic branching programs (ABP) on public attributes, followed by an inner-product predicate on private attributes. This simultaneously generalizes attribute-based encryption (ABE) for boolean formulas and ABP’s as well as strongly attribute-hiding PE schemes for inner products. The proposed scheme is proven secure for any a priori bounded number of ciphertexts and an unbounded (polynomial) number of decryption keys, which is the best possible in the simulation-based adaptive security framework. This directly implies that our construction also achieves indistinguishability-based strongly partially-hiding security against adversaries requesting an unbounded (polynomial) number of ciphertexts and decryption keys. The security of the proposed scheme is derived under (asymmetric version of) the well-studied decisional linear (DLIN) assumption. Our work resolves an open problem posed by Wee in TCC 2017, where his result was limited to the semi-adaptive setting. Moreover, our result advances the current state of the art in both the fields of simulation-based and indistinguishability-based strongly attribute-hiding PE schemes. Our main technical contribution lies in extending the strong attribute hiding methodology of Okamoto and Takashima [EUROCRYPT 2012, ASIACRYPT 2012] to the framework of simulation-based security and beyond inner products.

2015

ASIACRYPT

2010

CRYPTO

2010

EUROCRYPT

2010

EPRINT

Fully Secure Functional Encryption: Attribute-Based Encryption and (Hierarchical) Inner Product Encryption
Abstract

In this paper, we present two fully secure functional encryption schemes. Our first result is a fully secure attribute-based encryption (ABE) scheme. Previous constructions of ABE were only proven to be selectively secure. We achieve full security by adapting the dual system encryption methodology recently introduced by Waters and previously leveraged to obtain fully secure IBE and HIBE systems. The primary challenge in applying dual system encryption to ABE is the richer structure of keys and ciphertexts. In an IBE or HIBE system, keys and ciphertexts are both associated with the same type of simple object: identities. In an ABE system, keys and ciphertexts are associated with more complex objects: attributes and access formulas. We use a novel information-theoretic argument to adapt the dual system encryption methodology to the more complicated structure of ABE systems. We construct our system in composite order bilinear groups, where the order is a product of three primes. We prove the security of our system from three static assumptions. Our ABE scheme supports arbitrary monotone access formulas.
Our second result is a fully secure (attribute-hiding) predicate encryption (PE) scheme for inner-product predicates. As for ABE, previous constructions of such schemes were only proven to be selectively secure. Security is proven under a non-interactive assumption whose size does not depend on the number of queries. The scheme is comparably efficient to existing selectively secure schemes. We also present a fully secure hierarchical PE scheme under the same assumption. The key technique used to obtain these results is an elaborate combination of the dual system encryption methodology (adapted to the structure of inner product PE systems) and a new approach on bilinear pairings using the notion of dual pairing vector spaces (DPVS) proposed by Okamoto and Takashima.

2007

EPRINT

Authenticated Key Exchange and Key Encapsulation Without Random Oracles
Abstract

This paper presents a new paradigm to realize cryptographic primitives such as authenticated key exchange and key encapsulation
without random oracles under three assumptions: the decisional Diffie-Hellman (DDH) assumption, target collision resistant (TCR) hash functions and a class of pseudo-random functions (PRFs), {\pi}PRFs, PRFs with pairwise-independent random sources. We propose a (PKI-based) two-pass authenticated key exchange (AKE) protocol that is comparably as efficient as the existing most efficient protocols like MQV and that is secure without random oracles (under these assumptions). Our protocol is shown to be secure in the (currently) strongest security definition, the extended Canetti-Krawczyk (eCK) security definition introduced by LaMacchia, Lauter and Mityagin. We also show that a variant of the Kurosawa-Desmedt key encapsulation mechanism (KEM) using a {\pi}PRF is CCA-secure. This scheme is secure in a stronger security notion, the chosen public-key and ciphertext attack (CPCA) security, with using generalized TCR (GTCR) hash functions. The proposed schemes in this paper are redundancy-free (or validity-check-free) and the implication is that combining them with redundancy-free symmetric encryption (DEM) will yield redundancy-free (e.g., MAC-free) CCA-secure hybrid encryption.

2006

EPRINT

Efficient Blind and Partially Blind Signatures Without Random Oracles
Abstract

This paper proposes a new efficient signature scheme from bilinear maps that is secure in the standard model (i.e., without the random oracle model). Our signature scheme is more effective in many applications (e.g., blind signatures, group signatures, anonymous credentials etc.) than the existing secure signature schemes in the standard model. As typical applications of our signature scheme, this paper presents efficient blind signatures and partially blind signatures that are secure in the standard model. Here, partially blind signatures are a generalization of blind signatures (i.e., blind signatures are a special case of partially blind signatures) and have many applications including electronic cash and voting. Our blind signature scheme is much more efficient than the existing secure blind signature schemes in the standard model such as the Camenisch-Koprowski-Warinsch and Juels-Luby-Ostrovsky schemes, and is also almost as efficient as the most efficient blind signature schemes whose security has been analyzed heuristically or in the random oracle model. Our partially blind signature scheme is the first one that is secure in the standard model and it is very efficient (as efficient as our blind signatures). The security proof of our blind and partially blind signature schemes requires the 2SDH assumption, a variant of the SDH assumption introduced by Boneh and Boyen, and the 2SDH-IND assumption. This paper also presents an efficient way to convert our (partially) blind signature scheme in the standard model to a scheme secure for a concurrent run of users in the common reference string (CRS) model. Finally, we present a blind signature scheme based on the Waters signature scheme.

2006

EPRINT

On the Equivalence of Several Security Notions of Key Encapsulation Mechanism
Abstract

KEM (Key Encapsulation Mechanism) was introduced by Shoup to formalize the asymmetric encryption specified for key distribution in ISO standards on public-key encryption. Shoup defined the ``semantic security (IND) against adaptively chosen ciphertext attacks (CCA2)'' as a desirable security notion of KEM. This paper introduces ''non-malleability (NM)'' of KEM, a stronger security notion than IND. We provide three definitions of NM, and show that these three definitions are equivalent. We then show that NM-CCA2 KEM is equivalent to IND-CCA2 KEM. That is, we show that NM is equivalent to IND under CCA2 attacks, although NM is stronger than IND in the definition (or under some attacks like CCA1). In addition, this paper defines the universally composable (UC) security of KEM and shows that NM-CCA2 KEM is equivalent to UC KEM.

2003

EPRINT

Resource Bounded Unprovability of Computational Lower Bounds
Abstract

This paper introduces new notions of asymptotic proofs, PT(polynomial-time)-extensions, PTM(polynomial-time Turing machine)-$\omega$-consistency, etc. on formal theories of arithmetic including PA (Peano Arithmetic). An asymptotic proof is a set of infinitely many formal proofs, which is introduced to define and characterize a property, PTM-$\omega$-consistency, of a formal theory. Informally speaking, PTM-$\omega$-consistency is a {\it polynomial-time bounded} version (in asymptotic proofs) of $\omega$-consistency, and characterized in two manners: (1) (in the light of the {\it extension of PTM to TM}) the resource {\it unbounded} version of PTM-$\omega$-consistency is equivalent to $\omega$-consistency, and (2) (in the light of {\it asymptotic proofs by PTM})
a PTM-$\omega$-{\it inconsistent} theory includes an axiom that only a super-polynomial-time Turing machine can prove asymptotically over PA, under some assumptions. This paper shows that {\it P$\not=$NP (more generally, any super-polynomial-time lower bound in PSPACE) is unprovable in a PTM-$\omega$-consistent theory $T$}, where $T$ is a consistent PT-extension of PA (although this paper does not show that P$\not=$NP is unprovable in PA, since PA has not been proven to be PTM-$\omega$-consistent). This result implies that to prove P$\not=$NP by any technique requires a PTM-$\omega$-{\it inconsistent} theory, which should include an axiom that only a super-polynomial-time machine can prove asymptotically over PA (or implies a super-polynomial-time computational upper bound) under some assumptions. This result is a kind of generalization of the result of ``Natural Proofs'' by Razborov and Rudich, who showed that to prove ``P$\not=$NP'' by a class of techniques called ``Natural Proofs'' implies a super-polynomial-time (e.g., sub-exponential-time) algorithm that can break a typical cryptographic primitive, a pseudo-random generator. Our result also implies that any relativizable proof of P$\not=$NP requires the {\it resource unbounded version} of \PTM-$\omega$-{\it inconsistent} theory, $\omega$-{\it inconsistent} theory, which suggests another negative result by Baker, Gill and Solovay that no relativizable proof can prove ``P$\not=$NP'' in PA, which is a $\omega$-consistent theory.
Therefore, our result gives a unified view to the existing two major negative results on proving P$\not=$NP, Natural Proofs and relativizable proofs, through the two manners of characterization of PTM-$\omega$-consistency. We also show that the PTM-$\omega$-consistency of $T$ cannot be proven in any PTM-$\omega$-consistent theory $S$, where $S$ is a consistent PT-extension of $T$. That is, to prove the independence of P vs NP from $T$ by proving the PTM-$\omega$-consistency of $T$ requires a PTM-$\omega$-{\it inconsistent} theory, or implies a super-polynomial-time computational upper bound under some assumptions. This seems to be related to the results of Ben-David and Halevi and Kurz, O'Donnell and Royer, who showed that to prove the independence of P vs NP from PA using any currently known mathematical paradigm implies an extremely-close-to-polynomial-time (but still super-polynomial-time) algorithm that can solve NP-complete problems. Based on this result, we show that {\it the security of any computational cryptographic scheme is unprovable} in the setting where adversaries and provers are modeled as polynomial-time Turing machines and only a PTM-$\omega$-consistent theory is allowed to prove the security.

2000

EPRINT

RSA-OAEP is Secure under the RSA Assumption
Abstract

Recently Victor Shoup noted that there is a gap in
the widely-believed security result of OAEP against adaptive
chosen-ciphertext attacks. Moreover, he showed that,
presumably,
OAEP cannot be proven secure from the {\it one-wayness}
of the underlying trapdoor permutation.
This paper establishes another result on the security
of OAEP. It proves that OAEP offers semantic security
against adaptive chosen-ciphertext attacks,
in the random oracle model, under the {\it partial-domain}
one-wayness of the underlying permutation.
Therefore, this uses a formally stronger assumption.
Nevertheless, since partial-domain one-wayness of the RSA function
is equivalent to its (full-domain) one-wayness, it follows that
the security of RSA--OAEP can actually
be proven under the sole RSA assumption, although
the reduction is not tight.

1998

EUROCRYPT

1992

CRYPTO

1992

CRYPTO

1990

EUROCRYPT

1989

CRYPTO

1989

EUROCRYPT

#### Program Committees

- TCC 2019
- Asiacrypt 2017
- PKC 2016
- Asiacrypt 2016
- Asiacrypt 2015
- PKC 2013
- Crypto 2012
- Asiacrypt 2012
- Eurocrypt 2011
- Eurocrypt 2010
- TCC 2008
- Asiacrypt 2008
- PKC 2007
- Eurocrypt 2005
- PKC 2005
- Crypto 2004
- Crypto 2003
- PKC 2003
- Crypto 2002
- Crypto 2001
- PKC 2001
- Asiacrypt 2000
- PKC 2000
- PKC 1999
- PKC 1998
- Crypto 1997
- Eurocrypt 1996
- Eurocrypt 1994
- Asiacrypt 1994
- Crypto 1993
- Eurocrypt 1992

#### Coauthors

- Masayuki Abe (5)
- Allison Bishop (2)
- David Chaum (1)
- Giovanni Di Crescenzo (1)
- Ivan Damgård (1)
- Pratish Datta (3)
- Tony Eng (1)
- Atsushi Fujioka (5)
- Eiichiro Fujisaki (8)
- Oded Goldreich (1)
- Ryotaro Hayashi (1)
- Ryo Hiromasa (1)
- Ryo Kashima (1)
- Eike Kiltz (2)
- Susumu Kiyoshima (1)
- Kenji Koyama (2)
- Kaoru Kurosawa (1)
- Yoshifumi Manabe (3)
- Ueli Maurer (1)
- Shoji Miyaguchi (1)
- Waka Nagao (2)
- Kazuo Ohta (12)
- Choonsik Park (1)
- Giuseppe Persiano (1)
- Krzysztof Pietrzak (2)
- David Pointcheval (4)
- Amit Sahai (2)
- Kouichi Sakurai (2)
- Alfredo De Santis (1)
- Hiroki Shizuya (1)
- Jacques Stern (4)
- Katsuyuki Takashima (10)
- Keisuke Tanaka (2)
- Junichi Tomida (1)
- Shigeo Tsujii (1)
- Shigenori Uchiyama (3)
- Scott A. Vanstone (1)
- Brent Waters (4)
- Daniel Wichs (2)
- Avi Wigderson (1)
- Moti Yung (2)