中央研究院 資訊科學研究所

Small Memory Robust Simulation of Client-Server Interactive Protocols over Oblivious Noisy Channels
Prof. Hubert T.H. Chan (The University of Hong Kong)

Abstract:
We revisit the problem of low-memory robust simulation of interactive protocols over noisy channels. Haeupler [FOCS 2014] considered robust simulation of two-party interactive protocols over oblivious, as well as adaptive, noisy channels. Since the simulation does not need to have fixed communication pattern, the achieved communication rates can circumvent the lower bound proved by Kol and Raz [STOC 2013]. However, a drawback of this approach is that each party needs to remember the whole history of the simulated transcript. In a subsequent manuscript, Haeupler and Resch considered low-memory simulation. The idea was to view the original protocol as a computational DAG and only the identities of the nodes are saved (as opposed to the whole transcript history) for backtracking to reduce memory usage.
In this paper, we consider low-memory robust simulation of more general client-server interactive protocols, in which a leader communicates with other members/servers, who do not communicate among themselves; this setting can be applied to information-theoretic multi-server Private Information Retrieval (PIR) schemes. We propose an information-theoretic technique that converts any correct PIR protocol that assumes reliable channels, into a protocol which is both correct and private in the presence of a noisy channel while keeping the space complexity to a minimum. Despite the huge attention that PIR protocols have received in the literature, the existing works assume that the parties communicate using noiseless channels.
Moreover, we observe that the approach of Haeupler and Resch to just save the nodes in the aforementioned DAG without taking the transcript history into account will lead to a correctness issue even for oblivious corruptions. We resolve this issue by saving hashes of prefixes of past transcripts. Departing from the DAG representation also allows us to accommodate scenarios where a party can simulate its part of the protocol without any extra knowledge (such as the DAG representation of the whole protocol). In the the two-party setting, our simulation has the same dependence on the error rate as in the work of Haeupler, and in the client-server setting it also depends on the number of servers. Furthermore, since our approach does not remember the complete transcript history, our current technique can defend only against oblivious corruptions.

Adaptively Secure Garbling Schemes for Parallel Computations
Mr. Luowen Qian (Boston University)

Abstract:
Garbling scheme is one of the fundamental techniques in cryptography. Recent works constructed several adaptively secure garbling schemes. In this talk, we explore constructing parallelly efficient adaptive garbling schemes. This notion is especially useful when applying adaptive garbling schemes to delegating evaluation of one-time parallel programs. We construct the first adaptively secure garbling scheme based on standard public-key assumptions for garbling a circuit that simultaneously achieves a near-optimal online complexity and preserves the parallel efficiency for evaluating the garbled circuit. We take one step further to construct the first adaptively secure garbling scheme for parallel RAM (PRAM) programs under standard assumptions that preserves the parallel efficiency. Previous such constructions we are aware of is from strong assumptions like indistinguishability obfuscation Ananth et al. (TCC 2016).

Lunch

The capabilities and limits of quantum algorithms
Dr. Nai-Hui Chia (The University of Texas at Austin)

Abstract:
Quantum computing has notable impacts on computer science in recent years. While quantum computers are about to achieve so-called "quantum supremacy" (i.e., solving some classically-intractable computational tasks), it is the right time to understand the capabilities and limits of near-term and general quantum computers.
In this talk, I will address the following two questions: 1) What is the power of near-term quantum computers? 2) What problems in machine learning and data analysis can have quantum speedups, and what are the limits? We will first see that a general quantum computer is indeed more powerful than a hybrid classical-quantum computer that only has limited quantum circuit depth relative to an oracle. Then, I will show polylog(n) classical algorithms for problems thought to have had exponential quantum speedups with input/output formats analogous to existing quantum algorithms, including SVM, low-rank linear system, recommendation system, and more. This implies that existing quantum machine learning algorithms have not achieved exponential speedups. Finally, I will discuss polynomial quantum speedups for fundamental problems in data analysis and their limits under plausible assumptions in complexity theory.

Coffee Break

MPC for MPC: Secure Computation on a Massively Parallel Computing Architecture
Mr. Wei-Kai Lin (Cornell University)