http://www.ntt.co.jp/sc/event_e/event20190705.html
Program
- 10:30 - 11:30 CCA Security and Trapdoor Functions via Key-Dependent-Message Security (Takahiro Matsuda)
- 12:45 - 13:45 Multi-Client Functional Encryption for Inner Products (Romain Gay)
- 14:00 - 15:00 Attribute Based Encryption (and more) for Nondeterministic Finite Automata from LWE (Shota Yamada)
- 15:10 - 16:10 Unbounded Dynamic Predicate Compositions in Attribute-based Encryption (Nuttapong Attrapadung)
Abstracts
CCA Security and Trapdoor Functions via Key-Dependent-Message Security
Takahiro Matsuda (AIST)
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 constant-noise learning-parity-with-noise (LPN) problem.
This is joint work with Fuyuki Kitagawa and Keisuke Tanaka. Full paper: https://eprint.iacr.org/2019/291
Multi-Client Functional Encryption for Inner Products
Romain Gay (UC Berkley)
I will talk about Multi-Client Functional Encryption for inner products, where multiple parties, owning data that have to be frequently updated, agree to share weighted sums of these data with some aggregator, without revealing their individual data, and without trusting each other.
More specifically, I’ll present [Chotard, Dufour-Sans, Gay, Phan, Poincheval 18], where we combine techniques from Private Stream Aggregation (PSA) and Functional Encryption (FE), to introduce a primitive we call Decentralized Multi-Client Functional Encryption (DMCFE), for which we give a practical instantiation for Inner Product functionalities.
This primitive allows various senders to non-interactively generate ciphertexts which support inner-product evaluation, with functional decryption keys that can also be generated non-interactively, in a distributed way, among the senders. Interactions are required during the setup phase only.
Then I’ll present the follow up work of [Abdalla, Benhamouda, Gay 19] which presents a new generic construction of multi-client functional encryption (MCFE) for inner products from single-input functional inner-product encryption and standard pseudorandom functions. In spite of its simplicity, the new construction supports labels, achieves security in the standard model under adaptive corruptions, and can be instantiated from the plain DDH, LWE, and Paillier assumptions.
Attribute Based Encryption (and more) for Nondeterministic Finite Automata from LWE
Shota Yamada (AIST)
Constructing Attribute Based Encryption (ABE) [SW05] for uniform models of computation, i.e. with intrinsic support for unbounded length inputs, from standard assumptions is an important problem, about which very little is known. The only known ABE scheme in this setting that i) avoids reliance on multilinear maps or indistinguishability obfuscation, ii) supports unbounded length inputs and iii) permits unbounded key requests to the adversary in the security game, are by Waters from Crypto, 2012 [Wat12] and its variants. Waters provides the first ABE for Deterministic Finite Automata (DFA) satisfying the above properties, from a parametrized or “q-type” assumption over bilinear maps. Generalizing this construction to Nondeterministic Finite Automata (NFA) was left as an explicit open problem in the same work, and has seen no progress to date. Constructions from other assumptions such as more standard pairing based assumptions, or lattice based assumptions has also proved elusive.
In this work, we construct the first symmetric key attribute based encryption scheme for nondeterministic finite automata (NFA) from the learning with errors (LWE) assumption. Our scheme supports unbounded length inputs as well as unbounded length machines. In more detail, secret keys in our construction are associated with an NFA M of unbounded length, ciphertexts are associated with a tuple (x;m) where x is a public attribute of unbounded length and m is a secret message bit, and decryption recovers m if and only if M(x) = 1.
Further, we leverage our ABE to achieve (restricted notions of) attribute hiding analogous to the circuit setting, obtaining the first predicate encryption and bounded key functional encryption schemes for NFA from LWE. We achieve machine hiding in the single/bounded key setting to obtain the first reusable garbled NFA from standard assumptions. In terms of lower bounds, we show that secret key functional encryption even for DFAs, with security against unbounded key requests implies indistinguishability obfuscation (iO) for circuits; this suggests a barrier in achieving full fledged functional encryption for NFA.
Unbounded Dynamic Predicate Compositions in Attribute-based Encryption
Nuttapong Attrapadung (AIST)
We present several transformations that combine a set of attribute-based encryption (ABE) schemes for simpler predicates into a new ABE scheme for more expressive composed predicates. Previous proposals for predicate compositions of this kind, the most recent one being that of Ambrona et.al. at Crypto'17, can be considered static (or partially dynamic), meaning that the policy (or its structure) that specifies a composition must be fixed at the setup. Contrastingly, our transformations are dynamic and unbounded: they allow a user to specify an arbitrary and unbounded-size composition policy right into his/her own key or ciphertext. We propose transformations for three classes of composition policies, namely, the classes of any monotone span programs, any branching programs, and any deterministic finite automata. These generalized policies are defined over arbitrary predicates, hence admitting modular compositions. One application from modularity is a new kind of ABE for which policies can be ``nested’’ over ciphertext and key policies. As another application, we achieve the first fully secure completely unbounded key-policy ABE for non-monotone span programs, in a modular and clean manner, under the q-ratio assumption (Agrawal and Chase at Eurocrypt'17).
Our transformations work inside a generic framework for ABE called symbolic pair encoding, proposed by Agrawal and Chase at Eurocrypt'17. Along the way, we also propose a generic way to bundle ABE schemes (without a policy over them, and where each scheme works separately) so that almost all of their parameters can be reused among those ABE schemes. At the core of our transformations, we observe and exploit an unbounded nature of the symbolic property so as to achieve unbounded-size policy compositions.