http://www.ntt.co.jp/sc/event_e/event20191216.html
Program
- 10:30 - 11:30 Indistinguishability Obfuscation Without Multilinear Maps: New Paradigms via Low Degree Weak Pseudorandomness and Security Amplification (Aayush Jain)
- 13:00 - 14:00 Black-Box Language Extension of Non-Interactive Zero-Knowledge Arguments (Miguel Ambrona)
- 14:15 - 15:15 Structure-Preserving and Re-randomizable RCCA-secure Public Key Encryption and its Applications (Antonio Faonio)
- 15:30 - 16:30 On the (In)security of Kilian-Based SNARGs (Fermi Ma)
Abstracts
Indistinguishability Obfuscation Without Multilinear Maps: New Paradigms via Low Degree Weak Pseudorandomness and Security Amplification
Aayush Jain (UCLA)
In this talk, I will be talking about recent advances in constructing indistinguishability obfuscation from LWE, Bilinear maps, and a new falsifiable, succinct and instance independent pseudorandomness assumption. This assumption is closely tied with the hardness of systems of expanding random constant degree polynomial systems with a planted input. I will be giving a broad overview of the following works:
Technically, I will be presenting an amplification theorem for functional encryption which forms a crucial pillar for these works, and time permitting, talk a bit about evidence of hardness for these new assumptions in the form of a sum-of-squares lower bound.
This talk is based upon joint works with Prabhanjan Ananth, Boaz Barak, Sam Hopkins, Pravesh Kothari, Huijia Lin, Christian Matt and Amit Sahai.
Black-Box Language Extension of Non-Interactive Zero-Knowledge Arguments
Miguel Ambrona (NTT Secure Platform Laboratories)
Highly efficient non-interactive zero-knowledge arguments (NIZK) are often constructed for limited languages and it is not known how to extend them to cover wider classes of languages in general. In this paper we initiate a study on black-box language extensions for conjunctive and disjunctive relations, that is, building a NIZK system for $L \diamond \hat{L}$ (with $\diamond \in {\land,\lor}$) based on NIZK systems for languages $L$ and $\hat{L}$. While the conjunctive extension of NIZKs is straightforward by simply executing the given NIZKs in parallel, it is not known how disjunctive extensions could be achieved in a black-box manner. Besides, observe that the simple conjunctive extension does not work in the case of simulation-sound NIZKs (SS-NIZKs), as pointed out by Sahai (Sahai, FOCS 1999). Our main contribution is an impossibility result that negates the existence of the above extensions and implies other non-trivial separations among NIZKs, SS-NIZKs, and labelled SS-NIZKs. Motivated by the difficulty of such transformations, we additionally present an efficient construction of signature schemes based on unbounded simulation-sound NIZKs (USS-NIZKs) for any language without language extensions.
This is a joint work with Masayuki Abe and Miyako Ohkubo.
Structure-Preserving and Re-randomizable RCCA-secure Public Key Encryption and its Applications
Antonio Faonio (IMDEA Software)
Re-randomizable RCCA-secure public key encryption (Rand-RCCA PKE) schemes reconcile the property of re-randomizability of the ciphertexts with the need of security against chosen-ciphertexts attacks.
In this paper we give a new construction of a Rand-RCCA PKE scheme that is perfectly re-randomizable. Our construction is structure-preserving, can be instantiated over Type-3 pairing groups, and achieves better computation and communication efficiency than the state of the art perfectly re-randomizable schemes (e.g., Prabhakaran and Rosulek, CRYPTO'07).
Next, we revive the Rand-RCCA notion showing new applications where our Rand-RCCA PKE scheme plays a fundamental part: (1) We show how to turn our scheme into a publicly-verifiable Rand-RCCA scheme; (2) We construct a malleable NIZK with a (variant of) simulation soundness that allows for re-randomizability; (3) We propose a new UC-secure Verifiable Mix-Net protocol that is secure in the common reference string model. Thanks to the structure-preserving property, all these applications are efficient. Notably, our Mix-Net protocol is the most efficient universally verifiable Mix-Net (without random oracle) where the CRS is an uniformly random string of size independent of the number of senders. The property is of the essence when such protocols are used in large scale.
This is a joint work with Dario Fiore, Javier Herranz, and Carla Ràfols.
On the (In)security of Kilian-Based SNARGs
Fermi Ma (Princeton University)
The Fiat-Shamir transform applied to Kilian’s protocol (and its extension to interactive oracle proofs) is at the heart of both theoretical results as well as practical implementations of highly efficient non-interactive proof systems (e.g., SNARKs and STARKs). In this work, we demonstrate significant obstacles to establishing the soundness of this approach. We exhibit a particular (contrived) interactive oracle proof (IOP) for NP for which Fiat-Shamir is unsound for any concrete hash function and any Merkle tree commitment. We also show that if Kilian’s original protocol for PCPs is instantiated with a particular (contrived) Merkle tree commitment and any “natural” PCP, then the Fiat-Shamir transform cannot be soundly applied using any concrete hash function. Put together, our results suggest that provably-secure PCP/IOP-based SNARGs will require a synergistic choice of the PCP/IOP, the Merkle tree commitment, and Fiat-Shamir hash function.
This is a joint work with James Bartusek, Liron Bronfman, Justin Holmgren, and Ron Rothblum.