Uncloneable Cryptography

2025-05-06 0 0 1.82MB 12 页 10玖币

OR SATTATH∗,Ben-Gurion University of the Negev, Israel

The no-cloning theorem asserts that, unlike classical information, quantum information cannot be copied. This seemingly undesirable

phenomenon is harnessed in quantum cryptography. Uncloneable cryptography studies settings in which the impossibility of copying

is a desired property, and achieves forms of security that are classically unattainable. The rst example discovered and analyzed was

in the context of cash. On the one hand, we want users to hold the cash; on the other hand, the cash should be hard to counterfeit.

Quantum money uses variants of the no-cloning theorem to make counterfeiting impossible.

In the past decade, this eld developed in various directions: several avors of quantum money, such as classically veriable, locally

veriable, semi-quantum, quantum coins, and quantum lightning were constructed. New uncloneable primitives were introduced,

such as uncloneable signatures, quantum copy protection for classical software, pseudorandom states, and several uncloneable forms

of encryption. This work is a gentle introduction to these topics.

CCS Concepts:

•Security and privacy →Cryptography

;

•Theory of computation →Quantum computation theory

;

•Social

and professional topics →Intellectual property.

Additional Key Words and Phrases: Quantum Cryptography, No-cloning

In memory of Stephen Wiesner, 1942—2021.

Intractable computational problems are a barrier for algorithm designers. Cryptographers are modern lemonade

makers. Their lemons are these intractable problems, which they squeeze into sweet lemonade: secure cryptographic

protocols. Why is a lemon even required? Because it lets us assume there is something an adversary cannot do. Intractable

problems can give the honest user an advantage: for example, the honest user can multiply two large primes. The

honest user knows the prime factors of the resulting number; yet, it is widely believed that a classical adversary cannot

(eciently) nd these factors.

Cryptographers have been squeezing this computational intractability lemon since the 70s. Are there any other

lemons on which cryptography could be based? Quantum mechanics has quite a few peculiarities. One notable example

is the no-cloning theorem, which states that quantum information cannot be cloned. Uncloneable cryptography—the

main focus of this review—uses the no-cloning lemon as its main ingredient. For a broader perspective, see Fig. 1.

antum states and no-cloning

Suppose you are given a sample from a probability distribution you know nothing about. Can you create another

independent sample from that distribution? Clearly, the answer is no. The no-cloning theorem states that quantum

information behaves the same way: if you are given an unknown quantum state

|𝜓⟩

, it is impossible to create two

identical copies of it. Also, the proofs of these two statements are very similar. The no-cloning result and its simple

proof use quantum jargon, which can be safely skipped for those unfamiliar.

Theorem 0.1 ([

]). The transformation

|𝜓⟩ ↦→ |𝜓⟩⊗|𝜓⟩

is non-linear, and therefore is not permissible by

quantum mechanics.

A qubit—the most basic unit of quantum information—is a linear combination of the "0" and "1" state of a single bit,

and therefore is analogous to a bit. Yet, the theorem above shows that this analogy shouldn’t be taken too literally:

Author’s address: Or Sattath, sattath@bgu.ac.il, Ben-Gurion University of the Negev, Beersheba, Israel.

arXiv:2210.14265v1 [quant-ph] 25 Oct 2022

2 Or Sattath

Fig. 1. Classical cryptography relies on the computational intractability lemon. Uncloneable cryptography combines the computational

intractability lemon, with the no-cloning lemon—see more details in the main text. For the reader’s orientation, we mention that

uncloneable cryptography is a sub-field of quantum cryptography. antum cryptography uses two other no-go phenomena as fresh

(hence, the green hue in the illustration) lemons: the act of measuring a state collapses it, and this transformation is irreversible:

there is no way to “rewind” this process and return to the pre-measured state. Additionally, non-local games have the property that

classical strategies get a “low score” compared to the optimal quantum strategies. This review focuses on uncloneable cryptography,

and therefore no rewinding and no cloning are not discussed in detail. Illustration credits: Vince Serrano.

Uncloneable Cryptography 3

unlike bits, which can be copied, there are aspects in which a qubit resembles a (classical) sample from a distribution,

since in both cases one copy is not enough to create two independent copies.

Proof. By denition,

|0⟩ ↦→ |0⟩⊗|0⟩(1)

|1⟩ ↦→ |1⟩⊗|1⟩(2)

|+⟩ ↦→ |+⟩ ⊗ |+⟩ =

2(|0⟩⊗|0⟩+|0⟩⊗|1⟩+|1⟩⊗|0⟩+|1⟩⊗|1⟩) (3)

By summing Eqs. (1) and (2), and assuming that the transformation is linear, we have

|+⟩

√2(|

⟩ + |

⟩) ↦→ 1

√2(|

⟩ ⊗

|0⟩+|1⟩⊗|1⟩), which contradicts Eq. (3). □

Note that this theorem only shows that it is impossible to create two exact clones of all states given a single copy.

There are many no-cloning variants where these restrictions are relaxed. For example, Bruß et al. [

] discuss optimal

state dependent cloners. Here, the cloner (C) receives one of two predetermined states,

|𝛼⟩,|𝛽⟩ ∈ C𝑑

; The cloner’s goal

is to have

𝐹(𝐶(|𝛼⟩),|𝛼⟩ ⊗ |𝛼⟩) ≥ 𝑥

and

𝐹(𝐶(|𝛽⟩),|𝛽⟩ ⊗ |𝛽⟩) ≥ 𝑥

for

𝑥

as large as possible, where

𝐹

is a quantity called

the delity which measures how close two given states are. Werner [

] discusses an optimal

𝑁→𝑀

cloner for any

𝑀>𝑁

: the cloner receives

𝑁

copies of a Haar random state

|𝜓⟩ ∈ C𝑑

and outputs

𝑀

registers which have the highest

possible delity with

|𝜓⟩⊗𝑀

. Among other things, Werner’s result shows that

𝑝𝑜𝑙𝑦(𝑛)

copies of a Haar random state on

𝑛qubits would yield an exponentially small delity when trying to produce (only) one additional clone.

antum money and uncloneable signatures

The rst uncloneable primitive, and arguably the rst work in quantum cryptography, was Wiesner’s private quantum

money scheme [

Wiesner’s motivation was to design “money that it is physically impossible to counterfeit”. His

construction is as follows: Upon minting, the bank creates a banknote using

𝑛

qubits, where each qubit can be in one of

the 4 states

⟩,|

⟩,|+⟩

√2(|

⟩ + |

⟩),|−⟩

√2(|

⟩ − |

⟩)

. The banknote also contains a serial number. For example,

the 9th banknote could be

⟩ ⊗ |−⟩ ⊗ |+⟩ ⊗ |−⟩ ⊗ |

⟩,

)

(here

𝑛=

5, which is too small in practice). The bank also

maintains a database, containing a classical description of the quantum state for each of the serial numbers. Money can

be veried in each of the bank branches: each bank branch needs to have a copy of the database mentioned above. To

verify the 9th banknote in the previous example, the bank would measure the rst qubit of the proclaimed state in the

0/1 basis, and reject if the outcome is not 1 (recall that the rst qubit is supposed to be

⟩

, and therefore measuring it

in the standard basis should return 1). Otherwise, it will verify the second qubit by measuring it in the +/- basis, and

rejecting if the outcome is not -. This is repeated for all the 𝑛qubits.

There are variations of this scheme that are noise-tolerant (i.e., money passes verication even if some constant

fraction of the qubits are disturbed arbitrarily). A complete analysis proving the security of Wiesner’s scheme appeared

roughly 40 years later [35,39].

Since its inception, quantum money has been improved across multiple dimensions and properties, which are

discussed in the rest of this section. Table 1contains a cell for every combination of these properties. Every such cell

contains representative constructions and the common term used for that set of properties, which might not be so

obvious: for example, a particular type of keyless quantum money is called quantum lightning. Note that in some cases,

one notion is stronger than another. For example, public quantum money, which will be discussed next, is stronger than

1The rst version of this manuscript was submitted circa 1969.

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

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

10 玖币 0人已下载

立即下载

摘要：

UncloneableCryptographyORSATTATH∗,Ben-GurionUniversityoftheNegev,IsraelTheno-cloningtheoremassertsthat,unlikeclassicalinformation,quantuminformationcannotbecopied.Thisseeminglyundesirablephenomenonisharnessedinquantumcryptography.Uncloneablecryptographystudiessettingsinwhichtheimpossibilityofcopying...

展开>> 收起<<

Uncloneable Cryptography.pdf

共12页,预览3页

还剩页未读，继续阅读

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

Uncloneable Cryptography

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: