Program
- Encoding Predicates by Arithmetic Circuits and Its Applications (Shuich Katsumata)
- Threshold Cryptosystems From Threshold Fully Homomorphic Encryption (Sam Kim)
- Notes On GGH13 Without The Presence Of Ideals (Alex Davidson)
- Constrained PRF for NC1 in Traditional Groups (Takashi Yamakawa)
Abstracts
Encoding Predicates by Arithmetic Circuits and Its Applications
Shuich Katsumata (The University of Tokyo)
Predicates are used in cryptography as a fundamental tool to control the disclosure of secrets. However, how to embed a particular predicate into a cryptographic primitive is usually not given much attention. In this work, we formalize the idea of encoding predicates as arithmetic circuits and observe that choosing the right encoding of a predicate may lead to an improvement in many aspects such as the efficiency of a scheme or the required hardness assumption. In particular, we develop several predicate encoding schemes with different properties and construct cryptographic primitives that benefit from these: verifiable random functions (VRFs) and predicate encryption (PE) schemes for simple policies.
Threshold Cryptosystems From Threshold Fully Homomorphic Encryption
Sam Kim (Stanford University)
We develop a general approach to adding a threshold functionality to a large class of (non-threshold) cryptographic schemes. A threshold functionality enables a secret key to be split into a number of shares, so that only a threshold of parties can use the key, without reconstructing the key. We begin by constructing a threshold fully-homomorphic encryption scheme (TFHE) from the learning with errors (LWE) problem. We next introduce a new concept, called a universal thresholdizer, from which many threshold systems are possible. We show how to construct a universal thresholdizer from our TFHE. A universal thresholdizer can be used to add threshold functionality to many systems, such as CCA-secure public key encryption (PKE), signature schemes, pseudorandom functions, and others primitives. In particular, by applying this paradigm to a (non-threshold) lattice signature system, we obtain the first single-round threshold signature scheme from LWE.
Joint work with Dan Boneh, Rosario Gennaro, Steven Goldfeder, Aayush Jain, Peter M. R. Rasmussen and Amit Sahai
Notes On GGH13 Without The Presence Of Ideals
Alex Davidson (Royal Holloway)
We investigate the merits of altering the Garg, Gentry and Halevi (GGH13) graded encoding scheme to remove the presence of the ideal ⟨g⟩. In particular, we show that we can alter the form of encodings so that effectively a new gi is used for each source group Gi, while retaining correctness. This would appear to prevent all known attacks on indistinguishability obfuscation (IO) candidates instantiated using GGH13. However, when analysing security in simplified branching program and obfuscation security models, we present branching program (and thus IO) distinguishing attacks that do not use knowledge of ⟨g⟩. This result opens a counterpoint with the work of Halevi (EPRINT 2015) which stated that the core computational hardness problem underpinning GGH13 is computing a basis of this ideal. Our attempts seem to suggest that there is a structural vulnerability in the way that GGH13 encodings are constructed that lies deeper than the presence of ⟨g⟩.
Joint work with Martin Albrecht, Enrique Larraia, Alice Pellet-Mary
Constrained PRF for NC1 in Traditional Groups
Takashi Yamakawa (NTT Secure Platform Laboratories)
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, $\textbf{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 $q$ in 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 $\textbf{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.
Joint work with Nuttapong Attrapadung, Takahiro Matsuda, Ryo Nishimaki, and Shota Yamada