ITC (July 5-7) + Crypto Day (July 8) = Crypto Week
Daniel Wichs
Daniel Wichs
Program:
| 9:00 – 9:30 | Welcome and Breakfast |
| 9:30 – 10:30 | Benny Applebaum (Tel Aviv University) Quadratic Multiparty Randomized Encodings Beyond Honest Majority and Their Applications |
| 11:00 – 12:00 | Rafael Pass (Cornell Tech) Leakage-Resilient Hardness v.s. Randomness |
| 12 – 1:30 | Lunch (provided) |
| 1:30 – 2:30 | Dakshita Khurana (UIUC) SNARGs for P from sub-exponential DDH and QR |
| 3:00 – 4:00 | Wei-Kai Lin (Northeastern) Optimal Single-Server Private Information Retrieval |
Speaker: Benny Applebaum (Tel Aviv University)
Title: Quadratic Multiparty Randomized Encodings Beyond Honest Majority and Their Applications
Abstract:
Multiparty randomized encodings (Applebaum, Brakerski, and Tsabary, SICOMP 2021) reduce the task of securely computing a complicated multiparty functionality f to the task of securely computing a simpler functionality g. The reduction is non-interactive and preserves information-theoretic security against a passive (semi-honest) adversary, also referred to as {\em privacy}. The special case of a degree-2 encoding g (2MPRE) has recently found several applications to secure multiparty computation (MPC) with either information-theoretic security or making black-box access to cryptographic primitives. Unfortunately, as all known constructions are based on information-theoretic MPC protocols in the plain model, they can only be private with an honest majority.
In this work, we break the honest-majority barrier and present the first construction of general 2MPRE that remains secure in the presence of a dishonest majority. Our construction encodes every n-party functionality f by a 2MPRE that tolerates at most t=2n/3 passive corruptions.
We derive several applications including (1) The first non-interactive client-server MPC protocol with perfect privacy against any coalition of a minority of the servers and up to t of the n clients; (2) Completeness of 3-party functionalities under non-interactive t-private reductions; and (3) A single-round t-private reduction from general-MPC to an ideal oblivious transfer (OT). These positive results partially resolve open questions that were posed in several previous works. We also show that t-private 2MPREs are necessary for solving (2) and (3), thus establishing new equivalence theorems between these three notions. Finally, we present a new approach for constructing fully-private 2MPREs based on multi-round protocols in the OT-hybrid model that achieve *perfect privacy* against *active* attacks. Moreover, by slightly restricting the power of the active adversary, we derive an equivalence between these notions. This forms a surprising and quite unique connection between a non-interactive passively-private primitive to an interactive actively-private primitive.
Based on joint work with Yuval Ishai, Or Karni, and Arpita Patra.
Speaker: Rafael Pass (Cornell Tech)
Title: Leakage-Resilient Hardness v.s. Randomness
Abstract:
A central open problem in complexity theory concerns the question of whether all efficient randomized algorithms can be simulated by efficient deterministic algorithms. The celebrated “hardness v.s. randomness” paradigm pioneered by Blum-Micali (SIAM JoC’84), Yao (FOCS’84) and Nisan-Wigderson (JCSS’94) presents hardness assumptions under which prBPP = prP, but these hardness assumptions are not known to also be necessary for such derandomization.
In this work, following the recent work by Chen and Tell (STOC’20) that considers “almost-all-input” hardness of a function f (i.e., hardness of computing f on more than a finite number of inputs), we consider “almost-all-input” *leakage-resilient hardness* of a function f—that is, hardness of computing f(x) even given, say, sqrt(|x|) bits of leakage of f(x). We show that leakage-resilient hardness characterizes derandomization of prBPP (i.e., gives a both *necessary* and *sufficient* condition for derandomization). In more detail, we show that there exists a constant c such that the following are equivalent:
- prBPP = P;
- Existence of a poly-time computable function f : {0, 1}^n -> {0,1}^n that is almost-all-input leakage-resilient hard with respect to n^c-time probabilistic algorithms.
Our characterization naturally extends also to the low-end derandomization regime, to derandomization of MA, and also to average-case derandomization, by appropriately weakening the requirements on the function f.
Joint work with Yanyi Liu
Speaker: Dakshita Khurana (UIUC)
Title: SNARGs for P from sub-exponential DDH and QR
Abstract:
Abstract: We will describe a construction of publicly-verifiable Succinct Non-Interactive Arguments (SNARGs) for arbitrary deterministic computations and bounded space non-deterministic computations from group-based assumptions, without relying on pairings. In particular, assuming the sub-exponential hardness of both the Decisional Diffie-Hellman (DDH) and Quadratic Residuosity (QR) assumptions, we obtain the following results, where n denotes the size of the instance:
1. A SNARG for any language that can be decided in non-deterministic time T and space S with communication complexity and verifier runtime (n+S).T^{o(1)}
2. A SNARG for any language that can be decided in deterministic time T with communication complexity and verifier runtime n.T^{o(1)}.
Speaker: Wei-Kai Lin (Northeastern)
Title: Optimal Single-Server Private Information Retrieval
Abstract:
In this talk, we present a single-server Private Information Retrieval (PIR) scheme, which allows a client to privately query the database from the server. Our construction achieves optimal bandwidth and server computation (up to poly-logarithmic factors), assuming the hardness of the Learning With Errors (LWE) problem.
In the setting of single-server PIR, the server stores an n-bit database, and the client wants to query some bits in the database privately and adaptively so that the server learns nothing about the indices of the queried bits. Our scheme uses ~O(√n) client storage, but it achieves amortized ~O(√n) server and client computation and ~O(1) bandwidth per query, and completes in a single roundtrip, where the ~O notation hides a security parameter and poly-logarithmic factor. In particular, we achieve a significant reduction in bandwidth over the state-of-the-art scheme by Corrigan-Gibbs, Henzinger, and Kogan (Eurocrypt’22): their scheme requires as much as ~O(√n) bandwidth per query, with comparable computational and storage cost as ours. Since they proved that their scheme is nearly optimal in terms of server computation and client storage, our scheme is additionally optimal in bandwidth.
This is a joint work with Mingxun Zhou, Yiannis Tselekounis, and Elaine Shi.