## CryptoDB

### Kai-Min Chung

#### Publications

**Year**

**Venue**

**Title**

2022

PKC

A Note on the Post-Quantum Security of (Ring) Signatures
📺
Abstract

This work revisits the security of classical signatures and ring signatures in a quantum world. For (ordinary) signatures, we focus on the arguably preferable security notion of {\em blind-unforgeability} recently proposed by Alagic et al.\ (Eurocrypt'20). We present two {\em short} signature schemes achieving this notion: one is in the quantum random oracle model, assuming quantum hardness of SIS; and the other is in the plain model, assuming quantum hardness of LWE with super-polynomial modulus. Prior to this work, the only known blind-unforgeable schemes are Lamport's one-time signature and the Winternitz one-time signature, and both of them are in the quantum random oracle model.
For ring signatures, the recent work by Chatterjee et al.\ (Crypto'21) proposes a definition trying to capture adversaries with quantum access to the signer. However, it is unclear if their definition, when restricted to the classical world, is as strong as the standard security notion for ring signatures. They also present a construction that only {\em partially} achieves (even) this seeming weak definition, in the sense that the adversary can only conduct superposition attacks over the messages, but not the rings. We propose a new definition that does not suffer from the above issue. Our definition is an analog to the blind-unforgeability in the ring signature setting. Moreover, assuming the quantum hardness of LWE, we construct a compiler converting any blind-unforgeable (ordinary) signatures to a ring signature satisfying our definition.

2022

EUROCRYPT

Constant-round Blind Classical Verification of Quantum Sampling
📺
Abstract

In a recent breakthrough, Mahadev constructed a classical verification of quantum computation (CVQC) protocol for a classical client to delegate decision problems in BQP to an untrusted quantum prover under computational assumptions. In this work, we explore further the feasibility of CVQC with the more general sampling problems in BQP and with the desirable blindness property. We contribute affirmative solutions to both as follows.
* Motivated by the sampling nature of many quantum applications (e.g., quantum algorithms for machine learning and quantum supremacy tasks), we initiate the study of CVQC for quantum sampling problems (denoted by SampBQP). More precisely, in a CVQC protocol for a SampBQP problem, the prover and the verifier are given an input x\in{0, 1}^n and a quantum circuit C, and the goal of the classical client is to learn a sample from the output z\leftarrow C(x) up to a small error, from its interaction with an untrusted prover. We demonstrate its feasibility by constructing a four-message CVQC protocol for SampBQP based on the quantum Learning With Errors assumption.
* The blindness of CVQC protocols refers to a property of the protocol where the prover learns nothing, and hence is blind, about the client’s input. It is a highly desirable property that has been intensively studied for the delegation of quantum computation. We provide a simple yet powerful generic compiler that transforms any CVQC protocol to a blind one while preserving its completeness and soundness errors as well as the number of rounds.
Applying our compiler to (a parallel repetition of) Mahadev’s CVQC protocol for BQP and our CVQC protocol for SampBQP yields the first constant-round blind CVQC protocol for BQP and SampBQP respectively, with negligible and inverse polynomial soundness errors respectively, and negligible completeness errors.

2022

CRYPTO

Post-Quantum Simulatable Extraction with Minimal Assumptions: Black-Box and Constant-Round
📺
Abstract

From the minimal assumption of post-quantum semi-honest oblivious transfers, we build the first $\epsilon$-simulatable two-party computation (2PC) against quantum polynomial-time (QPT) adversaries that is both constant-round and black-box (for both the construction and security reduction). A recent work by Chia, Chung, Liu, and Yamakawa (FOCS'21) shows that post-quantum 2PC with standard simulation-based security is impossible in constant rounds, unless either $NP \subseteq BQP$ or relying on non-black-box simulation. The $\epsilon$-simulatability we target is a relaxation of the standard simulation-based security that allows for an arbitrarily small noticeable simulation error $\epsilon$. Moreover, when quantum communication is allowed, we can further weaken the assumption to post-quantum secure one-way functions (PQ-OWFs), while maintaining the constant-round and black-box property.
Our techniques also yield the following set of constant-round and black-box two-party protocols secure against QPT adversaries, only assuming black-box access to PQ-OWFs:
- extractable commitments for which the extractor is also an $\epsilon$-simulator;
- $\epsilon$-zero-knowledge commit-and-prove whose commit stage is extractable with $\epsilon$-simulation;
- $\epsilon$-simulatable coin-flipping;
- $\epsilon$-zero-knowledge arguments of knowledge for $NP$ for which the knowledge extractor is also an $\epsilon$-simulator;
- $\epsilon$-zero-knowledge arguments for $QMA$.
At the heart of the above results is a black-box extraction lemma showing how to efficiently extract secrets from QPT adversaries while disturbing their quantum state in a controllable manner, i.e., achieving $\epsilon$-simulatability of the after-extraction state of the adversary.

2022

CRYPTO

On the Impossibility of Key Agreements from Quantum Random Oracles
📺
Abstract

We study the following question, ﬁrst publicly posed by Hosoyamada and Yamakawa in 2018. Can parties A, B with local quantum computing power rely (only) on a random oracle and classical communication to agree on a key? (Note that A, B can now query the random oracle at quantum superpositions.) We make the ﬁrst progress on the question above and prove the following.
– When only one of the parties A is classical and the other party B is quantum powered, as long as they ask a total of d oracle queries and agree on a key with probability 1, then there is always a way to break the key agreement by asking O(d^2) number of classical oracle queries.
– When both parties can make quantum queries to the random oracle, we introduce a natural conjecture, which if true would imply attacks with poly(d) classical queries to the random oracle. Our conjecture, roughly speaking, states that the multiplication of any two degree-d real-valued polynomials over the Boolean hypercube of inﬂuence at most δ = 1/ poly(d) is nonzero. We then prove our conjecture for exponentially small inﬂuences, which leads to an (unconditional) classical 2^O(md)-query attack on any such key agreement protocol, where m is the random oracle’s output length.
– Since our attacks are classical, we then ask whether it is possible to ﬁnd such classical attacks in general. We prove a barrier for this approach, by showing that if the folklore “simulation conjecture” about the possibility of simulating efﬁcient-query quantum algorithms classically is false, then that implies a possible quantum protocol that cannot be broken by classical adversaries.

2022

ASIACRYPT

Collusion-Resistant Functional Encryption for RAMs
Abstract

In recent years, functional encryption (FE) has established
itself as one of the fundamental primitives in cryptography. The choice
of model of computation to represent the functions associated with the
functional keys plays a critical role in the complexity of the algorithms
of an FE scheme. Historically, the functions are represented as circuits.
However, this results in the decryption time of the FE scheme growing
proportional to not only the worst case running time of the function but
also the size of the input, which in many applications can be quite large.
In this work, we present the first construction of a public-key collusion
resistant FE scheme, where the functions, associated with the keys, are
represented as random access machines (RAMs). We base the security
of our construction on the existence of: (i) public-key collusion-resistant
FE for circuits and, (ii) public-key doubly-efficient private-information
retrieval [Boyle et al., Canetti et al., TCC 2017]. Our scheme enjoys
many nice efficiency properties, including input-specific decryption time.
We also show how to achieve FE for RAMs in the bounded-key setting
with weaker efficiency guarantees from laconic oblivious transfer, which
can be based on standard cryptographic assumptions. En route to achieving
our result, we present conceptually simpler constructions of succinct
garbling for RAMs [Canetti et al., Chen et al., ITCS 2016] from weaker
assumptions.

2021

EUROCRYPT

On the Compressed-Oracle Technique, and Post-Quantum Security of Proofs of Sequential Work
📺
Abstract

We revisit the so-called compressed oracle technique, introduced by Zhandry for analyzing quantum algorithms in the quantum random oracle model (QROM). To start off with, we offer a concise exposition of the technique, which easily extends to the parallel-query QROM, where in each query-round the considered algorithm may make several queries to the QROM in parallel. This variant of the QROM allows for a more fine-grained query-complexity analysis.
Our main technical contribution is a framework that simplifies the use of (the parallel-query generalization of) the compressed oracle technique for proving query complexity results. With our framework in place, whenever applicable, it is possible to prove quantum query complexity lower bounds by means of purely classical reasoning. More than that, for typical examples the crucial classical observations that give rise to the classical bounds are sufficient to conclude the corresponding quantum bounds.
We demonstrate this on a few examples, recovering known results but also obtaining new results. Our main target is the hardness of finding a q-chain with fewer than q parallel queries, i.e., a sequence x_0, x_1, ..., x_q with x_i = H(x_{i-1}) for all 1 \leq i \leq q.
The above problem of finding a hash chain is of fundamental importance in the context of proofs of sequential work. Indeed, as a concrete cryptographic application of our techniques, we prove quantum security of the ``Simple Proofs of Sequential Work'' by Cohen and Pietrzak.

2021

CRYPTO

On the Concurrent Composition of Quantum Zero-Knowledge
📺
Abstract

We study the notion of zero-knowledge secure against quantum polynomial-time verifiers (referred to as quantum zero-knowledge) in the concurrent composition setting.
Despite being extensively studied in the classical setting, concurrent composition in the quantum setting has hardly been studied. \par We initiate a formal study of concurrent quantum zero-knowledge. Our results are as follows:
- Bounded Concurrent QZK for NP and QMA: Assuming post-quantum one-way functions, there exists a quantum zero-knowledge proof system for NP in the bounded concurrent setting. In this setting, we fix a priori the number of verifiers that can simultaneously interact with the prover. Under the same assumption, we also show that there exists a quantum zero-knowledge proof system for QMA in the bounded concurrency setting.
- Quantum Proofs of Knowledge: Assuming quantum hardness of learning with errors (QLWE), there exists a bounded concurrent zero-knowledge proof system for NP satisfying quantum proof of knowledge property.
Our extraction mechanism simultaneously allows for extraction probability to be negligibly close to acceptance probability (extractability) and also ensures that the prover's state after extraction is statistically close to the prover's state after interacting with the verifier (simulatability).
Even in the standalone setting, the seminal work of [Unruh EUROCRYPT'12], and all its followups, satisfied a weaker version of extractability property and moreover, did not achieve simulatability. Our result yields a proof of {\em quantum knowledge} system for QMA with better parameters than prior works.

2021

CRYPTO

Game-Theoretic Fairness Meets Multi-Party Protocols: The Case of Leader Election
📺
Abstract

Suppose that $n$ players
want to elect a random leader and they communicate by posting
messages to a common broadcast channel.
This problem is called leader election, and it is
fundamental to the distributed systems and cryptography literature.
Recently, it has attracted renewed interests
due to its promised applications in decentralized environments.
In a game theoretically fair leader election protocol, roughly speaking,
we want that even a majority coalition
cannot increase its own chance of getting
elected, nor hurt the chance of any honest individual.
The folklore tournament-tree
protocol, which completes in logarithmically many rounds,
can easily be shown to satisfy game theoretic security. To the best of our knowledge,
no sub-logarithmic round protocol was known in the setting that we consider.
We show that
by adopting an appropriate notion of approximate game-theoretic fairness,
and under standard cryptographic assumption,
we can achieve
$(1-1/2^{\Theta(r)})$-fairness in $r$ rounds for $\Theta(\log \log n) \leq r \leq \Theta(\log n)$,
where $n$ denotes the number of players. In particular, this means that we can approximately match the fairness of the tournament tree protocol using as few as $O(\log \log n)$ rounds.
We also prove a lower bound showing that
logarithmically many rounds are necessary if we restrict ourselves
to ``perfect'' game-theoretic fairness
and protocols that are
``very similar in structure'' to the tournament-tree protocol.
Although leader election is a well-studied problem in other contexts in distributed
computing,
our work is the first exploration of the round complexity
of {\it game-theoretically
fair} leader election in the presence of a possibly majority coalition.
As a by-product of our exploration,
we suggest a new, approximate game-theoretic fairness
notion, called ``approximate sequential fairness'',
which provides a more desirable solution concept than some previously
studied approximate fairness notions.

2021

CRYPTO

A Black-Box Approach to Post-Quantum Zero-Knowledge in Constant Rounds
📺
Abstract

In a recent seminal work, Bitansky and Shmueli (STOC '20) gave the first construction of a constant round zero-knowledge argument for NP secure against quantum attacks. However, their construction has several drawbacks compared to the classical counterparts. Specifically, their construction only achieves computational soundness, requires strong assumptions of quantum hardness of learning with errors (QLWE assumption) and the existence of quantum fully homomorphic encryption (QFHE), and relies on non-black-box simulation. In this paper, we resolve these issues at the cost of weakening the notion of zero-knowledge to what is called ϵ-zero-knowledge. Concretely, we construct the following protocols:
- We construct a constant round interactive proof for NP that satisfies statistical soundness and black-box ϵ-zero-knowledge against quantum attacks assuming the existence of collapsing hash functions, which is a quantum counterpart of collision-resistant hash functions. Interestingly, this construction is just an adapted version of the classical protocol by Goldreich and Kahan (JoC '96) though the proof of ϵ-zero-knowledge property against quantum adversaries requires novel ideas.
- We construct a constant round interactive argument for NP that satisfies computational soundness and black-box ϵ-zero-knowledge against quantum attacks only assuming the existence of post-quantum one-way functions.
At the heart of our results is a new quantum rewinding technique that enables a simulator to extract a committed message of a malicious verifier while simulating verifier's internal state in an appropriate sense.

2021

CRYPTO

Round Efficient Secure Multiparty Quantum Computation with Identifiable Abort
📺
Abstract

A recent result by Dulek et al. (EUROCRYPT 2020) showed a secure protocol for computing any quantum circuit even without the presence of an honest majority. Their protocol, however, is susceptible to a ``denial of service'' attack and allows even a single corrupted party to force an abort. We propose the first quantum protocol that admits security-with-identifiable-abort, which allows the honest parties to agree on the identity of a corrupted party in case of an abort.
Additionally, our protocol is the first to have the property that the number of rounds where quantum communication is required is independent of the circuit complexity. Furthermore, if there exists a post-quantum secure classical protocol whose round complexity is independent of the circuit complexity, then our protocol has this property as well. Our protocol is secure under the assumption that classical quantum-resistant fully homomorphic encryption schemes with decryption circuit of logarithmic depth exist. Interestingly, our construction also admits a reduction from quantum fair secure computation to classical fair secure computation.

2020

TCC

Classical Verification of Quantum Computations with Efficient Verifier
📺
Abstract

In this paper, we extend the protocol of classical verification of quantum computations (CVQC) recently proposed by Mahadev to make the verification efficient.
Our result is obtained in the following three steps:
\begin{itemize}
\item We show that parallel repetition of Mahadev's protocol has negligible soundness error. This gives the first constant round CVQC protocol with negligible soundness error. In this part, we only assume the quantum hardness of the learning with error (LWE) problem similar to Mahadev's work.
\item We construct a two-round CVQC protocol in the quantum random oracle model (QROM) where a cryptographic hash function is idealized to be a random function.
This is obtained by applying the Fiat-Shamir transform to the parallel repetition version of Mahadev's protocol.
\item We construct a two-round CVQC protocol with an efficient verifier in the CRS+QRO model where both prover and verifier can access a (classical) common reference string generated by a trusted third party in addition to quantum access to QRO.
Specifically, the verifier can verify a $\mathsf{QTIME}(T)$ computation in time $\mathsf{poly}(\lambda,\log T)$ where $\lambda$ is the security parameter.
For proving soundness, we assume that a standard model instantiation of our two-round protocol with a concrete hash function (say, SHA-3) is sound and the existence of post-quantum indistinguishability obfuscation and post-quantum fully homomorphic encryption in addition to the quantum hardness of the LWE problem.
\end{itemize}

2019

EUROCRYPT

A Quantum-Proof Non-malleable Extractor
📺
Abstract

In privacy amplification, two mutually trusted parties aim to amplify the secrecy of an initial shared secret X in order to establish a shared private key K by exchanging messages over an insecure communication channel. If the channel is authenticated the task can be solved in a single round of communication using a strong randomness extractor; choosing a quantum-proof extractor allows one to establish security against quantum adversaries.In the case that the channel is not authenticated, this simple solution is no longer secure. Nevertheless, Dodis and Wichs (STOC’09) showed that the problem can be solved in two rounds of communication using a non-malleable extractor, a stronger pseudo-random construction than a strong extractor.We give the first construction of a non-malleable extractor that is secure against quantum adversaries. The extractor is based on a construction by Li (FOCS’12), and is able to extract from source of min-entropy rates larger than 1 / 2. Combining this construction with a quantum-proof variant of the reduction of Dodis and Wichs, due to Cohen and Vidick (unpublished) we obtain the first privacy amplification protocol secure against active quantum adversaries.

2019

EUROCRYPT

On Quantum Advantage in Information Theoretic Single-Server PIR
📺
Abstract

In (single-server) Private Information Retrieval (PIR), a server holds a large database
$${\mathtt {DB}}$$
of size n, and a client holds an index
$$i \in [n]$$
and wishes to retrieve
$${\mathtt {DB}}[i]$$
without revealing i to the server. It is well known that information theoretic privacy even against an “honest but curious” server requires
$$\varOmega (n)$$
communication complexity. This is true even if quantum communication is allowed and is due to the ability of such an adversarial server to execute the protocol on a superposition of databases instead of on a specific database (“input purification attack”).Nevertheless, there have been some proposals of protocols that achieve sub-linear communication and appear to provide some notion of privacy. Most notably, a protocol due to Le Gall (ToC 2012) with communication complexity
$$O(\sqrt{n})$$
, and a protocol by Kerenidis et al. (QIC 2016) with communication complexity
$$O(\log (n))$$
, and O(n) shared entanglement.We show that, in a sense, input purification is the only potent adversarial strategy, and protocols such as the two protocols above are secure in a restricted variant of the quantum honest but curious (a.k.a specious) model. More explicitly, we propose a restricted privacy notion called anchored privacy, where the adversary is forced to execute on a classical database (i.e. the execution is anchored to a classical database). We show that for measurement-free protocols, anchored security against honest adversarial servers implies anchored privacy even against specious adversaries.Finally, we prove that even with (unlimited) pre-shared entanglement it is impossible to achieve security in the standard specious model with sub-linear communication, thus further substantiating the necessity of our relaxation. This lower bound may be of independent interest (in particular recalling that PIR is a special case of Fully Homomorphic Encryption).

2019

TCC

Adaptively Secure Garbling Schemes for Parallel Computations
Abstract

We construct the first adaptively secure garbling scheme based on standard public-key assumptions for garbling a circuit
$$C: \{0, 1\}^n \mapsto \{0, 1\}^m$$
that simultaneously achieves a near-optimal online complexity
$$n + m + \textsf {poly} (\lambda , \log |C|)$$
(where
$$\lambda $$
is the security parameter) and preserves the parallel efficiency for evaluating the garbled circuit; namely, if the depth of C is d, then the garbled circuit can be evaluated in parallel time
$$d \cdot \textsf {poly} (\log |C|, \lambda )$$
. In particular, our construction improves over the recent seminal work of [GS18], which constructs the first adaptively secure garbling scheme with a near-optimal online complexity under the same assumptions, but the garbled circuit can only be evaluated gate by gate in a sequential manner. Our construction combines their novel idea of linearization with several new ideas to achieve parallel efficiency without compromising online complexity.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. Our construction is based on the work of [GOS18] for adaptively secure garbled RAM, but again introduces several new ideas to handle parallel RAM computation, which may be of independent interests. As an application, this yields the first constant round secure computation protocol for persistent PRAM programs in the malicious settings from standard assumptions.

2018

TCC

Game Theoretic Notions of Fairness in Multi-party Coin Toss
Abstract

Coin toss has been extensively studied in the cryptography literature, and the well-accepted notion of fairness (henceforth called strong fairness) requires that a corrupt coalition cannot cause non-negligible bias. It is well-understood that two-party coin toss is impossible if one of the parties can prematurely abort; further, this impossibility generalizes to multiple parties with a corrupt majority (even if the adversary is computationally bounded and fail-stop only).Interestingly, the original proposal of (two-party) coin toss protocols by Blum in fact considered a weaker notion of fairness: imagine that the (randomized) transcript of the coin toss protocol defines a winner among the two parties. Now Blum’s notion requires that a corrupt party cannot bias the outcome in its favor (but self-sacrificing bias is allowed). Blum showed that this weak notion is indeed attainable for two parties assuming the existence of one-way functions.In this paper, we ask a very natural question which, surprisingly, has been overlooked by the cryptography literature: can we achieve Blum’s weak fairness notion in multi-party coin toss? What is particularly interesting is whether this relaxation allows us to circumvent the corrupt majority impossibility that pertains to strong fairness. Even more surprisingly, in answering this question, we realize that it is not even understood how to define weak fairness for multi-party coin toss. We propose several natural notions drawing inspirations from game theory, all of which equate to Blum’s notion for the special case of two parties. We show, however, that for multiple parties, these notions vary in strength and lead to different feasibility and infeasibility results.

#### Program Committees

- Asiacrypt 2021
- Eurocrypt 2021
- TCC 2020
- PKC 2020
- Eurocrypt 2019
- Crypto 2019
- TCC 2019
- PKC 2018
- Asiacrypt 2017
- TCC 2017
- Asiacrypt 2015
- TCC 2015
- Asiacrypt 2014
- TCC 2014
- Crypto 2013

#### Coauthors

- Divesh Aggarwal (1)
- Dorit Aharonov (1)
- Bar Alon (1)
- Prabhanjan Ananth (3)
- Per Austrin (2)
- Eleanor Birrell (1)
- Elette Boyle (3)
- Zvika Brakerski (1)
- T-H. Hubert Chan (1)
- T.-H. Hubert Chan (1)
- Rahul Chatterjee (1)
- Yu-Chi Chen (1)
- Yi-Hsiu Chen (1)
- Nai-Hui Chia (3)
- Hao Chung (2)
- Xiong Fan (1)
- Serge Fehr (1)
- Shiuan Fu (1)
- Ayal Green (1)
- Yue Guo (1)
- Mi-Ying Huang (1)
- Yu-Hsuan Huang (1)
- Yael Tauman Kalai (2)
- Jonathan Katz (1)
- Rolando L. La Placa (1)
- Ching-Yi Lai (1)
- Yi Lee (2)
- Xiaohui Liang (2)
- Tai-Ning Liao (1)
- Jyun-Jie Liao (1)
- Han-Hsuan Lin (2)
- Wei-Kai Lin (2)
- Yao-Ting Lin (1)
- Huijia Lin (2)
- Feng-Hao Liu (3)
- Zhenming Liu (1)
- Chi-Jen Lu (1)
- Edward Lui (1)
- Mohammad Mahmoody (2)
- Giulio Malavolta (1)
- Rafail Ostrovsky (1)
- Rafael Pass (12)
- Luowen Qian (2)
- Ran Raz (1)
- Or Sattath (1)
- Karn Seth (1)
- Yu-Ching Shen (1)
- Elaine Shi (3)
- Sidharth Telang (1)
- Wei-Lung Dustin Tseng (1)
- Salil P. Vadhan (1)
- Muthuramakrishnan Venkitasubramaniam (1)
- Thomas Vidick (1)
- Ivan Visconti (1)
- Ting Wen (1)
- Xiaodi Wu (1)
- Takashi Yamakawa (3)
- Bo-Yin Yang (1)
- Hong-Sheng Zhou (1)