Non-uniformity and Quantum Advice in the Quantum Random Oracle Model Qipeng Liu

2025-04-24 0 0 608.03KB 32 页 10玖币

侵权投诉

Non-uniformity and Quantum Advice in the Quantum

Random Oracle Model

Qipeng Liu*

Abstract

In the quantum random oracle model (QROM) introduced by Boneh et al. (Asiacrypt 2011),

a hash function is modeled as a uniformly random oracle, and a quantum algorithm can only

interact with the hash function in a black-box manner. QRO methodology captures all generic

algorithms. However, they fail to describe non-uniform quantum algorithms with preprocess-

ing power, which receives a piece of bounded classical or quantum advice.

As non-uniform algorithms are largely believed to be the right model for attackers, starting

from the work by Nayebi, Aaronson, Belovs, and Trevisan (QIC 2015), a line of works inves-

tigates non-uniform security in the random oracle model. Chung, Guo, Liu, and Qian (FOCS

2020) provide a framework and establish non-uniform security for many cryptographic appli-

cations. Although they achieve nearly optimal bounds for many applications with classical

advice, their bounds for quantum advice are far from tight.

In this work, we continue the study on quantum advice in the QROM. We provide a new

idea that generalizes the previous multi-instance framework, which we believe is more quantum-

friendly and should be the quantum analog of multi-instance games. To this end, we match the

bounds with quantum advice to those with classical advice by Chung et al., showing quantum ad-

vice is almost as good/bad as classical advice for many natural security games in the QROM.

More formally,

•OWFs: Even with 𝑆-qubits of quantum advice, a 𝑇-query quantum algorithm has advan-

tage 𝑂((𝑆𝑇 +𝑇2)/𝑁 )to invert a random function with domain and range size 𝑁. As

shown by Corrigan-Gibbs and Kogan (TCC 2019), any further improvement will lead to

new classical circuit lower bounds.

•PRGs: An 𝑆-qubit, 𝑇-query quantum algorithm can distinguish between a random im-

age and a random element in the range, with an winning probability at most 1/2 +

𝑂(𝑇2/𝑁 )1/2+𝑂(𝑆𝑇/𝑁)1/3, in contrast to 1/2 + 𝑂((𝑆5𝑇+𝑆4𝑇2)/𝑁)1/19 by Chung et

al.

•Salting: A commonly used mechanism in cryptography called salting defeats preprocess-

ing, even with quantum advice, improved the bounds by Chung et al.

Finally, we show that for some contrived games in the QROM, quantum advice can be ex-

ponentially better than classical advice for some parameter regimes. To our best knowledge,

it provides the ﬁrst evidence of a general separation between quantum and classical advice

relative to an unstructured oracle.

*Simons Institute for the Theory of Computing. Email: qipengliu0@gmail.com

arXiv:2210.06693v1 [quant-ph] 13 Oct 2022

1 Introduction

Many practical cryptographic constructions are analyzed in idealized models, for example, the

random oracle model which treats an underlying hash function as a uniformly random oracle

(ROM) [BR93]. On a high level, the random oracle model captures all algorithms that use the

underlying hash function in a generic (black-box) way; often, the best attacks are generic. Whereas

the random oracle methodology guides the actual security of practical constructions, it fails to

describe non-uniform security: that is, an algorithm consists of two parts, the ofﬂine and the

online part; the ofﬂine part can take forever, and at the end of the day, it produces a piece of

bounded advice for its online part; the online part given the advice, tries to attack cryptographic

constructions efﬁciently.

Non-uniform algorithms are largely believed to be the right model for attackers and usually

show advantages over uniform algorithms [Unr07,CDGS18,CDG18]. The famous non-uniform

example is Hellman’s algorithm [Hel80] for inverting permutations or functions. When a per-

mutation of range and domain size 𝑁is given, Hellman’s algorithm can invert any image (with

certainty) with roughly advice size √𝑁and running time √𝑁. In contrast, uniform algorithms

require running time 𝑁to achieve constant success probability. Another more straightforward

example is collision resistance. When non-uniform algorithms are presented, no single ﬁxed hash

function is collision-resistant as an algorithm can hardcode a pair of collisions in its advice.

Non-uniform security in idealized models has been studied extensively in the literature. Let

us take the two most simple yet fundamental security games as examples: one search game and

one decision game. The ﬁrst one is one-way function inversion (or OWFs) as mentioned above.

The goal is to invert a random image of the random oracle. The study was initialized by Yao

[Yao90] and later improved by a line of works [DTT10,Unr07,DGK17,CDGS18]. They show that

any 𝑇-query algorithm with arbitrary 𝑆-bit advice, can win this game with probability at most

𝑂(𝑆𝑇/𝑁), assuming the random oracle has equal domain and range size. The other example is

pseudorandom generators (or PRG). The task is to distinguish between a random image 𝐻(𝑥)(𝑥

is uniformly at random and 𝐻is the hash function) or a random element 𝑦in its range. Since it is

a decision game, some techniques for OWFs may not apply to PRGs, which we will see later. Its

non-uniform security is 𝑂(1/2 + 𝑇/𝑁 +𝑆𝑇/𝑁 )by Coretti et al. [CDGS18], and later improved

by Garvin et al. [GGKL21].

The quantum setting is very similar to the classical one, except an algorithm can query the

random oracle in superposition. Boneh et al. [BDF+11] justify the ability to make superposition

queries since a quantum computer can always learn the description of a hash function and com-

pute it coherently. Besides, advice can be either a sequence of bits or qubits. We should carefully

distinguish between the two different models. Indeed, we believe non-uniform quantum algo-

rithms with quantum advice are important to understand and should be considered the “right”

attacker model when full-scale quantum computers are widely viable and quantum memory is

affordable.

Nayebi, Aaronson, Belovs, and Trevisan [NABT14] initiated the study of quantum non-uniform

security with classical advice of OWFs and PRGs. Hhan, Xagawa and Yamakawa [HXY19], Chung,

Liao and Qian [CLQ19] extended the study to quantum advice. Most recently, Chung, Guo, Liu

and Qian [CGLQ20] improved the bounds for both examples. For OWFs, their bounds are almost

optimal in terms of query complexity for both classical and quantum advice. They show that to

invert a random image with at least constant probability, advice size 𝑆and the number of queries

𝑇should satisfy 𝑆𝑇 +𝑇2≥̃

Ω(𝑁). However, a gap between classical and quantum advice appears

when we choose security parameters for practical hash functions against non-uniform attacks. In

practice, we ensure that an adversary with bounded resources (for example, 𝑆=𝑇= 2128) only

has probability smaller than 2−128. The bounds in [CGLQ20] suggest that for OWF, the security

parameter needs to be 𝑛= 384 (and 𝑁= 2384) for classical advice and 𝑛= 640 for quantum

advice, leaving a big gap between two types of advice. Even worse, when it comes to PRGs, the

security parameters are 𝑛= 640 for classical advice v.s. 𝑛= 3200 for quantum advice; not to

mention a large gap between their query complexity, unlike OWFs.

As understanding quantum advice is beneﬁcial to both practical cryptography efﬁciency and

may inspire general computation theory (such as, 𝖰𝖬𝖠 v.s. 𝖰𝖢𝖬𝖠 [AK07,Aar21] and 𝖡𝖰𝖯/𝗉𝗈𝗅𝗒

v.s. 𝖡𝖰𝖯/𝗊𝗉𝗈𝗅𝗒 [Aar05]), we raise the following natural question:

Can quantum advice outperform classical advice in the QROM?

In this work, we provide a new technique for analyzing quantum advice in the QROM and

show that for many games, the non-uniform security with quantum advice matches the best-

known security with classical advice, including OWFs and PRGs. It gives strong evidence that for

many cryptographic games in the QROM, quantum advice provides no or little advantage over

classical one.

So far, we have seen no advantage of quantum advice in the QROM for common cryptographic

games. We then ask the second question:

Is there any (contrived) game in the QROM, in which quantum advice is “exponentially better”

than classical advice?

We give an afﬁrmative answer to this question, for some parameters of 𝑆, 𝑇 . We show that when

algorithms can not make online queries (i.e., 𝑇= 0), there is an exponential separation between

quantum and classical advice for certain games. This result is inspired by the recent work by

Yamakawa and Zhandry [YZ22] on veriﬁable quantum advantages in the QROM. We elaborate

on both results now.

1.1 Our Results

Our ﬁrst result is to give a quantum analog of “multi-instance games” via “alternating measure-

ment games” (introduced in Section 6) and develop a new technique for analyzing non-uniform

bounds with quantum advice. Our techniques do not need to rewind a non-uniform quantum al-

gorithm and completely avoid the rewinding issues/difﬁculties in the prior work [CGLQ20]. We

delay the technical details in Section 2 and give other results below.

To show the power of our technique, we incorporate it into three important applications:

OWFs, PRGs, and salted cryptography. Note that our result below is a non-exhaustive list of ap-

plications. With little effort, we can show improved non-uniform security with quantum advice

of Merkle-Damgård [GLLZ21], Yao’s box [CGLQ20] and other games.

One-Way Functions. In this application, a random oracle is interpreted as a one-way function. A

(non-uniform) algorithm needs to win the OWF security game with the random oracle as a OWF.

Formally, let 𝐻: [𝑁]→[𝑀]be a random oracle.

1. A challenger samples a uniformly random input 𝑥∈[𝑁]and sends 𝑦=𝐻(𝑥)to the algo-

rithm.

2. The algorithm returns 𝑥′and it wins if and only if 𝐻(𝑥′) = 𝑦.

When both advice and queries are classical, the best lower bound is ̃

𝑂(𝑆𝑇/𝛼)by [CDGS18],

where 𝛼= min{𝑁, 𝑀}and 𝑁,𝑀are the domain and range size of the random oracle. In

other words, no algorithm with 𝑆bits of advice and 𝑇classical queries can win with prob-

ability more than ̃

𝑂(𝑆𝑇/𝛼). There is a gap between this lower bound and the upper bound

≈𝑇/𝛼+(𝑆2𝑇/𝛼2)1/3provided by Hellman’s algorithm1. Later, Corrigan-Gibbs and Kogan [CK19]

study the possible improvement on the lower bound and conclude that any improvement will lead

to improved results in circuit lower bounds. Thus, ̃

𝑂(𝑆𝑇/𝛼)is the best one can hope for in light

of the barrier.

Chung et al. [CGLQ20] show that if 𝑆bits of classical advice and 𝑇quantum queries are given,

the maximum winning probability is bounded by ̃

𝑂𝑆𝑇 +𝑇2

𝛼. They further argue that this bound

is almost optimal. Intuitively, one can think of this as 𝑇2/𝛼 comes from a brute-force Grover’s

algorithm [Gro96], without using any advice, and 𝑆𝑇/𝛼 comes from classical advice and hits the

classical barrier by [CK19].

For quantum advice and quantum queries, they show the maximum success probability is

𝑂𝑆𝑇 +𝑇2

𝛼1/3. As mentioned early, although the bound is optimal regarding query complexity,

the exponent seems non-tight. Thus, they ask the following question:

... Can this loss (of the exponent) be avoided, or is there any speed up in terms of 𝑆and 𝑇for

sub-constant success probability?.

Our ﬁrst result gives a positive answer to the above question and proves that the loss on expo-

nent can be avoided.

Theorem 1.1. Let 𝐻be a random oracle [𝑁]→[𝑀]and 𝛼= min{𝑁, 𝑀}. One-way function games in

the QROM have security 𝑂𝑆𝑇 +𝑇2

𝛼against non-uniform quantum algorithms with 𝑆-qubits of advice

and 𝑇quantum queries.

The theorem guides security parameter choices of hash functions to be secure against non-

uniform attacks. The security parameter 𝑛should be 384 to have security 2−128 against non-

uniform quantum attacks with 𝑆=𝑇= 2128. Another direct implication of our theorem is that,

when quantum advice 𝑆=𝑂(√𝛼), quantum advice is useless for speeding up function inver-

sion. To put it in another way, Grover’s algorithm can not be sped up and only has probability

𝑇2/𝛼 to succeed even with quantum advice of size 𝑂(√𝛼), relative to a random oracle. We list a

comparison of best-known bounds and our result below.

Pseudorandom Generators. Another important application we will focus on is pseudorandom

generators. One fundamental difference from one-way functions is its being a decision game. We

will later see that publicly veriﬁable games such as one-way functions are easy to deal with in the

previous work [CGLQ20]. For games that can not be publicly veriﬁed, such as decision games,

[CGLQ20] often gives worse bounds.

1Hellman’s algorithm on functions does not behave as well as on permutations. Upper and lower bounds meet at

𝑆𝑇 /𝛼 only when we consider permutations.

Classical Advice in [CGLQ20] Quantum Advice in [CGLQ20] Quantum Advice in This Work

𝑂𝑆𝑇 +𝑇2

𝛼̃

𝑂𝑆𝑇 +𝑇2

𝛼1/3𝑂𝑆𝑇 +𝑇2

𝛼

Table 1: Non-uniform security for OWFs with 𝑇queries and 𝑆bits (qubits) of advice, where 𝛼=

min{𝑁, 𝑀 }and 𝑁,𝑀are the domain and range size of the random oracle. Our bound is a “big-𝑂” in-

stead of “big- ̃

𝑂” as we also remove the dependence on log 𝑁and log 𝑀.

In this game, an algorithm tries to distinguish between an image of a random input, and a

uniformly random element in the range. Let 𝐻: [𝑁]→[𝑀]be a random oracle.

• A challenger samples a uniformly random bit 𝑏. If 𝑏= 0, it samples a uniformly random

𝑥∈[𝑁]and outputs 𝑦=𝐻(𝑥); otherwise, it samples a uniform 𝑦∈[𝑀]and outputs 𝑦.

• The algorithm is given 𝑦and returns 𝑏′. It wins if and only if 𝑏′=𝑏.

Our new technique demonstrates the following theorem about PRGs.

Theorem 1.2. Let 𝐻be a random oracle [𝑁]→[𝑀]. PRG games in the QROM have security 1/2 +

𝑂𝑇2

𝑁1/2+𝑂𝑆𝑇

𝑁1/3against non-uniform quantum algorithms with 𝑆-qubits of advice and 𝑇quantum

queries.

Classical Advice in [CGLQ20] Quantum Advice in [CGLQ20] Quantum Advice in This Work

2+̃

𝑂𝑆𝑇 +𝑇2

𝑁1/31

2+̃

𝑂𝑆5𝑇+𝑆4𝑇2

𝑁1/19 1

2+𝑂𝑇2

𝑁1/2+𝑂𝑆𝑇

𝑁1/3

Table 2: Non-uniform security of PRGs with 𝑇queries and 𝑆bits (qubits) of advice. Our bound also

improves the previous result on classical advice by reducing the exponent on 𝑇2/𝑁 from 1/3to 1/2; we

note that the improvement on the exponent only follows from a simple observation and can also be applied

to the previous work as well.

“Salting Defeats Preprocessing”. Finally, instead of proving more concrete non-uniform bounds

like Merkle-Damgård [GLLZ21], we demonstrate that the generic mechanism “salting” helps pre-

vent quantum preprocessing attacks even with quantum advice. Maybe the most illustrating ex-

ample is collision-resistant hash functions. As mentioned before, no single ﬁxed hash function

can be collision resistant against non-uniform attacks. A typical solution is to add “salt” to the

hash function. A salt is a piece of random data that will be fed into a hash function as an addi-

tional input. To attack a salted collision resistant hash function, an adversary gets a salt 𝑠and is

required to come out with two input 𝑚̸=𝑚′such that the hash evaluation on (𝑠, 𝑚)equals that of

(𝑠, 𝑚′). Intuitively, since salt 𝑠is chosen uniformly at random from a large space, advice is not long

enough to include collisions for every possible salt. Thus, salting is a mechanism that compiles

a game into another game, by adding a random extra input 𝑠and restricting the execution of the

game always under oracle access to 𝐻(𝑠, ·).

Chung et al. [CLMP13], and Coretti et al. [CDGS18] formally proved the non-uniform security

of salted collision-resistant hash in the classical ROM. Chung et al. [CGLQ20] extended the state-

ment in the quantum setting. For quantum advice, their result roughly says that if an underlying

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

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

10 玖币 0人已下载

立即下载

摘要：

Non-uniformityandQuantumAdviceintheQuantumRandomOracleModelQipengLiu*AbstractInthequantumrandomoraclemodel(QROM)introducedbyBonehetal.(Asiacrypt2011),ahashfunctionismodeledasauniformlyrandomoracle,andaquantumalgorithmcanonlyinteractwiththehashfunctioninablack-boxmanner.QROmethodologycapturesallgener...

展开>> 收起<<

Non-uniformity and Quantum Advice in the Quantum Random Oracle Model Qipeng Liu.pdf

共32页,预览5页

还剩页未读，继续阅读

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

Non-uniformity and Quantum Advice in the Quantum Random Oracle Model Qipeng Liu

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: