Picnic is a signature scheme that was designed by cryptographers from several teams and submitted to the post-quantum cryptography standardization project of the National Institute of Standards and Technology (NIST). Among all submissions to NIST's project, Picnic is one of the most innovative, making use of recent progress in construction of practically efficient zero-knowledge protocols. In this talk, I will describe the design of Picnic and analyze its security.

Bluetooth is a widely deployed platform for wireless communications between mobile devices. It uses authenticated Elliptic Curve Diffie-Hellman for its key exchange. We show that the authentication provided by the Bluetooth pairing protocols is insufficient and does not provide the promised MitM protection. We present a new variant of an Invalid Curve Attack that preserves the x-coordinate of the public keys. The attack compromises the encryption keys of all of the current Bluetooth authenticated pairing protocols, provided both paired devices are vulnerable. Specifically, it successfully compromises the encryption keys of 50% of the Bluetooth pairing attempts, while in the other 50% the pairing of the victims is terminated. Finally, we show that most of the Bluetooth market is vulnerable.

Joint work with Eli Biham.

We present a new approach to designing concretely efficient MPC protocols with semi-honest security in the dishonest majority setting. Motivated by the fact that within the dishonest majority setting the efficiency of most practical protocols does not depend on the number of honest parties, we investigate how to construct protocols which improve in efficiency as the number of honest parties increases. Our central idea is to take a protocol which is secure for n-1 corruptions and modify it to use short symmetric keys, with the aim of basing security on the concatenation of all honest parties' keys. This results in a more efficient protocol tolerating fewer corruptions, whilst also introducing an LPN-style syndrome decoding assumption.

Based on a joint work with Emmanuela Orsini, Peter Scholl and Eduardo Soria-Vazquez that appeared in Crypto 2018.

Homomorphic Secret Sharing (HSS) is a form of secret sharing that allows parties to locally evaluate functions on shares, yielding applications to succinct secure computation, private manipulation of remote databases and more. In this talk, we briefly discuss the state of the art in HSS research, focusing on a recent result of Compressing Vector OLE.

Oblivious linear-function evaluation (OLE), and its extension of Vector OLE (VOLE), are secure two-party protocols allowing a receiver to learn a linear combination of a pair of field elements (respectively, of vectors) held by a sender. OLE and VOLE serve as common building blocks in secure computation of arithmetic circuits, analogous to the roles of oblivious transfer (OT) and string OT for boolean circuits.

We suggest a new approach for fast generation of pseudo-random instances of VOLE via a deterministic local expansion of a pair of short correlated seeds and no interaction. This provides the first example of compressing a non-trivial and cryptographically useful correlation with good concrete efficiency.

Our VOLE generators are based on a novel combination of a dual form of HSS (sometimes known as Function Secret Sharing (FSS)) for multi-point functions and variants of the Learning Parity with Noise problem over large fields. We apply our VOLE generators towards efficient secure computation with "silent" preprocessing and non-interactive zero-knowledge proofs with reusable correlated randomness.

Joint work with Geoffroy Couteau, Niv Gilboa, and Yuval Ishai

In this talk we will discuss some new techniques in linear cryptanalysis, that can improve the bias of linear approximations. These techniques can also create some new kinds of linear approximations, that were hard to find previously. When used in attacks, these techniques can reduce the complexity of some known attacks. In particular, they improve over Matsui's attack on DES.

Joint work with Eli Biham.

We initiate the study of out-of-band authentication in the group setting, extending the user-to-user setting where messaging platforms (e.g., Telegram and WhatsApp) protect against man-in-the-middle attacks by assuming that users have access to an external channel for authenticating one short value (e.g., two users who recognize each other’s voice can compare a short value). Inspired by the frameworks of Vaudenay (CRYPTO ’05) and Naor et al. (CRYPTO ’06) in the user-to- user setting, we assume that users communicate over a completely- insecure channel, and that a group administrator can out-of-band authenticate one short message to all users. An adversary may read, remove, or delay this message (for all or for some of the users), but cannot undetectably modify it.

Within our framework we establish tight bounds on the tradeoff between the adversary’s success probability and the length of the out-of-band authenticated message (which is a crucial bottleneck given that the out-of-band channel is of low bandwidth). We consider both computationally-secure and statistically-secure protocols, and for each flavor of security we construct an authentication protocol and prove a lower bound showing that our protocol achieves essentially the best possible tradeoff (moreover, instantiating our computationally- secure protocol in the random-oracle model yields an efficient and practically-relevant protocol).

This talk is based on joint work with Gil Segev.

Protocols for secure multiparty computation enable a set of parties to compute a joint function of their inputs, while preserving privacy, correctness and more. In theory, secure computation has broad applicability and can be used to solve many of the modern concerns around utilization of data and privacy. Huge steps have been made towards this vision in the past few years, and we now have protocols that can carry out large computations extremely efficiently, especially in the setting of an honest majority. However, in practice, there are still major barriers to widely deploying secure computation, especially in a decentralized manner.

In this paper, we present the first end-to-end automated system for deploying large- scale MPC protocols between end users, called MPSaaS (for MPC system-as-a-service). Our system enables parties to pre-enroll in an upcoming MPC computation, and then participate by either running software on a VM instance (e.g., in Amazon), or by run- ning the protocol on a mobile app, in Javascript in their browser, or even on an IoT device. Our system includes an automation system for deploying MPC protocols, an administration component for setting up an MPC computation and inviting partici- pants, and an end-user component for running the MPC protocol in realistic end-user environments. We demonstrate our system for a specific application of running secure polls and surveys, where the secure computation is run end-to-end with each party ac- tually running the protocol (i.e., without relying on a set of servers to run the protocol for them). This is the first such system constructed, and is a big step forward to the goal of commoditizing MPC.

Based on joint works with Assi Barak, Martin Hirt and Lior Koskas, and with Jun Furukawa.