CryptoDay @ Cornell Tech, Manhattan, Friday, Mar 08, 2019

Mar 08, 2019 (Friday) at Cornell Tech, Manhattan, Bloomberg Center, room 071.

Program

09:30 – 10:00.	Introduction/Coffee
10:00 – 10:50.	Yuval Ishai (Technion) Compressing Vector OLE: Secure Computation with Silent Preprocessing
11:00 – 11:50.	Quanquan C. Liu (MIT) Static-Memory-Hard Functions and Modeling the Cost of Space vs Time
12:00 – 02:00.	Lunch (not provided)
02:00 – 02:50.	Ofir Weisse (University of Michigan) Foreshadow: Breaking the Virtual Memory Abstraction with Transient Out-of-Order Execution
03:00 – 03:50.	Dov Gordon (George Mason University) Secure Computation with Differentially Private Access Patterns

Venue

Address: Cornell Tech, Manhattan, Bloomberg Center, room 071.

2 West Loop Road New York NY 10044

• Subway:
  • Coming from the west side:
    1. Line 1 to 59th street-Columbus circle (direction: South Ferry)
    2. Line B or D from 59th street-Columbus circle to 47-50 street-Rockefeller center (direction: Coney Island)
    3. Line F from 47-50 street-Rockefeller center to Roosvelt Island station (direction: Jamaica-179 st)
    4. Walk to Bloomberg center
  • Coming from the east side:
    1. Take any train on the green line (4,5,6) to 59st
    2. Walk to LexingtonAv/63st
    3. Take the F line to Roosevelt island station (transfer is for free)
    4. Walk to Bloomberg center
• Parking:
  • Parking fee: 18$ for 10 hours
  • Parking located just next to the bridge – (the north bridge): https://rioc.ny.gov/parking.htm
  • 16 min walk from the parking to Cornell. There is a free (red) bus that circles the island, every 10 minutes.

[Directions] [Google Maps]

Organizers

Fabrice Benhamouda (IBM Research)
Tal Rabin (IBM Research)
with the help and support of Ilan Komargodski and Rafael Pass (Cornell Tech).

Support

Some travel support for NY CryptoDay is provided by DIMACS/Simons Collaboration in Cryptography through NSF grant #CNS-1523467.

Abstracts

• Compressing Vector OLE: Secure Computation with Silent Preprocessing / Yuval Ishai (Technion)

  Oblivious linear-function evaluation (OLE) is a secure two-party protocol allowing a receiver to learn a linear combination of two field elements held by a sender. Vector OLE (VOLE) extends OLE by allowing the receiver to learn a linear combination of two vectors held by the 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 function secret sharing (FSS) for multi-point functions and linear codes in which decoding is intractable.

  We present several applications of VOLE generators, including:

  • Efficient secure computation with “silent” preprocessing
  • NIZK with a reusable correlated randomness setup from LPN-style assumptions that are not known to imply public-key encryption.

  Joint work with Elette Boyle, Geoffroy Couteau, and Niv Gilboa.

• Static-Memory-Hard Functions and Modeling the Cost of Space vs Time / Quanquan C. Liu (MIT)

  A series of recent research starting with (Alwen and Serbinenko, STOC 2015) has deepened our understanding of the notion of memory-hardness in cryptography — a useful property of hash functions for deterring large-scale password-cracking attacks — and has shown memory-hardness to have intricate connections with the theory of graph pebbling. Definitions of memory-hardness are not yet unified in the somewhat nascent field of memory-hardness, however, and the guarantees proven to date are with respect to a range of proposed definitions. In this talk, we observe two significant and practical considerations that are not analyzed by existing models of memory- hardness, and propose new models to capture them, accompanied by constructions based on new hard-to-pebble graphs. Our contribution is two-fold, as follows.

  First, existing measures of memory-hardness only account for dynamic memory usage (i.e., memory read/written at runtime), and do not consider static memory usage (e.g., memory on disk). Among other things, this means that memory requirements considered by prior models are inherently upper-bounded by a hash function’s runtime; in contrast, counting static memory would potentially allow quantification of much larger memory requirements, decoupled from runtime. We propose a new definition of static-memory-hard function (SHF) which takes static memory into account: we model static memory usage by oracle access to a large preprocessed string, which may be considered part of the hash function description. Static memory requirements are complementary to dynamic memory requirements: neither can replace the other, and to deter large-scale password-cracking attacks, a hash function will benefit from being both dynamic- memory-hard and static-memory-hard. We give two SHF constructions based on pebbling. To prove static-memory-hardness, we define a new pebble game (“black-magic pebble game”), and new graph constructions with optimal complexity under our proposed measure. Moreover, we provide a prototype implementation of our first SHF construction (which is based on pebbling of a simple “cylinder” graph), providing an initial demonstration of practical feasibility for a limited range of parameter settings.

  Secondly, existing memory-hardness models implicitly assume that the cost of space and time are more or less on par: they consider only linear ratios between the costs of time and space. We propose a new model to capture nonlinear time-space trade-offs: e.g., how is the adversary impacted when space is quadratically more expensive than time? We prove that nonlinear tradeoffs can in fact cause adversaries to employ different strategies from linear tradeoffs.

  Finally, as an additional contribution of independent interest, we present an asymptotically tight graph construction that achieves the best possible space complexity up to log log n-factors for an existing memory-hardness measure called cumulative complexity in the sequential pebbling model.

  Joint work with Thaddeus Dryja and Sunoo Park.

• Foreshadow: Breaking the Virtual Memory Abstraction with Transient Out-of-Order Execution / Ofir Weisse (University of Michigan)

  Foreshadow is a speculative execution attack on Intel processors which allows an attacker to steal sensitive information stored inside personal computers or third party clouds. Foreshadow has two versions, the original attack designed to extract data from SGX enclaves and a Next-Generation version which affects Virtual Machines (VMs), hypervisors (VMM), operating system (OS) kernel memory, and System Management Mode (SMM) memory.

  Foreshadow-SGX: At a high level, SGX is a new feature in modern Intel CPUs which allows computers to protect users’ data even if the entire system falls under the attacker’s control. While it was previously believed that SGX is resilient to speculative execution attacks (such as Meltdown and Spectre), Foreshadow demonstrates how speculative execution can be exploited for reading the contents of SGX-protected memory as well as extracting the machine’s private attestation key. Making things worse, due to SGX’s privacy features, an attestation report cannot be linked to the identity of its signer. Thus, it only takes a single compromised SGX machine to erode trust in the entire SGX ecosystem.

  Foreshadow Next Generation: While investigating the vulnerability that causes Foreshadow, which Intel refers to as “L1 Terminal Fault”, Intel identified two related attacks, which we call Foreshadow-NG. These attacks can potentially be used to read any information residing in the L1 cache, including information belonging to the System Management Mode (SMM), the Operating System’s Kernel, or Hypervisor. Perhaps most devastating, Foreshadow-NG might also be used to read information stored in other virtual machines running on the same third-party cloud, presenting a risk to cloud infrastructure. Finally, in some cases, Foreshadow-NG might bypass previous mitigations against speculative execution attacks, including countermeasures to Meltdown and Spectre.

  Joint work with Jo Van Bulck, Marina Minkin, Daniel Genkin, Baris Kasikci, Frank Piessens, Mark Silberstein, Thomas F. Wenisch, Yuval Yarom, Raoul Strackx.

  https://foreshadowattack.com
  https://www.youtube.com/watch?v=ynB1inl4G3c&t=5s
  https://www.youtube.com/watch?v=8ZF6kX6z7pM

• Secure Computation with Differentially Private Access Patterns / Dov Gordon (George Mason University)

  We explore a new trade-off between efficiency and privacy in secure computation, allowing some bounded amount of leakage to be observed by the computing servers, in the form of access patterns to memory. However, unlike much of the prior work that has proposed such tradeoffs, we give provable guarantees about what is revealed, demonstrating that what is leaked in the process of computing preserves the differential privacy of the users that have contributed data. The leakage allows us to improve on the run-time of existing protocols for a wide class of computations. In this talk we will give some background on both secure computation and differential privacy, before presenting our new results that combine the techniques from these two fields.

  Joint work with Sahar Mazloom.

  https://eprint.iacr.org/2017/1016

Advertisements