Fall 2021 Crypto Day

Date: Friday, November 5th
Location:  University of Maryland, Brendan Iribe Center, IRB-4105. Masks are required to be worn inside.
Zoom link: contact aandreea at umd dot edu or giorgos at umd dot edu.
Parking: Here, for $3 / hour. More information here.

Shuttle: from College Park Metro. Take a right out of the fare gates and climb the stairs. Look for the 104 Shuttle bus (there are signs for it), and exit at the Glenn L. Martin Wind Tunnel stop.
Time: 9:30-16:30 EST.
Lunch: Look here. (Vigilante Coffee is a good place for coffee.)


  • 09:30 – 10:00 Welcome breakfast
  • 10:00 – 10:40 Alexander Bienstock (in person): What is the Exact Security of the Signal Protocol?
  • 10:50 – 10:30 Ian Miers (in person): Fuzzy message detection
  • 11:40 – 12:20 Justin Thaler (virtual): Linear-time SNARKs
  • 12:30 – 14:00 Lunch (on your own)
  • 14:00 – 14:40 Austin Theriault (in person): Fighting Fake News in Encrypted Messaging with the Fuzzy Anonymous Complaint Tally System (FACTS)
  • 14:50 – 15:30 Zhengzhong Jin (virtual): SNARGs for P from LWE
  • 15:40 – 16:20 Mariana Raykova (virtual): On the (in)security of ROS

Speaker: Alexander Bienstock (NYU)

Title: What is the Exact Security of the Signal Protocol?

Abstract: In this work we develop comprehensive definitions in the Universal Composability framework to study the Signal Double Ratchet (Signal for short) protocol. Our definitions enable a more fine-grained and rigorous analysis of the exact security of Signal by explicitly capturing many new security guarantees, in addition to the ones that were already identified in the state-of-art work by Alwen, Coretti and Dodis [Eurocrypt 2019]. Moreover, our definitions provide the ability to more easily build on top of Signal, using the UC Composition Theorem. The Signal protocol, as it is described in the whitepaper, securely realizes our ideal functionality F_Signal. However, as we interpret from the high-level description in the whitepaper, the guarantees of F_Signal seem slightly weaker than those one would expect Signal to satisfy. Therefore we provide a stronger, more natural definition, formalized through the ideal functionality F_Signal+ . Based on our definitions we are able to make many important insights as follows:

  • We observe several shortcomings of Alwen et al.’s game-based security notions. To demonstrate them, we construct four different modified versions of the Signal protocol, all of which are insecure according to our weaker FSignal definition, but remain secure according to their definitions. Among them, one variant was suggested for use by Alwen et al.; another one was suggested for use by the Signal whitepaper itself.
  • We identify the exact assumptions required for the full security of Signal. In particular, our security proofs use the gap-Diffie-Hellman assumption and the random oracle model, as opposed to the DDH assumption and standard model used in Alwen et al.
  • We demonstrate the shortcomings of Signal with respect to our stronger functionality FSignal+ by showing a non-trivial (albeit minor) weakness with respect to that definition.
  • Finally, we complement the above weakness by providing a minimalistic modification to Signal (that we call the Triple Ratchet) and show that the resulting protocol securely realizes the stronger functionality FSignal+ . Remarkably, the modification incurs no additional communication cost and virtually no additional computational cost.

Joint work with Jaiden Fairoze, Sanjam Garg, Pratyay Mukherjee, and Srinivasan Raghuraman

Speaker: Ian Miers (UMD)

Title: Fuzzy message detection

Abstract: Many privacy-preserving protocols employ a primitive that allows a sender to “flag” a message to a recipient’s public key, such that only the recipient (who possesses the corresponding secret key) can detect that the message is intended for their use. Examples of such protocols include anonymous messaging, privacy-preserving payments, and anonymous tracing. A limitation of the existing techniques is that recipients cannot easily outsource the detection of messages to a remote server, without revealing to the server the exact set of matching messages. In this work we propose a new class of cryptographic primitives called fuzzy message detection schemes. These schemes allow a recipient to derive a specialized message detection key that can identify correct messages, while also incorrectly identifying non-matching messages with a specific and chosen false positive rate pp. This allows recipients to outsource detection work to an untrustworthy server, without revealing precisely which messages belong to the receiver. We show how to construct these schemes under a variety of assumptions; describe several applications of the new technique; and show that our schemes are efficient enough to use in real applications.

Joint work with Gabrielle Beck, Julia Len and Matthew Green.

Speaker: Justin Thaler (Georgetown U)

Title: Linear-time SNARKs

Abstract: This talk describes some new SNARKs for expressive NP-complete problems such as R1CS and circuit satisfiability and implementations thereof. The prover runs in time linear in the size of the NP statement, and the argument works over any sufficiently large field. No prior implemented SNARK satisfied these properties.

Speaker: Austin Theriault (GWU)

Title: Fighting Fake News in Encrypted Messaging with the Fuzzy Anonymous Complaint Tally System (FACTS)

Abstract: Recent years have seen a strong uptick in both the prevalence and real-world consequences of false information spread through online platforms. At the same time, encrypted messaging systems such as WhatsApp, Signal, and Telegram, are rapidly gaining popularity as users seek increased privacy in their digital lives. The challenge we address is how to combat the viral spread of misinformation without compromising privacy. Our FACTS system tracks user complaints on messages obliviously, only revealing the message’s contents and originator once sufficiently many complaints have been lodged. Our system is private, meaning it does not reveal anything about the senders or contents of messages which have received few or no complaints; secure, meaning there is no way for a malicious user to evade the system or gain an outsized impact over the complaint system; and scalable, as we demonstrate excellent practical efficiency for up to millions of complaints per day. Our main technical contribution is a new collaborative counting Bloom filter, a simple construction with difficult probabilistic analysis, which may have independent interest as a privacy-preserving randomized count sketch data structure. Compared to prior work on message flagging and tracing in end-to-end encrypted messaging, our novel contribution is the addition of a high threshold of multiple complaints that are needed before a message is audited or flagged. We present and carefully analyze the probabilistic performance of our data structure, provide a precise security definition and proof, and then measure the accuracy and scalability of our scheme via experimentation.

Joint work with Linsheng Liu, Daniel S. Roche and Arkady Yerukhimovich.

Speaker: Zhengzhong Jin (JHU)

Title: SNARGs for P from LWE

Abstract: We provide the first construction of a succinct non-interactive argument (SNARG) for all polynomial time deterministic computations based on standard assumptions. For T steps of computation, the size of the proof and the common random string (CRS) as well as the verification time are poly-logarithmic in T. The security of our scheme relies on the hardness of the Learning with Errors (LWE) problem against polynomial-time adversaries. Previously, SNARGs based on standard assumptions could support bounded-depth computations and required sub-exponential hardness assumptions [Jawale-Kalai-Khurana-Zhang, STOC’21].

Along the way, we also provide the first construction of non-interactive batch arguments for NP based solely on the LWE assumption.

Based on the joint work with Abhishek Jain and Arka Rai Choudhuri.

Speaker: Mariana Raykova (Google)

Title: On the (in)security of ROS

Abstract: We present an algorithm solving the ROS (Random inhomogeneities in a Overdetermined Solvable system of linear equations) problem mod p in polynomial time for L > log p dimensions. Our algorithm can be combined with Wagner’s attack, and leads to a sub-exponential solution for any dimension L with best complexity known so far. 

When concurrent executions are allowed, our algorithm leads to practical attacks against unforgeability of blind signature schemes such as Schnorr and Okamoto–Schnorr blind signatures, threshold signatures such as GJKR and the original version of FROST, multisignatures such as CoSI and the two-round version of MuSig, partially blind signatures such as Abe–Okamoto, and conditional blind signatures such as ZGP17. Schemes for e-cash (such as Brands’ signature) and anonymous credentials (such as Anonymous Credentials Light) inspired from the above are also affected.

Joint work with Fabrice Benhamouda, Tancrede Lepoint, Julian Loss,  Michele Orru.

Fall 2021 Crypto Day

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s