Spring 2019 Crypto Day

Thank you for attending Spring 2019 Crypto Day 🙂

Date: Thursday, April 11th
Location: National Institute of Standards and Technology (NIST).
                Administration Building/Heritage Room
                (There are signs pointing from the front door of the Admin
                 building to Heritage Room; 1 minute walk.)
Parking: Instructions here.  Map location for visitor’s center here
Shuttle: From Shady Grove Metro, meet the NIST shuttle at the east side of
                the Shady Grove Metro Station at 15 and 45 minutes past the hour.
                The NIST shuttle will stop at “Bus Bay C.” 
Arriving via Uber/Lyft: Ride to NIST’s front gate — 100 Bureau Dr.,
                Gaithersburg, Maryland — and drop off in the Visitor Center
                parking lot. The NIST shuttle arrives at the front gate at :25 and :55
                past the hour, and (if you are checked in already) you can board it
                to ride to the Administration Building (where Heritage Room is).
Checking in: [If you received a Pass via email, please print it and skip
                this step.]
All visitors should plan to stop at the Visitor’s Center
                (next to the front gate of NIST at 100 Bureau Dr.) to receive their
                visitor’s badge for the day. Please leave ample time for this process
                (at least 5-10 minutes). Note that visitors arriving via the Metro
                Shuttle will need to disembark in order to receive their badge. (You
                may then ask for walking directions to the Admin building;
                10 minute walk.)
Time: 9:30-4:30
Lunch: NIST cafeteria (opens at 7:30am, closes at 3:00pm)

(Alternative informational website: NIST Event Page )



  • 9:30am – 10:00am: Breakfast in the cafeteria
  • 10:00am – 10:45am: David Wu (UVA)
  • 10:45am – 11:00am: coffee break 
  • 11am – 11:45am: Shuhong Gao (Clemson)
  • 11:45am – 12:30pm: Alessandra Scafuro (NC State)
  • 12:30pm – 1:45pm: Lunch at NIST cafeteria
  • 1:45pm – 2:30pm: Foteini Baldimtsi (George Mason)
  • 2:30pm – 3:00pm: coffee break 
  • 3:00pm – 3:45pm: Mohammad Mahmoody (UVA)
  • 3:45pm – 4:30pm: John Kelsey (NIST)


Talk list:

Speaker: David Wu — UVA
Title: New Constructions of Reusable Designated-Verifier NIZKs
Non-interactive zero-knowledge (NIZKs) are important cryptographic primitives, but we currently only have instantiations from a few specific assumptions like trapdoor permutations, bilinear maps, and very recently, the plain LWE assumption. We are still missing constructions from Diffie-Hellman assumptions. A recent line of work has studied specific NIZK constructions in relaxed models such as the designated-prover and the designated-verifier models.

In this work, we consider designated-verifier NIZKs (DV-NIZKs), where a trusted setup generates a common reference string together with a secret key for the verifier. We seek reusable schemes where the verifier can reuse the secret key to verify many different proofs and soundness should hold even against a prover who learns whether various proofs are accepted or rejected. In this talk, I will describe a generic approach for constructing reusable designated-verifier NIZKs based on Sigma protocols and any single-key attribute-based encryption scheme (ABE) satisfying a weak function-hiding property. Our generic framework can be instantiated from assumptions such as CDH and LWE.

Next, I describe an extension of our framework to obtain the stronger notion of malicious-designated-verifier NIZKs where the only trusted setup consists of a common random string, and there is a separate untrusted setup where the verifier chooses its own public/secret key needed to generate/verify proofs, respectively. Our generic framework yields new constructions of malicious DV-NIZKs from the DDH or the LWE assumptions.

Joint work with Alex Lombardi, Willy Quach, Ron D. Rothblum, and Daniel Wichs


Speaker: Shuhong Gao — Clemson
Title: Efficient Fully Homomorphic Encryption Schemes
As cloud computing, internet of things (IoT) and blockchain technology become increasingly  prevalent, there is an urgent need to protect the privacy of massive volumes of sensitive data collected or stored in distributed  computer networks  or cloud  servers,  as many of the networks or servers can be vulnerable to external and internal threats such as malicious hackers or curious insiders.   The Holy-Grail of cryptography is to have practical fully homomorphic encryption (FHE) schemes that allow any third party (including cloud servers, hackers, miners or  insiders) to perform searching or analytics of an arbitrary function on encrypted data without decryption, while no information on the original data is ever leaked. The breakthrough was made by Gentry in 2009  who discovered the first FHE scheme, and since then  many improvements have been made on designing more efficient homomorphic encryption schemes.  The main bottlenecks are in bootstrapping speed and large cipher expansion factor (the size ratio of ciphertexts over plaintexts): the current best FHE schemes can compute bootstrapping of one bit operation in a fraction of a second and have a cipher expansion factor of 8,000. In this talk, we present compact FHE schemes that achieve cipher expansion factor of 2.5 to 6 under secret key and 6.5 to 20 under public key while the bootstrapping speed matches the current best FHE schemes. The talk is based in part on the two papers:

   1. Shuhong Gao, Efficient fully homomorphic encryption scheme, preprint 2018. https://eprint.iacr.org/2018/637
   2. Benjamin Case, Shuhong Gao, Gengran Hu, and Qiuxia Xu. Fully homomorphic encryption with k-bit arithmetic operations, in preparation, 2019.



Speaker: Alessandra Scafuro — NC State
Title: Traceable Ring Signatures and other Anonymity Tools from a Random Oracle Only
We will show two main results.
First, a traceable ring signature that uses the RO only, in a black-box way thus leading to (1) extremely fast signing time and (2) post-quantum resistant security. I will also briefly comment on how to extend this idea  to  regular (non-traceable) ring signatures and to threshold (t-out-of-n) ring signature using trapdoor commitments in a black-box way.

Second, we show how to construct anonymous commit-and-prove schemes from a RO only. Previous construction of commit-and-prove for the anonymous setting all required the use of the code, or levering specific assumptions (typically non post-quantum resistant) such as DDH.



Speaker: Foteini Baldimtsi — George Mason
Title: Certifying RSA Public Keys with an Efficient NIZK
In many applications, it is important to verify that an RSA public key (N,e) specifies a permutation, in order to prevent attacks due to adversarially-generated public keys. We design and implement a simple and efficient noninteractive zero-knowledge protocol (in the random oracle model) for this task. The key feature of our protocol is compatibility with existing RSA implementations and standards. The protocol works for any choice of e. Applications concerned about adversarial key generation can just append our proof to the RSA public key without any other modifications to existing code or cryptographic libraries. Users need only perform a one-time verification of the proof to ensure that raising to the power e is a permutation of the integers modulo N. For typical parameter settings, the proof consists of nine integers modulo N; generating the proof and verifying it both require about nine modular exponentiations.

Joint work with Sharon Goldberg and Leonid Reyzin and Omar Sagga


Speaker: Mohammad Mahmoody — UVA
Title: Registration-Based Encryption
We introduce a new cryptographic primitive that is a hybrid of Identity-Based Encryption and Public-Key Directories, which we call Registration-Based Encryption (RBE). In RBE, identities generate their own public and secret keys and then ‘register’ into a server that holds no secrets nor any randomness (other than an initial public CRS). Therefore, there is no key-escrow problem in RBE as is in IBE. On the other hand, at any moment, there is a compact public parameter (independent of the number of parties) that can be used to securely encrypt messages to all the identities so far. We also show how to construct RBE based on various assumptions (from IO to DDH) with different efficiency trade-offs.

Based on joint (TCC-18 and PKC-19) works with Sanjam Garg, Mohammad Hajiabadi, Ahmadreza Rahimi, and Sruthi Sekar.


Speaker: John Kelsey — NIST
Title: Password Tickets
We introduce the notion of Ticket-Mediated Password Strengthening (TMPS), a technique for allowing users to derive keys from passwords while imposing a strict limit on the number of guesses of their password any attacker can make, and strongly protecting the users’ privacy. We describe the security requirements of TMPS, and then a set of efficient and practical protocols to implement a TMPS scheme, requiring only hash functions, CCA2-secure encryption, and blind signatures. We provide several variant protocols, including an offline symmetric-only protocol that uses a local trusted computing environment, and online variants that avoid the need for blind signatures in favor of group signatures or stronger trust assumptions. We formalize the security of our scheme by defining an ideal functionality in the Universal Composability (UC) framework, and by providing game-based definitions of security. We prove that our protocol realizes the ideal functionality in the random oracle model (ROM) under adaptive corruptions with erasures, and prove that security with respect to the ideal/real definition implies security with respect to the game-based definitions.

Spring 2019 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 )

Facebook photo

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

Connecting to %s