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.
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.
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
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.
Based on joint works with Assi Barak, Martin Hirt and Lior Koskas, and with Jun Furukawa.