Schedule

schedule and talk abstract

The event schedule on December 13th

Abstract

Tracing in Encryption Systems

Brent Waters (NTT Research Inc.)

Abstract: I will first describe a STOC 2018 result that shows collusion resistant traitor tracing with polynomial in lg(N), \lambda size ciphertexts for N users and security parameter \lambda. Then I will talk about some recent and upcoming results in the area.

Securely implementing Gaussian distributions in lattice-based signatures

Mehdi Tibouchi (NTT Secure Platform Laboratories)

Abstract: Candidates for lattice-based signature schemes in the NIST postquantum standardization process have mostly avoided discrete Gaussian distributions (preferring uniform noise instead), despite the better theoretical behavior of Gaussians and the better parameters they allow. This is mostly due to concerns regarding the difficulty of implementing noise sampling and rejection sampling securely when using Gaussians.

In this talk, we discuss previous attacks on insecure implementations of Gaussian-based signature schemes, and describe new techniques to overcome these challenges.

Most of the talk will be based on joint work with Gilles Barthe, Sonia Belaïd, Thomas Espitau, Pierre-Alain Fouque and Mélissa Rossi, addressing the case of signatures based on the Fiat–Shamir transform. If time permits, we will also mention recent results with Alexandre Wallet and others regarding the hash-and-sign setting.

On Black-Box Extensions of Non-Interactive Zero-Knowledge Arguments

Masayuki Abe (NTT Secure Platform Laboratories)

Abstract: 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 talk we explore black-box language extensions for conjunctive and disjunctive relations. Namely, we study about building a NIZK system for L1 # L2 for logical operator # being AND or OR based on NIZK systems for languages L1 and L2. 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.

Joint work with Miguel Ambrona and Miyako Ohkubo

Compact NIZKs from Standard Assumptions on Bilinear Maps

Ryo Nishimaki (NTT Secure Platform Laboratories)

Abstract: A non-interactive zero-knowledge (NIZK) protocol enables a prover to convince a verifier of the truth of a statement without leaking any other information by sending a single message. The main focus of this work is on exploring short pairing-based NIZKs for all NP languages based on standard assumptions. In this regime, the seminal work of Groth, Ostrovsky, and Sahai (J.ACM’12) (GOS-NIZK) is still considered to be the state-of-the-art. Although fairly efficient, one drawback of GOS-NIZK is that the proof size is multiplicative in the circuit size computing the NP relation. That is, the proof size grows by $O(|C|k)$, where $C$ is the circuit for the NP relation and $k$ is the security parameter. By now, there have been numerous follow-up works focusing on shortening the proof size of pairing-based NIZKs, however, thus far, all works come at the cost of relying either on a non-standard knowledge-type assumption or a non-static $q$-type assumption. Specifically, improving the proof size of the original GOS-NIZK under the same standard assumption has remained as an open problem.

Our main result is a construction of a pairing-based NIZK for all of NP whose proof size is additive in $|C|$, that is, the proof size only grows by $|C| + poly(k)$, based on the decisional linear (DLIN) assumption. Since the DLIN assumption is the same assumption underlying GOS-NIZK, our NIZK is a strict improvement on their proof size.

The main building block for all of our NIZKs is a constrained signature scheme with decomposable online-offline efficiency. This is a property which we newly introduce in this paper and construct from the DLIN assumption. We believe this construction is of an independent interest.

Joint work with Shuichi Katsumata, Shota Yamada, and Takshi Yamakawa

Extracting Randomness from Extractor-Dependent Sources

Daniel Wichs (NTT Research Inc.)

Abstract: We revisit the well-studied problem of extracting nearly uniform randomness from an arbitrary source of sufficient min-entropy. Strong seeded extractors solve this problem by relying on a public random seed, which is unknown to the source. Here, we consider a setting where the seed is reused over time and the source may depend on prior calls to the extractor with the same seed. Can we still extract nearly uniform randomness? In more detail, we assume the seed is chosen randomly, but the source can make arbitrary oracle queries to the extractor with the given seed before outputting a sample. We require that the sample has entropy and differs from any of the previously queried values. The extracted output should look uniform even to a distinguisher that gets the seed. We provide constructions and lower bounds for extractors in this setting.

Joint work with Yevgeniy Dodis and Vinod Vaikuntanathan

Finding Collisions in a Quantum World: Quantum Black-Box Separation of Collision-Resistance and One-Wayness

Takashi Yamakawa (NTT Secure Platform Laboratories)

Abstract: Since the celebrated work of Impagliazzo and Rudich (STOC 1989), a number of black-box impossibility results have been established. However, these works only ruled out classical black-box reductions among cryptographic primitives. Therefore it may be possible to overcome these impossibility results by using quantum reductions. To exclude such a possibility, we have to extend these impossibility results to the quantum setting. In this paper, we initiate the study of black-box impossibility in the quantum setting. We first formalize a quantum counterpart of fully-black-box reduction following the formalization by Reingold, Trevisan and Vadhan (TCC 2004). Then we prove that there is no quantum fully-black-box reduction from collision-resistant hash functions to one-way permutations (or even trapdoor permutations). We take both of classical and quantum implementations of primitives into account. This is an extension to the quantum setting of the work of Simon (Eurocrypt 1998) who showed a similar result in the classical setting.

Joint work with Akinori Hosoyamada

Ingredients for securing blockchain and countermeasure against compromise of underlying cryptography

Shin’ichiro Matsuo (NTT Research Inc.)

Abstract: Blockchain technology is expected to provide advanced level of distributed trust. It is basically a kind of cryptographic protocol, but the security analysis of this technology is more complicated than existing cryptographic protocol. For example, game theory and economic incentive is one of the key part in securing blockchain technology. In this talk, we explore how ingredients of blockchain technology help the security of blockchain, then how we can have relief from insecurity caused by compromise of underlying cryptography.

Blockchain-based Smart Contracts: Security Challenges and Correct-by-Design Development

Aron Laszka (NTT Research Inc.)

Abstract: The adoption of blockchain based distributed ledgers is growing fast due to their ability to provide reliability, integrity, and auditability without trusted entities. One of the key capabilities of these emerging platforms is the ability to create self-enforcing smart contracts. However, the development of smart contracts has proven to be error-prone in practice, and as a result, contracts deployed on public platforms are often riddled with security vulnerabilities. This issue is exacerbated by the design of these platforms, which forbids updating contract code and rolling back malicious transactions. In this talk, we first give an overview of key security challenges in smart contract development and existing tools for vulnerability discovery and verification. Then, we introduce VeriSolid, a novel framework for the correct-by-design development of smart contracts. VeriSolid enables developer to specify contracts using a transition-system based model with rigorous operational semantics, to formally verify the specified contracts, and to generate contract code that can be deployed on the Ethereum blockchain platform. Our model-based approach allows developers to reason about contract behavior at a high level of abstraction, which enables the correct-by-design development of smart contracts.

Based on joint work with Anastasia Mavridou, Emmanouela Stachtiari, Keerthi Nelaturu, and Andreas Veneris.

Publicly Verifiable MPC and Applications

Bernardo David (IT University of Copenhagen)

Abstract: Multiparty computation (MPC) allows mutually distrustful parties to perform computation on private inputs without revealing such inputs to each other. Additionally, some flavours of MPC allow the computing parties to either be sure that the computation was successfully completed or that a given party misbehaved. However, these properties usually do not extend to external third parties who wish to publicly verify that a computation succeed or that a party cheated without knowing the inputs. In this talk, we give an overview of two upcoming results on constructing efficient publicly verifiable MPC with cheater identification and compiling certain classes of universally composable (UC) protocols into protocols with public verifiability. Our constructions build on recent results on UC homomorphic commitments and other building blocks that can be efficiently realised. In order to prove our constructions secure, we put forth new notions of UC public verifiability that might be of independent interest. We also discuss applications of our results to constructing financially incentivised MPC and privacy preserving smart contracts, where cheating parties are financially punished and the MPC output determines the distribution of funds.

Based on joint work with Carsten Baum and Rafael Dowsley.

HIBE with Tight Security

Jiaxin Pan (NTNU)

Abstract: Most of the existing hierarchical identity-based encryption (HIBE) schemes have security loss of at least Q, where Q is the number of user secret key queries. Even worse, it has been proved Lewko and Waters (Eurocrypt 2014) that there is a class of HIBEs has to lose a factor of Q^L, where L is the maximum hierarchy depth.

In this talk, I will present the first tightly secure HIBE scheme based on standard assumption, which is from our recent result. At the core of our construction is a MAC scheme for messages of flexible length that allows us to tightly randomize user secret keys of hierarchical identities.

The talk is based on joint work with Roman Langrehr (KIT, Germany).