The second post-lockdown GTACS will be at IDC Herzliya, Sun, May 30th, 2021 at the Efi Arazi School of Computer Science.
The event will be held in room A316 in the Arison Bulding. (There will be signs directing you to the location)
PROGRAM
10:00-10:30 Coffee & Registration
10:30-11:00 Tal Rabin, You Only Speak Once -- Secure MPC with Stateless Ephemeral Roles
11:00-11:30 Coffee break (Tea will be permitted)
11:30-12:15 Lior Rotem, Generic Delay Functions: Equivalence to Factoring in RSA Groups and an Impossibility Result in Known-Order Groups
12:15-13:45 Lunch
13:45-14:30 Guy Rothblum, Outcome Indistinguishability
14:30-14:45 Coffee break
14:45-15:30 Yael Kalai, The Fiat-Shamir Protocol for Succinct Protocols
15:30-16:00 Coffee break
16:00-16:30 Hemanta Maji, Computational Hardness of Optimal Fair Computation (On the big screen, with accompanying snacks)
ABSTRACTS
You Only Speak Once -- Secure MPC with Stateless Ephemeral Roles
Tal Rabin, Algorand Foundation and University of Pennsylvania
Abstract:
The inherent difficulty of maintaining stateful environments over long periods of time gave rise to the paradigm of serverless computing, where mostly-stateless components are deployed on demand to handle computation tasks, and are teared down once their task is complete. Serverless architecture could offer the added benefit of improved resistance to targeted denial-of-service attacks. Realizing such protection, requires that the protocol only uses stateless parties. Perhaps the most famous example of this style of protocols is the Nakamoto consensus protocol used in Bitcoin. We refer to this stateless property as the You-Only-Speak-Once (YOSO) property, and initiate the formal study of it within a new YOSO model. Our model is centered around the notion of roles, which are stateless parties that can only send a single message. Furthermore, we describe several techniques for achieving YOSO MPC; both computational and information theoretic.
Lior Rotem, Hebrew University
Abstract:
Despite the fundamental importance of delay functions, the main known delay function which offers both sufficient structure for realizing time-lock puzzles and verifiable delay functions, as well as a realistic level of practicality is the “iterated squaring” function of Rivest, Shamir and Wagner in hidden-order groups. The challenges of basing the sequentiality of iterated squaring on well-established assumptions, or of constructing new delay functions in well-understood cyclic groups of known order, have remained open for over two decades. In this talk, I will present both upper bounds, connecting the sequentiality of iterated squaring in RSA groups to the factoring assumption, and a lower bound, ruling out the existence of generic-group delay functions in cyclic groups of known order.
This talk is based on joint works with Gil Segev and Ido Shahaf.
Guy Rothblum, The Weizmann Institute of Science
Abstract:
Prediction algorithms assign numbers to individuals that are popularly understood as individual "probabilities" -- what is the probability of 5-year survival after cancer diagnosis? -- and which increasingly form the basis for life-altering decisions. Drawing on an understanding of computational indistinguishability developed in complexity theory and cryptography, we introduce Outcome Indistinguishability: we require that the predicted outcome distribution be indistinguishable from outcomes observed in the real world.
We investigate a hierarchy of Outcome Indistinguishability definitions, whose stringency increases with the degree to which distinguishers may access the predictor in question. First, we provide constructions at all levels of the hierarchy. Then, leveraging recently-developed machinery for proving average-case fine-grained hardness, we obtain lower bounds on the complexity of the more stringent forms of Outcome Indistinguishability. This hardness result provides the first scientific grounds for the political argument that, when inspecting algorithmic risk prediction instruments, auditors should be granted oracle access to the algorithm, not simply historical predictions.
Joint work with Cynthia Dwork, Michael Kim, Omer Reingold and Gal Yona.
The Fiat-Shamir Protocol for Succinct Protocols
Yael Kalai, Microsoft Research
Abstract:
Recently there has been significant progress in proving the security of the Fiat-Shamir paradigm, when applied to statistically sound proofs, culminating with a series of recent works which proved its security when applied to some (zero-knowledge, non-succinct) protocols, under the standard LWE assumption.
In this talk, we will show the security of the Fiat-Shamir paradigm when applied to the succinct GKR protocol, under the sub-exponential hardness of LWE, yielding the first SNARG for bounded depth computations, from a standard and post-quantum assumption. As a corollary we obtain the (sub-exponential) average-case hardness of PPAD assuming the sub-exponential hardness of LWE.
To obtain these results, we introduce and construct (assuming the sub-exponential hardness of LWE) a new cryptographic primitive: a lossy correlation-intractable hash function family. We use this primitive to soundly instantiate the Fiat-Shamir transform for a large class of interactive proofs, including the interactive sum-check protocol and the GKR protocol.
Computational Hardness of Optimal Fair Computation
Hemanta Maji, Purdue University
Abstract:
Characterizing the limits of achievable security using the most conservative hardness of computation assumptions is one of the fundamental principles of cryptographic research. For instance, guaranteeing output delivery to honest parties when adversarial parties may abort prematurely during the protocol execution is significantly challenging. Against such powerful adversaries, the hardness of computation assumptions necessary and sufficient to achieve various security levels is relatively not well understood.
In the early 1980s, groundbreaking research introduced coin-tossing protocols using private-key cryptographic primitives to ensure that an adversary can change the honest party's output distribution by at most 1/sqrt(r) in r-round protocols. Two decades later, a sequence of seminal results, relying on strong public-key cryptographic primitives, constructed protocols where an adversary can change the output distribution only by 1/r, which coincides with the optimal achievable security.
In light of these results, it is natural to wonder whether public-key cryptographic primitives are necessary to achieve this higher security threshold. Furthermore, do the coin-tossing protocols from the 1980s achieve the best possible security relying on private-key cryptographic primitives? This talk shall present recent results resolving these long-standing foundational problems in cryptography.
The key technical innovation is a potential-based proof-technique introduced in a sequence of our recent works.