# Monthly Archives: December 2018

Where: Barrister’s Hall at the ground floor of the BU Law School. The address is 765 Comm Ave but it’s better to enter the building from the back entrance on Bay State Road, and then turn right.

Organizers: Ran Canetti, Yael Kalai, Vinod Vaikuntanathan and Daniel Wichs.

When:Friday, Dec 14 at BU.

Thanks: NSF MACS Project for their generous support.

### Program:

 9:30 – 10:00. Coffee/Breakfast 10:00 – 11:00. Sandro Coretti, NYU The Double Ratchet: Security Notions, Proofs, and Modularization for the Signal Protocol (video) 11:15 – 12:15. Omer Paneth, Northeastern and MIT Weak Zero-Knowledge Beyond the Black-Box Barrier (video) 12:15 – 1:30. Lunch 1:30 – 2:30. Lisa Yang, MIT Publicly Verifiable Delegation from Standard Assumptions (video) 2:45 – 3:45. Alex Lombardi, MIT Fiat-Shamir from Simpler Assumptions (video) 3:45 – 4:30. Reception

### Abstracts:

Speaker: Sandro Coretti, NYU
Title: The Double Ratchet: Security Notions, Proofs, and Modularization for the Signal Protocol

Abstract:

Signal is a famous secure messaging protocol used by billions of
people, by virtue of many secure text messaging applications including
Signal itself, WhatsApp, Facebook Messenger, Skype, and Google Allo.
At its core it uses the concept of double ratcheting, where every
message is encrypted and authenticated using a fresh symmetric key; it
has many attractive properties, such as forward security,
post-compromise security, and immediate (no-delay) decryption, which
had never been achieved in combination by prior messaging protocols.While the formal analysis of the Signal protocol, and ratcheting in
general, has attracted a lot of recent attention, we argue that none
of the existing analyses is fully satisfactory. To address this
problem, we give a clean and general definition of secure messaging,
which clearly indicates the types of security we expect, including
forward security, post-compromise security, and immediate decryption.
We are the first to explicitly formalize and model the immediate
decryption property, which implies (among other things) that parties
seamlessly recover if a given message is permanently lost—a property
not achieved by any of the recent provably secure alternatives to
Signal. We build a modular generalized Signal protocol from the
following components: (a) continuous key agreement (CKA), a clean
primitive we introduce and which can be easily and generically built
from public-key encryption (not just Diffie-Hellman as is done in the
current Signal protocol) and roughly models so-called public-key
ratchets; (b) forward-secure authenticated encryption with associated
data (FS-AEAD), which roughly captures so-called symmetric-key
ratchets; and (c) a two-input hash function that is a pseudorandom
function (resp. generator with input) in its first (resp. second)
input, which we term PRF-PRNG. As a result, in addition to
instantiating our framework in a way resulting in the existing, widely
used Diffie-Hellman based Signal protocol, we can easily get
post-quantum security and not rely on random oracles in the analysis.We further show that our design can be elegantly extended to include
forms of fine-grained state compromise recently studied at CRYPTO’18,
but without sacrificing the immediate decryption property. However, we
argue that the additional security offered by these modifications is
unlikely to justify the efficiency hit of using much heavier
public-key cryptography in place of symmetric-key cryptography.

Speaker: Omer Paneth, Northeastern and MIT
Title: Weak Zero-Knowledge Beyond the Black-Box Barrier

Abstract: The round complexity of zero-knowledge protocols is a long-standing open question, yet to be settled under standard assumptions. So far, the question has appeared equally challenging for relaxations such as weak zero-knowledge and witness hiding. Protocols satisfying these relaxed notions under standard assumptions have at least four messages, just like full-fledged zero knowledge. The difficulty in improving round complexity stems from a fundamental barrier: none of these notions can be achieved in three messages via reductions (or simulators) that treat the verifier as a black box.

We introduce a new non-black-box technique and use it to obtain the first protocols that cross this barrier under standard assumptions. Our main results are:

– Weak zero-knowledge for $\NP$ in two messages, assuming quasipolynomially-secure fully-homomorphic encryption and other standard primitives (known from quasipolynomial hardness of Learning with Errors), as well as subexponentially-secure one-way functions.

– Weak zero-knowledge for $\NP$ in three messages under standard polynomial assumptions (following for example from fully-homomorphic encryption and factoring).

We also give, under polynomial assumptions, a two-message witness-hiding protocol for any language L \in NP that has a witness encryption scheme. This protocol is also publicly verifiable.

Our technique is based on a new homomorphic trapdoor paradigm, which can be seen as a non-black-box analog of the classic Feige-Lapidot-Shamir trapdoor paradigm.

Joint work with Nir Bitansky and Dakshita Khurana.

Speaker: Lisa Yang, MIT
Title: Publicly Verifiable Delegation from Standard Assumptions

Abstract: We construct a delegation scheme for all polynomial time computations. Our scheme is publicly verifiable and completely non-interactive in the common reference string (CRS) model.

Our scheme is based on an efficiently falsifiable decisional assumption on groups with bilinear maps. Prior to this work, publicly verifiable non-interactive delegation schemes were only known under knowledge assumptions (or in the Random Oracle model), or under non-standard assumptions related to obfuscation or multilinear maps.

We obtain our result in two steps. First, we construct a scheme with a long CRS (polynomial in the running time of the computation) by following the blueprint of Paneth and Rothblum (TCC 2017). Then we show how to bootstrap this scheme to obtain a short CRS. Our bootstrapping theorem exploits the fact that our scheme can securely delegate certain classes of nondeterministic computations.

Speaker: Alex Lombardi
Title: Fiat-Shamir from Simpler Assumptions

Abstract: We present two new protocols:

(1) A succinct publicly verifiable non-interactive argument system for log-space uniform NC computations, under the assumption that any one of a broad class of fully homomorphic encryption (FHE) schemes has almost optimal security against polynomial-time adversaries. The class includes all FHE schemes in the literature that are based on the learning with errors (LWE) problem.

(2) A non-interactive zero-knowledge argument system for NP in the common random string model, assuming almost optimal hardness of search-LWE against polynomial-time adversaries.

Both results are obtained by applying the Fiat-Shamir transform with explicit, efficiently computable functions to certain classes of interactive proofs. We improve over prior work by reducing the security of these protocols to qualitatively weaker computational hardness assumptions. Along the way, we also show that the Fiat-Shamir transform can be soundly applied (in the plain model) to a richer class of protocols than was previously known.

Joint work with Ran Canetti, Yilei Chen, Justin Holmgren, Guy Rothblum, and Ron Rothblum