Post-Quantum Zero-Knowledge with Space-Bounded Simulation Prabhanjan Ananth UCSBAlex B. Grilo

2025-04-26 0 0 935.46KB 42 页 10玖币

侵权投诉

Post-Quantum Zero-Knowledge with Space-Bounded Simulation∗

Prabhanjan Ananth†

UCSB

Alex B. Grilo‡

Sorbonne Université, CNRS, LIP6

Abstract

The traditional deﬁnition of quantum zero-knowledge stipulates that the knowledge gained by

any quantum polynomial-time veriﬁer in an interactive protocol can be simulated by a quantum

polynomial-time algorithm. One drawback of this deﬁnition is that it allows the simulator

to consume signiﬁcantly more computational resources than the veriﬁer. We argue that this

drawback renders the existing notion of quantum zero-knowledge not viable for certain settings,

especially when dealing with near-term quantum devices.

In this work, we initiate a ﬁne-grained notion of post-quantum zero-knowledge that is more

compatible with near-term quantum devices. We introduce the notion of (𝑠, 𝑓 )space-bounded

quantum zero-knowledge. In this new notion, we require that an 𝑠-qubit malicious veriﬁer can

be simulated by a quantum polynomial-time algorithm that uses at most 𝑓(𝑠)-qubits, for some

function 𝑓(·), and no restriction on the amount of the classical memory consumed by either the

veriﬁer or the simulator.

We explore this notion and establish both positive and negative results:

•For veriﬁers with logarithmic quantum space 𝑠and (arbitrary) polynomial classical space,

we show that (𝑠, 𝑓)-space-bounded QZK, for 𝑓(𝑠) = 2𝑠, can be achieved based on the

existence of post-quantum one-way functions. Moreover, our protocol runs in constant

rounds.

•For veriﬁers with super-logarithmic quantum space 𝑠, assuming the existence of post-

quantum secure one-way functions, we show that (𝑠, 𝑓)-space-bounded QZK protocols,

with fully black box simulation (classical analogue of black-box simulation) can only be

achieved for languages in BQP.

1 Introduction

Zero-knowledge is a foundational notion in cryptography. Invented in the 80s by Goldwasser, Micali

and Rackoﬀ [GMR85], this notion has slowly transitioned from being a purely theoretical notion

to having applications in practice. Some notable applications of zero-knowledge include secure

computation [GMW87] and cryptocurrencies [SCG+14].

A zero-knowledge proof (or argument) system for a language in NP is an interactive protocol

between a prover, who receives as input an instance-witness pair (𝑥, 𝑤)and a veriﬁer, who receives

as input an instance 𝑥. The zero-knowledge property states that the veriﬁer, after interacting

∗This work was done (in part) while the authors were visiting the Simons Institute for the Theory of Computing.

This research was supported in part by the National Science Foundation under Grant No. NSF PHY-1748958.

†Email: prabhanjan@cs.ucsb.edu

‡Email: alex.bredariol-grilo@lip6.fr

arXiv:2210.06093v1 [quant-ph] 12 Oct 2022

with the prover, should not gain any information about the witness beyond what is leaked by the

statement. That is, in the words of the inventors of zero-knowledge [GMR85], “. . . what the veriﬁer

sees in the protocol (even if he cheats) should be something which the veriﬁer could have computed

himself. . .". Formally, we deﬁne the notion of a simulator and we require that the view of the veriﬁer

after interacting with the prover should be computationally indistinguishable from the output of

the simulator.

When we consider polynomial-time veriﬁers we typically require the simulator to run in poly-

nomial time. In particular, the storage and the computational power utilized by the simulator can

be an arbitrary polynomial, respectively, in the storage and computational power of the veriﬁer.

One might worry that this deﬁnition is not strong enough: the veriﬁer might gain knowledge from

a protocol that would need far more computational resources in order for it to have computed by

itself.1Nonetheless, this is a reasonable assumption to make in the present day as getting access to

more computational resources is cheaper than ever before.

Quantum Zero-Knowledge. The advancement in quantum technology forces us to re-think the

design of cryptographic protocols. But even before we build protocols that are secure against quan-

tum adversaries, we need to ﬁrst focus on formal deﬁnitions and appropriately deﬁne post-quantum

security for existing cryptographic primitives. We focus on the notion of zero-knowledge against

malicious quantum veriﬁers, also referred to as quantum zero-knowledge. One approach to for-

malize this deﬁnition is to modify the deﬁnition of classical zero-knowledge as follows: instead of

considering (classical) probabilistic polynomial-time adversaries in the traditional zero-knowledge

deﬁnition, we instead consider quantum polynomial-time (QPT) adversaries. And instead of mod-

eling the auxiliary input to the veriﬁer as a classical string, we model it as a quantum state. Almost

all the works [Wat09,BS20,ALP20,ABG+20,ACP21,BKS21,CCY21,LMS21] take this approach

of deﬁning quantum zero-knowledge. While this is the most general deﬁnition one can think of, this

deﬁnition does not accommodate the subtleties on the computational power of the quantum veriﬁer

that is highlighted by the example below.

Deﬁnitional Issues. Let us consider the following language based on integer factorization:

ℒ𝖥𝖠𝖢𝖳𝖮𝖱𝖨𝖭𝖦 ={⟨𝑁, 𝐿, 𝑈 ⟩:∃prime 𝑝that divides 𝑁, s.t.𝐿≤𝑝≤𝑈}.

Consider the following protocol for ℒ𝖥𝖠𝖢𝖳𝖮𝖱𝖨𝖭𝖦 between a prover 𝑃and a veriﬁer 𝑉:

1. 𝑃sends a prime 𝑝that divides 𝑁and moreover, 𝐿≤𝑝≤𝑈

2. 𝑉checks if: 𝑎)𝑝is prime; 𝑏)𝑝divides 𝑁; and 𝑐)𝐿≤𝑝≤𝑈. If all the checks pass, then 𝑉

accepts. Otherwise, 𝑉rejects.

It is not hard to see that this protocol is complete and sound. Interestingly, according to the

existing deﬁnition, this protocol satisﬁes the quantum zero-knowledge property. The simulator

works as follows:

1. Using the Shor’s algorithm for integer factorization [Sho99], ﬁnd all the prime factors 𝑝1, ..., 𝑝ℓ

of 𝑁.

1See the discussion on precise zero-knowledge in Section 1.3.

2. Let 𝑖be such that 𝑝𝑖is prime, 𝑝𝑖divides 𝑁and 𝐿≤𝑝𝑖≤𝑈. Send 𝑝𝑖to the veriﬁer.

Notice that when describing the simulator, we did not take into consideration the computational

power of the veriﬁer. In particular, let us consider a malicious veriﬁer 𝑉′which is a hybrid com-

puter, consisting of a quantum device available today (such as the implementations of low-depth

Random Circuit Sampling devices [Aru19], Boson sampling [Zho21], non-universal adiabatic com-

putation [Joh11], etc.) and a classical machine. None of the currently available quantum devices

have the capability to factor large prime numbers. If 𝑉′participates in the protocol described above

then 𝑉′could be gaining knowledge, i.e., a non-trivial factor of 𝑁, that it could not have been able

to compute by itself; despite the protocol being quantum zero-knowledge!

This discrepancy appears because the deﬁnition of quantum zero-knowledge allows the simulator

to be an arbitrary quantum polynomial-time algorithm, regardless of the computational power of

the veriﬁer. For instance, even if the malicious veriﬁer is a classical polynomial-time algorithm, the

simulator is still a quantum polynomial-time algorithm.

A more realistic deﬁnition should instead consider the resources used by the veriﬁer and require

the simulator to run under (roughly) the same constraints. There are many resources we can take

into consideration when formulating this deﬁnition. In this work, we focus on the resource of

quantum memory. More speciﬁcally, we focus on the number of qubits utilized by the simulator in

relation to the number of qubits used by the veriﬁer.

Constructions of QZK: Prior Work. We ﬁrst observe that the existing works on post-quantum

zero-knowledge propose simulators whose space complexity is a large polynomial overhead in the

space complexity of the veriﬁer. One main reason behind this is the fact that all the existing black-

box simulation techniques [Wat09,Unr12,CCY21,CMSZ22,CCLY21b,LMS21] ﬁrst purify the

veriﬁer; that is, they convert the next message function of the veriﬁer into a unitary2by delaying

the measurements. The puriﬁcation process increases the space complexity, proportional to the

number of intermediate measurements.

Even if we ignore the above issue and consider veriﬁers where the next message functions are

implemented as unitaries, the existing simulators still have large polynomial overheads in the space

complexity of the veriﬁer. In [Wat09], the reason for this is the fact that the space complexity of the

simulator depends on the communication complexity of the protocol which in turn is some function

of the security parameter. In [CCY21,CCLY21b,LMS21], the simulator runs the veriﬁer coherently

multiple times and thus, the space complexity additionally depends on the number of iterations.

1.1 Our Contributions

We propose a new deﬁnition of quantum zero-knowledge, where the amount of quantum memory

used by the simulator is closely related to the quantum memory used by the veriﬁer. We also

investigate the feasibility of the new notion.

1. New Deﬁnition: Space-Bounded QZK. We formulate a new deﬁnition of post-quantum

zero-knowledge, that we call (𝑠, 𝑓)-space-bounded QZK, where 𝑠∈ℕand 𝑓(·)is some function.

Suppose the malicious quantum polynomial-time (QPT) veriﬁer is a quantum algorithm that uses

at most 𝑠qubits of quantum memory. Then, we require that the simulator runs in polynomial time

2Technically, it is converted into a unitary followed by measurement, where the measurement outcome will be the

message communicated to the prover.

and use the number of qubits is at most 𝑓(𝑠). For example, if 𝑓is deﬁned to be 𝑓(𝑥)=2𝑥then

(𝑠, 𝑓)-space bounded QZK states that the simulator should take up at most twice the number of

qubits as the veriﬁer. On the other hand, we don’t place any restriction on the classical memory of

the simulator. The amount of classical storage of the simulator could be an arbitrary polynomial in

the amount of classical storage of the veriﬁer. Indeed, in reality, classical storage is much cheaper

than quantum storage and thus, we need to be more precise about modeling the latter.

We consider three diﬀerent notions of (𝑠, 𝑓)-space-bounded QZK:

•Fully Black Box: In this notion, the simulator gets oracle access to the veriﬁer. More precisely,

each round of the veriﬁer is modeled as a sequence of channels (one per round) and the

simulator can make polynomially many queries to each of these channels. This notion of

quantum zero-knowledge is a direct analogue of classical zero-knowledge.

In terms of space complexity, the space undertaken by the simulator would also take into

account the space needed to store the private state of the veriﬁer in-between the executions

of every two consecutive rounds.

In this work, we mainly focus on understanding the feasibility of (𝑠, 𝑓 )-space bounded QZK

for diﬀerent 𝑠(·)functions.

•Black Box: In this notion, the simulator gets oracle access to the puriﬁcation of the veriﬁer

and its inverse. More precisely, suppose the veriﬁer is represented as a sequence of channels

and let 𝑈1, . . . , 𝑈𝑘be their canonical puriﬁcations3. Then, the simulator gets oracle access

to 𝑈𝑖and also oracle access to 𝑈†

𝑖, for every 𝑖∈[𝑘]. Although, in this model, the veriﬁer’s

code is modiﬁed before giving access to the simulator, we still call it black box in order to be

consistent with most of the previous works on black box quantum zero-knowledge who adopt

this model.

Note that here, we model the quantum space complexity of the simulator as a function of the

quantum space complexity of the original veriﬁer (and not the one obtained after puriﬁcation).

A (canonically) puriﬁed veriﬁer can take signiﬁcantly more space than the underlying non-

puriﬁed veriﬁer. For example, purifying an 𝑠-qubit veriﬁer with ℓmeasurements will result in a

unitary that consumes at least 𝑠+ℓqubits. Thus, (𝑠, 𝑓)space-bounded black-box QZK, for any

polynomial 𝑓(·), is impossible to achieve. On the other hand, prior works [Wat09,ACP21,

CCY21,CCLY21b,LMS21] are (𝑠, 𝑓 )-space bounded black box QZK for super-polynomial

𝑓(𝑠)=2𝜔(log(𝑠))4.

•Non Black Box: Finally, one can consider non black box quantum zero knowledge, where the

simulator is allowed to arbitrarily depend on the veriﬁer and in particular, could make use of

the code of the veriﬁer. This deﬁnition resembles the counterpart deﬁnition of (classical) non-

black box zero-knowledge. Prior works [BS20,BKS21] satisfy (𝑠, 𝑓)-space bounded non black

box QZK for super-polynomial 𝑓(𝑠) = 2𝜔(𝑙𝑜𝑔(𝑠)). We leave the investigation on the feasibility

of (𝑠, 𝑓)-space bounded non black box QZK, when 𝑓(·)is a polynomial, as an interesting open

problem.

3This means that the puriﬁcation is computed in a speciﬁc manner: that is, by delaying the measurements of the

channel.

4Notice that in these previous results, the number of qubits used by the simulator is polynomial but it might scale

with the time-complexity of the veriﬁer and that is why we can only achieve a super-polynomial upper-bound on the

number of qubits.

2. Space-Bounded QZK Against Logarithmic Space Veriﬁers. We ﬁrst focus on a re-

stricted case case when the malicious QPT veriﬁers only have access to logarithmically many qubits.

In this case, we demonstrate a feasibility result.

Suppose 𝑠=𝑂(log(𝜆)). We show that there exist, even constant-round, (𝑠, 𝑓)-space-bounded

quantum zero-knowledge protocols for NP, where 𝑓(𝑥)=2𝑥, based on the assumption of post-

quantum one-way functions. In fact, our protocol even achieves fully black-box quantum zero-

knowledge.

3. Space-Bounded QZK Against Super-Logarithmic Space Veriﬁers. We then investigate

the case when the malicious veriﬁers have access to super-logarithmically many qubits. In this case,

we present a negative result.

Suppose 𝑠=𝜔(log(𝜆)). Assuming the existence of post-quantum one-way functions, we show

that there do not exist fully black-box (𝑠, 𝑓)-space bounded quantum zero-knowledge protocols for

languages outside BQP.

Our negative result only applies to fully black-box quantum zero-knowledge and it is an inter-

esting open problem to either prove a negative result or circumvent our negative result using non

black box techniques.

1.2 Technical Overview

In Section 1.2.1 and Section 1.2.2, we present an overview of the techniques employed in both the

results.

1.2.1 Zero-Knowledge Against Logarithmic Quantum Space Veriﬁers

Rewinding has been the quintessential technique employed in proving black-box simulation security

of cryptographic protocols against probabilistic polynomial-time classical adversaries. A rewinding-

based simulator has to store copies of the intermediate states of the veriﬁer so that it can use these

copies whenever it rewinds the execution of the veriﬁer to an earlier round. However, adopting

rewinding to prove post-quantum security has not been easy; this was ﬁrst identiﬁed by [VDG97]. At

a high level, the reason for the diﬃculty arises since rewinding implicitly requires the ability to store

copies of the intermediate states, which the no-cloning theorem [Die82,WZ82]. Thus, most of the

recent works on post-quantum zero-knowledge [Wat09,Unr13,ACP21,CCY21,CMSZ22,CCLY21a,

LMS21] have proposed various rewinding techniques to perform simulation without having the need

to store intermediate copies of the veriﬁer’s state.

State Recovery. To rewind the veriﬁer to an earlier round, the most commonly adopted strategy

is to invert the operations performed by the veriﬁer in the hope that we can completely recover the

earlier states. There are two issues with it:

1. Firstly, this means that the veriﬁer has to be a unitary and thus needs to be puriﬁed; that is,

all the intermediate measurements of the veriﬁer needs to be pushed to the end of each round.

As a consequence of the puriﬁcation process, the simulator could take much larger quantum

space than the veriﬁer.

2. Secondly, each round could potentially disturb the veriﬁer’s intermediate state in an irre-

versible way. Thus, we might no longer be able to recover the earlier states.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

Post-QuantumZero-KnowledgewithSpace-BoundedSimulation*PrabhanjanAnanthUCSBAlexB.GriloSorbonneUniversité,CNRS,LIP6AbstractThetraditionaldefinitionofquantumzero-knowledgestipulatesthattheknowledgegainedbyanyquantumpolynomial-timeverifierinaninteractiveprotocolcanbesimulatedbyaquantumpolynomial-timea...

展开>> 收起<<

Post-Quantum Zero-Knowledge with Space-Bounded Simulation Prabhanjan Ananth UCSBAlex B. Grilo.pdf

共42页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Post-Quantum Zero-Knowledge with Space-Bounded Simulation Prabhanjan Ananth UCSBAlex B. Grilo

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: