# Fall 2019 Cryptoday

Date: Oct 4th, 2019,  Friday

Location: Room E4229 (da Vinci room),
College of Engineering East Hall, VCU
401 W. Main Street, VA 23284
(Please see below for directions and parking instructions. )

### Program (subject to change):

• 9:30am – 10:00am: Breakfast
• 10:00am – 10:45am: Thang Dinh (VCU): BackPackers: A New Network Paradigm for Secure and High-performance Blockchains
• 10:45am – 11:00am: coffee break
• 11am – 11:45am: Arkady Yerukhimovich (GWU): Stormy: Statistics in Tor by Measuring Securely
• 11:45am – 12:30pm: Arka Rai Choudhuri (JHU): Round Optimal Secure Multiparty Computation from Minimal Assumptions
• 12:30pm – 1:45pm: Lunch  (on your own)
• 1:45pm – 2:30pm: Qiang Tang (NJIT): Correcting Subverted Random Oracles
• 2:30pm – 3:00pm: coffee break
• 3:00pm – 3:45pm: David Wu (UVA): Watermarking PRFs from Lattices: Stronger Security via Extractable PRFs

### Directions and Parking

Please see the below detail regarding our location and parking information. The JL Lot will be the location for you to park.

Virginia Commonwealth University
College of Engineering (East Hall)
401 West Main Street
Room E4229
Richmond, Virginia 23284-3068

Directions to the Engineering Building

Arriving from the North/West by Interstate 95S/64E
Take Exit 76B Belvidere Street. Stay in the middle lane on the exit. Turn left, then get in the right lane for an immediate right turn onto Belvidere Street. When you pass Monroe Park on the right, get in the left lane turning left onto West Cary Street (the next block after Main Street.). Go one block and turn left at Madison Street. The JL parking lot is on the right behind the 7-11.

Arriving from the South/East by Interstate 95N/64W
Take Exit 190 for Fifth Street and Downtown/Coliseum. Turn right at the eighth traffic light onto Main Street. Follow Main Street to Belvidere Street. (Landmarks: 7-11, then the Snead Building on the left). Turn left at Belvidere Street and stay in the left hand lane turning left on West Cary Street (the next light). Go one block and turn left at Madison Street. The JL parking lot is on the right behind the 7-11.

Once in the Eng East Building, make your way up to the 4th floor near the Belvidere and Main St side/corner of the building. Room E4229.

### Talk abstracts

Thang Dinh (VCU): BackPackers: A New Network Paradigm for Secure and High-performance Blockchains
Abstract: Despite many scaling proposals for Bitcoin protocols, existing permissionless approaches, including Bitcoin-Compact, Bitcoin-NG, and Conflux, achieve very low efficiency in terms of networking. In our large-scale peer-to-peer blockchain simulation, no existing permissionless protocols can achieve more than 4% bandwidth utilization, the fraction of bandwidth used for transmitting confirmed transactions. We propose BackPackers, a cross-layer paradigm that optimizes concurrently both consensus (layer 1) and network communication (layer 0) protocols. BackPackers introduces a new node role, called packers, who form a secure and decentralized network backbone. Without any trust assumption, independent packers work together to effectively distribute transactions to all miners, eliminating a major network bottleneck in broadcasting transactions. In exchange for their networking service, each packer receives a portion of transaction fees that it distributes. Through theoretical analysis, we show rigorous proofs for security properties, namely, consistency and liveness. Most importantly, we prove that BackPackers achieves $(1-\epsilon)$-optimality in throughput, with respect to the network limit, and $O(1)$-optimality in block propagation time, even when the network is heterogeneous. Through experimental studies, we show that BackPackers can achieve up to 80\% bandwidth utilization, achieving 7,000+ tps and 0.8s block propagation time for 1,000 nodes with 20Mbps bandwidth. Under the same networking condition, BackPackers achieves an order of magnitude higher throughput comparing to the state-of-the-arts permissionless blockchains.

Arkady Yerukhimovich (GWU): Stormy: Statistics in Tor by Measuring Securely
Abstract: The prevalence of large-scale, Internet-wide distributed systems such as the Tor network call for the development of large-scale secure multi-party computation (MPC).  MPC designed for such settings must run over thousands of parties, where the parties have unequal resources (e.g., bandwidth, and processing power), and must be resilient to party failure.  In this talk, we present Stormy, an MPC protocol for performing secure measurements over the Tor network that maximizes throughput through optimal utilization of the available bandwidth on Tor routers.  Moreover, Stormy’s security requires no additional assumptions over what is already necessary for the secure operation of the Tor network.  We describe experimental results showing that Stormy enables important statistics to be evaluated securely over the entire Tor network.
Joint work with Ryan Wails, Aaron Johnson, Daniel Starin, and Dov Gordon

Arka Rai Choudhuri (JHU): Round Optimal Secure Multiparty Computation from Minimal Assumptions
Abstract: We construct a four round secure multiparty computation (MPC) protocol in the plain model that achieves security against any dishonest majority. The security of our protocol only relies on the existence of four round oblivious transfer. This fully resolves the round complexity of MPC (w.r.t. black-box simulation) based on minimal assumptions.
All previous results required either a larger number of rounds or stronger assumptions.
Joint with with Michele Ciampi, Vipul Goyal, Abhishek Jain and Rafail Ostrovsky.

Qiang Tang (NJIT): How to Securely Deploy a Blockchain: Correcting Subverted Random Oracles
Abstract: Hash function is a fundamental primitive for many security applications including blockchain, password login, digital signatures and more. In this talk we focus on the basic problem of correcting faulty—or adversarially corrupted—random oracles, so that they can be confidently applied for such cryptographic purposes.
We prove that a simple construction can transform a “subverted” random oracle—which disagrees with the original one at a negligible fraction of inputs—into a construction that is indifferentiable from a random function. Our results permit future designers of cryptographic primitives in typical kleptographic settings (i.e., with adversaries who may subvert the implementation of cryptographic algorithms but undetectable via black-box testing) to use random oracles as a trusted black box, in spite of not trusting the implementation. Our analysis relies on a general rejection re-sampling lemma which is a tool of possible independent interest.
Bio: Qiang Tang is currently an assistant professor of New Jersey Institute of Technology and also the director of JD-NJIT-ISCAS Joint Blockchain Lab. He was a postdoc at Cornell before joining NJIT and obtained his Ph.D from the University of Connecticut. His research interests are applied and theoretical cryptography and blockchain technology, including post-Snowden cryptography, accountability among others.

David Wu (UVA): Watermarking PRFs from Lattices: Stronger Security via Extractable PRFs
Abstract: A software watermarking scheme enables one to embed a “mark” (i.e., a message) within a program while preserving the program’s functionality. Moreover, there is an extraction algorithm that recovers an embedded message from a program. The main security goal is that it should be difficult to remove the watermark without destroying the functionality of the program. Existing constructions of watermarking focus on watermarking cryptographic functions like pseudorandom functions (PRFs). Even in this setting, realizing watermarking from standard assumptions remains difficult. For example, existing constructions from standard assumptions become insecure in the presence of a mark-extraction oracle or require fully trusting a central watermarking authority (that has the ability to break security of even unmarked keys).
In this talk, I describe a new lattice-based secret-key watermarking scheme for PRFs that provides unremovability against adversaries with access to the mark-extraction oracle and offers a strong and meaningful notion of pseudorandomness even against the watermarking authority. Security of our new schemes can be based on the hardness of computing nearly polynomial approximations to worst-case lattice problems, a qualitatively weaker assumption than that needed for existing constructions of (message-embedding) watermarking. Along the way, I will introduce the notion of an extractable PRF, which offers a new intermediary primitive and approach for constructing cryptographic watermarking schemes.
Joint work with Sam Kim

# Spring 2019 Crypto Day

Thank you for attending Spring 2019 Crypto Day 🙂

Date: Thursday, April 11th
Location: National Institute of Standards and Technology (NIST).
(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
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 )

Program:

• 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)

# Fall 2018 Crypto Day

Date: Thursday, December 13th
Location:  University of Maryland, A.V. Williams Building, 4172.
Parking: Here, for $3 / hour. Shuttle: from College Park Metro. Take a left out of the fare gates. Look for the 104 Shuttle bus, and exit at the first stop on campus. Time: 10:00-4:30 Lunch: Look here. (Vigilante Coffee is a good place for coffee.) Program (subject to change): • 9:30-10:00AM: Welcome breakfast • 10:00 – 10:45AM: Babis Papamanthou • 11AM-11:45PM: Gilad Asharov • 11:45PM-12:30PM: Prabhanjan Ananth • 12:30 – 2PM: Lunch (on your own) • 2pm-2:45PM: Phi Hung Le • 2:45-3:30PM: Marcella Hastings • 3:45-4:30PM: Erica Blum # Summer 2018 Crypto Day Date: Friday, May 25th Location: George Mason University, 4201 Volgenau School of Engineering. Parking:$15 Parking. Or \$8 Parking, which requires creating an account.
Shuttle: from Vienna Metro station (Metro to Sandy Creek).
Time: 9-5

Program (subject to change):

• 9-9:40AM: Welcome breakfast
• 9:40-11AM:  Aria Shahverdi.
• Title: On the Leakage Resilience of Ideal-Lattice Based Public Key Encryption.
• 11AM-12:20PM: Hong-Sheng Zhou.
• Title: How to mimic Nakamoto’s design via proof-of-stake.
• 12:20PM-2PM: Lunch (on your own)
• Title: Trapdoor Functions From the Computational Diffie-Hellman Assumption
• Title: On Instantiability of RSA-OAEP and Variants

# 3rd DC-AREA CRYPTO DAY

Our next Crypto Day will be May 6th at Georgetown.  We will hold in it in room 155 of the business school building; see here for directions.  Please find the abstract of the talks below.  The plan is to allocate 1 hour 20 minutes for each talk, with the talk itself to an hour, and then there can be 20 minutes (hopefully lively) questions/discussion. In terms of getting to Georgetown, check out the GUTS bus.  Otherwise, the closest metro stop is probably Foggy Bottom.

Preliminary schedule:

9-9:40AM: Welcome breakfast
9:40-11AM Mukul
2pm-3:20pm Paul
3:20-4:40pm George

Non-Malleable Codes for Bounded Depth, Bounded Fan-in Circuits

Mukul R. Kulkarni

Non-malleable codes are a relaxation of error correcting codes, for settings in which privacy, but not necessarily correctness, is desired. Instead of requiring that after modification—i.e. tampering—of the codeword, the original message can always be recovered, non-malleable codes allow a different message to be recovered, as long as the recovered message is unrelated to the original message.  This relaxation potentially allows for the construction of coding schemes for rich classes of tampering classes, beyond what can be done for error correcting codes. In applications, non-malleable codes are used to encode the memory of a device, and thus protect against (certain classes) of adversarial tampering.

Dziembowski et al. [ITCS 2010] introduced the notion of non-malleable codes and since then, constructing such codes has been a highly active area of research. Unfortunately, nearly all previous results consider only “compartmentalized” tampering classes, wherein a codeword is split into blocks and the attacker is assumed to tamper with different blocks of codeword independently of each other.
In our work, we consider a natural, non-compartmentalized class of tampering functions. Specifically, we present non-malleable codes secure against tampering functions that can be represented by bounded depth, bounded fan-in circuits. More generally, our scheme is resilient against “local” tampering functions wherein any output bit is dependent on at most n^{\delta} bits, where n is the total number of bits in the codeword and 0 \leq \delta < 1 is a constant. Notably this function class includes NC^0.
Bio: Mukul R. Kulkarni is a doctoral student at the University of Maryland, College Park studying under the guidance of Dr. Dana Dachman-Soled. His research interests involve Tamper Resilient Cryptography.

Lower-Bounds on Assumptions behind Indistinguishability Obfuscation

In this talk, we first show that basing IO on a variety of assumptions (e.g., trapdoor permutations, bi-linear maps, etc) in a weakly black-box way is as hard as basing public-key encryption on one-way functions (in a non-black-box way). The latter has remained as one of the most challenging open questions in cryptography. Then, by combining our results with a recent result of Brakerski, Brzuska, and Fleischhacker, we rule out any fully black-box construction of IO from the same set of primitives assuming the existence of one-way functions and that the polynomial-hierarchy does not collapse.

Based on joint works with Ameer Mohammed, Soheil Nematihaji, Rafael Pass, and abhi shelat.
Bio: Mohammad Mahmoody is an assistant professor at the Univ of Virginia. He got his PhD from Princeton in 2010 under supervision of Boaz Barak and then spent a few years in Rafael Pass’s crypto group at Cornell before joining UVa in 2013.

New Inference Attacks on Order-Preserving and Order-Revealing Encryption

Paul Grubbs

Order-preserving Encryption (OPE) has, of late, received a great deal of attention from the research community and from industry. It has proven to be an enormously useful tool in areas like cloud security and encrypted databases. However, for most plaintext distributions of practical interest very little is known about the concrete security of OPE. In this talk, I will describe some new cryptanalytic attacks on OPE and order-revealing encryption. I will also motivate stronger adversarial models and present new attacks in those settings. Finally, I will present experimental results of implementing the attacks on several data sets. Our results show that the concrete security of OPE and ORE is very low in some settings, and that more work is needed to understand the consequences (and hopefully, the limits) of inference attacks against encryption schemes that leak order. Joint work with Kevin Sekniqi, Muhammad Naveed, and Tom Ristenpart.
Bio: Paul Grubbs is a PhD student in Computer Science at Cornell University and Cornell Tech, working on the theory and practice of cryptography. Currently he is interested in property-preserving encryption, searchable encryption, and applied crypto. Before starting his PhD, he worked for two and a half years as a cryptography engineer at Skyhigh Networks, a cloud security startup in Campbell, CA.

Accessing Data while Preserving Privacy

Georgios Kellaris

We initiate a formal research of the privacy-efficiency tradeoff of secure database systems. Such systems, such as CryptDB and Cipher-base, try to mitigate the high costs of full-fledged cryptographic solutions by relaxing the security guarantees they provide. We provide abstract models that capture the basic properties of these systems and identify their fundamental leakage channels. These models allow performing a generic and implementation independent investigation of the inherent tradeoffs between security and efficiency. In particular, this modeling allows us in some cases to devise generic reconstruction attacks where the server learns the secret attributes of every record stored in the database, pointing to inherent limitations of these models.

We present a new model of differentially private storage where differential privacy is preserved even against an attacker that controls the data and the queries made to it. We give a generic construction of differentially private storage that combines ORAM and differentially private sanitizers. We also provide efficient constructions and lower bounds for some specific query sets. We have implemented some of our algorithms, and report on their efficiency.Joint work with Georgios Kellaris, George Kollios, Kobbi Nissim, and Adam O’Neill.

Bio: Georgios is currently a Post-Doctoral Fellow at CRCS, Harvard University, and at Boston University. He received his Ph.D. degree in Computer Science and Engineering from the Hong Kong University of Science and Technology (2015), under the supervision of prof. Dimitris Papadias, and with the support of the Hong Kong Ph.D. Fellowship Scheme. He holds a 4-year B.Sc. in Informatics and Telecommunications from the University of Athens (2006) and a 2-year M.Sc. degree in Digital Systems from the University of Piraeus (2008). He has worked as a researcher at the University of Piraeus in Greece, the Singapore Management University and the Nanyang Technological University in Singapore, and at Boston University. His research interests include databases and differential privacy.

# 2nd DC-Area Crypto Day

DC CRYPTO DAY
FRIDAY, OCTOBER 30
JOHNS HOPKINS UNIVERSITY (HOMEWOOD CAMPUS) ∙ BALTIMORE, MD

Be sure to join us for the next DC area Crypto Day scheduled from 10:00 a.m. – 5:00 p.m. on Friday, October 30 at the Homewood Campus of Johns Hopkins University. The theme of this installment is Bitcoin.

Parking Location: South Garage
3100 Wyman Park Drive
Baltimore, MD 21211

Location of Talks: Sherwood Room, Levering Hall
Campus map.
*Please note that Levering Hall is building number 40 on the map and South Garage Parking is the one next to building 45 on the map.

Agenda:
10:00 AM – 11:00 AM |David Evans, University of Virginia
11:10 AM – 12:10 PM |Andrew Miller, University of Maryland
12:10 PM – 1:40 PM | Lunch
1:40 PM – 2:40 PM |Ranjit Kumaresan, Massachusetts Institute of Technology
2:50 PM – 3:50 PM |Matthew Green, Johns Hopkins University
4:00 PM – 5:00 PM | Panel discussion

Note that there is a 10:00 minute break between the talks.

Please find the titles and abstracts below.

Speaker: David Evans, University of Virginia
Title: Trick or Treat?: Bitcoin for Non-Believers, Cryptocurrencies for Cypherpunks
Abstract: This (non-research) talk will start with a tutorial introduction to cryptocurrencies and how bitcoin works (and doesn’t work) today. We’ll touch on some of the legal, policy, and business aspects of bitcoin and discuss some potential research opportunities in cryptocurrencies.

Speaker: Andrew Miller, University of Maryland
Title: Privacy-preserving Smart Contracts
https://eprint.iacr.org/2015/675.pdf

Abstract: Existing blockchain-based cryptocurrencies such as Bitcoin and Ethereum, store all financial transactions in the clear on the blockchain. This compromises the privacy of financial transactions, which is essential in numerous applications.
Hawk is a blockchain-based smart contract system that stores encrypted transactions on the blockchain, and relies on cryptography to retain the security of the cryptocurrency. A Hawk programmer can write a private smart contract in an intuitive manner without having to implement cryptography, and our compiler automatically generates an efficient cryptographic protocol where contractual parties interact with the blockchain, using cryptographic primitives such as succinct zero-knowledge proofs.
To formally define and reason about the security of our protocols, we also formalize a new simulation-based “blockchain model” of secure computation, which is of independent interest.

Speaker: Ranjit Kumaresan, Massachusetts Institute of Technology
Title: How to Use Bitcoin to Design Fair Protocols
Abstract: I will talk about a recent line of work that integrates traditional secure computation with a formal financial framework. This line of work identifies and abstracts some key transaction functionalities offered by the Bitcoin network, and shows how to incentivize correct behavior in secure computation (and other cryptographic tasks) in a model where parties have access to such a transaction functionality.

Speaker: Matt Green,  Johns Hopkins University
Title: TBD
Abstract: TBD

*Please note that lunch will not be provided, click on Crypto Conference Dining Options to check out local nearby options.

Please RSVP to Sr. Academic Program Coordinator Jessica Finkelstein at jkastne2@jhu.edu by Friday, October 23.

This DC Crypto Day is hosted by:

p.s. The first DC area crypto day was held at the University of Maryland at College Park. See here for the program and more information.