Taiga Hiroka

Bruno Cavalar, Eli Goldin, Matthew Gray et al.

One of the most fundamental problems in distribution testing is the identity testing problem: given samples $x_1,\ldots,x_s$, the goal is to determine whether the samples are drawn from a target distribution $\mathcal{D}$. When $\mathcal{D}$ is a distribution over $\bit^n$, the optimal sample complexity of identity testing is known to be $Ω(\sqrt{2^n})$. Furthermore, most existing results assume that the samples $x_1,\ldots,x_s$ are generated independently from an unknown distribution. In this work, we overcome both of these limitations by initiating study of distribution testing in a more realistic setting. In our model, the unknown distribution is promised to be efficiently samplable, while allowing the observed samples $x_1,\ldots,x_s$ to be adversarially generated and arbitrarily correlated. Under this model, we show that polynomially many samples suffice to verify distributions. We further characterize the computational complexity of verifying classically- and quantumly-samplable distributions. Our techniques also extend to verifications of quantum states. In establishing some of our results, we employ Kolmogorov complexity techniques in a novel manner. We also present multiple applications of Kolmogorov complexity that are of independent interest. In particular, we show that certified randomness with a classical efficient prover can be achieved without computational assumptions when inefficient verification is allowed. Furthermore, we also show that a natural quantum extension of a well-studied Kolmogorov complexity measure provides a good benchmark for certifying sampling-based quantum advantage.

Taiga Hiroka, Tomoyuki Morimae, Ryo Nishimaki et al.

In known constructions of classical zero-knowledge protocols for NP, either of zero-knowledge or soundness holds only against computationally bounded adversaries. Indeed, achieving both statistical zero-knowledge and statistical soundness at the same time with classical verifier is impossible for NP unless the polynomial-time hierarchy collapses, and it is also believed to be impossible even with a quantum verifier. In this work, we introduce a novel compromise, which we call the certified everlasting zero-knowledge proof for QMA. It is a computational zero-knowledge proof for QMA, but the verifier issues a classical certificate that shows that the verifier has deleted its quantum information. If the certificate is valid, even unbounded malicious verifier can no longer learn anything beyond the validity of the statement. We construct a certified everlasting zero-knowledge proof for QMA. For the construction, we introduce a new quantum cryptographic primitive, which we call commitment with statistical binding and certified everlasting hiding, where the hiding property becomes statistical once the receiver has issued a valid certificate that shows that the receiver has deleted the committed information. We construct commitment with statistical binding and certified everlasting hiding from quantum encryption with certified deletion by Broadbent and Islam [TCC 2020] (in a black box way), and then combine it with the quantum sigma-protocol for QMA by Broadbent and Grilo [FOCS 2020] to construct the certified everlasting zero-knowledge proof for QMA. Our constructions are secure in the quantum random oracle model. Commitment with statistical binding and certified everlasting hiding itself is of independent interest, and there will be many other useful applications beyond zero-knowledge.

Taiga Hiroka, Tomoyuki Morimae, Ryo Nishimaki et al.

Broadbent and Islam (TCC '20) proposed a quantum cryptographic primitive called quantum encryption with certified deletion. In this primitive, a receiver in possession of a quantum ciphertext can generate a classical certificate that the encrypted message is deleted. Although their construction is information-theoretically secure, it is limited to the setting of one-time symmetric key encryption (SKE), where a sender and receiver have to share a common key in advance and the key can be used only once. Moreover, the sender has to generate a quantum state and send it to the receiver over a quantum channel in their construction. Although deletion certificates are privately verifiable, which means a verification key for a certificate has to be kept secret, in the definition by Broadbent and Islam, we can also consider public verifiability. In this work, we present various constructions of encryption with certified deletion. - Quantum communication case: We achieve (reusable-key) public key encryption (PKE) and attribute-based encryption (ABE) with certified deletion. Our PKE scheme with certified deletion is constructed assuming the existence of IND-CPA secure PKE, and our ABE scheme with certified deletion is constructed assuming the existence of indistinguishability obfuscation and one-way function. These two schemes are privately verifiable. - Classical communication case: We also achieve PKE with certified deletion that uses only classical communication. We give two schemes, a privately verifiable one and a publicly verifiable one. The former is constructed assuming the LWE assumption in the quantum random oracle model. The latter is constructed assuming the existence of one-shot signatures and extractable witness encryption.