## 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.

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

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

#### Coauthors

- Divesh Aggarwal (1)
- Dorit Aharonov (1)
- Bar Alon (1)
- Prabhanjan Ananth (2)
- Per Austrin (1)
- 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 (2)
- Hao Chung (1)
- Serge Fehr (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 (1)
- Xiaohui Liang (1)
- Tai-Ning Liao (1)
- Jyun-Jie Liao (1)
- Han-Hsuan Lin (1)
- Wei-Kai Lin (2)
- Huijia Lin (2)
- Feng-Hao Liu (3)
- Zhenming Liu (1)
- Chi-Jen Lu (1)
- Edward Lui (1)
- Mohammad Mahmoody (1)
- Giulio Malavolta (1)
- Rafail Ostrovsky (1)
- Rafael Pass (12)
- Luowen Qian (1)
- 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)
- Takashi Yamakawa (2)
- Bo-Yin Yang (1)
- Hong-Sheng Zhou (1)