Device-independent uncloneable encryption Srijita Kundu Ernest Y.-Z. Tan December 31 2024

2025-04-27 0 0 728.81KB 72 页 10玖币

侵权投诉

Device-independent uncloneable encryption

Srijita Kundu *Ernest Y.-Z. Tan †

December 31, 2024

Abstract

Uncloneable encryption, ﬁrst introduced by Broadbent and Lord (TQC 2020) is a quantum

encryption scheme in which a quantum ciphertext cannot be distributed between two non-

communicating parties such that, given access to the decryption key, both parties cannot learn

the underlying plaintext. In this work, we introduce a variant of uncloneable encryption in

which several possible decryption keys can decrypt a particular encryption, and the security

requirement is that two parties who receive independently generated decryption keys cannot

both learn the underlying ciphertext. We show that this variant of uncloneable encryption

can be achieved device-independently, i.e., without trusting the quantum states and measure-

ments used in the scheme, and that this variant works just as well as the original deﬁnition in

constructing quantum money. Moreover, we show that a simple modiﬁcation of our scheme

yields a single-decryptor encryption scheme, which was a related notion introduced by Geor-

giou and Zhandry. In particular, the resulting single-decryptor encryption scheme achieves

device-independent security with respect to a standard deﬁnition of security against random

plaintexts. Finally, we derive an “extractor” result for a two-adversary scenario, which in par-

ticular yields a single-decryptor encryption scheme for single bit-messages that achieves per-

fect anti-piracy security without needing the quantum random oracle model.

1 Introduction

A fundamental difference between classical and quantum information lies in the fact that

quantum information cannot be perfectly copied. This property can be used to do cryptogra-

phy, as was noted by Wiesner [Wie83], who gave the ﬁrst scheme for quantum money which cannot

be forged. Later [Got03] considered the question of whether in the context of encryption schemes,

one could construct a form of uncloneable encryption; i.e. quantum ciphertexts that in some sense

cannot be copied. Pursuing this line of reasoning, [Got03] developed an encryption scheme in

which an adversary attempting to copy a quantum ciphertext would be caught with high proba-

bility by the intended (honest) recipient. Following up on a question posed in that work, [BL20]

*Institute for Quantum Computing and Department of Combinatorics and Optimization, University of Waterloo,

Waterloo, Ontario N2L 3G1, Canada. srijita.kundu@uwaterloo.ca

†Institute for Quantum Computing and Department of Physics and Astronomy, University of Waterloo, Waterloo,

Ontario N2L 3G1, Canada. yzetan@uwaterloo.ca

arXiv:2210.01058v5 [quant-ph] 30 Dec 2024

subsequently constructed an encryption scheme achieving a slightly different notion of unclone-

able encryption1, namely a quantum ciphertext that cannot be distributed amongst two parties

in such a way that they can both decrypt the message with high probability (after obtaining the

decryption key).

An uncloneable encryption scheme needs to satisfy a standard notion of indistinguishability

(or semantic security) that any encryption scheme needs to satisfy. Aside from this, [BL20] intro-

duced two notions of security that an uncloneable encryption scheme should satisfy: uncloneabil-

ity and uncloneable-indistinguishability. The uncloneable encryption scheme given [BL20] was a

simple construction based on Wiesner states and monogamy of entanglement games. While this

scheme achieved uncloneability in the plain model, it did not achieve uncloneable-indistinguishability,

even in the quantum random oracle model (QROM).

Following [BL20], there have been several subsequent works on uncloneable cryptography.

[MST21] showed that uncloneable-indistinguishability cannot be achieved by schemes using cer-

tain kinds of states, and other limitations of the proof techniques employed in [BL20]. [AK21]

considered public-key uncloneable encryption; [GMP23] gave a protocol for uncloneable encryp-

tion based on the post-quantum hardness of the learning with errors (LWE) problem. Recently,

[AKL+22] gave a more complicated uncloneable encryption protocol based on subset coset states

that achieves uncloneable-indistinguishability in the QROM. Moreover, [AKL+22] also gave some

impossibility results showing that certain kinds of schemes cannot achieve uncloneable-indistinguishability

in the plain model. The concept of uncloneable decryption keys, or single-decryptor encryption,

was introduced by [GZ20], which takes a reversed perspective compared to uncloneable encryp-

tion: here a quantum decryption key is made uncloneable rather than a ciphertext, with the secu-

rity requirement being only a single party should be able to use the decryption key to decrypt a

classical ciphertext. [GZ20] showed that single-decryptor encryption is equivalent to uncloneable

encryption under a certain security deﬁnition, but other deﬁnitions of single-decryptor encryption

have also been considered, see e.g. [CLLZ21].

As noted in [BJL+21], uncloneable encryption can be considered the second level in the hierar-

chy of uncloneable objects, since it makes information uncloneable. The ﬁrst level of the hierarchy

only lets us verify the authenticity of objects: this is where private-key quantum money lies. At the

top level of the hierarchy, functionalities are made uncloneable: this includes quantum copy pro-

tection and secure software leasing. It would be natural to ask if higher levels of the hierarchy can

be used to achieve lower levels. Indeed, [BL20] showed that uncloneable encryption can be used

to construct private-key quantum money. More surprisingly, it has been shown [CMP24,AK21]

that uncloneable encryption can be used to construct quantum copy protection of a certain class

of functions, although these constructions require either the QROM [CMP24] or additional com-

putational assumptions [AK21].

Device-independence. The results in [Got03,BL20] were derived in a device-dependent setting, in

which it is assumed that any honest parties can generate trusted states and/or perform trusted

measurements. However, it was observed in e.g. [BHK05,AGM06,PAB+09] that in some situa-

tions, one can construct protocols that are secure under much weaker assumptions: no assump-

tions on the states and measurements are made except that the measurements of spatially sepa-

rated parties are in tensor product (or commute). This strong form of security is referred to as the

device-independent (DI) paradigm, in that security can be achieved (almost) independently of the

1[BL20] refer to the scheme in [Got03] as one that achieves tamper-detection rather than uncloneability; in this work

we follow their terminology rather than the original terminology in [Got03].

underlying operations being performed by the devices used in the protocol. Device-independent

protocols that have information theoretic security are often based on the property of self-testing

or rigidity displayed by some non-local games. Suppose a non-local game is played with some

unknown state and measurements. If these measurements and state achieve a winning probabil-

ity close to the optimal winning probability of the game, then self-testing tells us the state and

measurements are close to the ideal state and measurements needed to achieve the optimal win-

ning probability for that game.2This means that we can do cryptography with this state and

measurements as though they were the ideal state and measurements.

We note that in the speciﬁc context of uncloneable encryption, the security proofs in [Got03,

BL20] do already have a form of “one-sided device-independent” property, in the sense that for the

uncloneable encryption scenario the receiver may be dishonest, and hence the security proof must

cover the possibility of the receiver not performing the intended operations. However, our goal

in this work is to extend the device-independence to cover the client’s devices as well (we brieﬂy

elaborate on how the [BL20] scheme is insecure in the fully DI setting in Section 1.1 below). This

is somewhat similar to the scenario considered by [GMP23] (for which they achieve polynomial

rather than exponential security), except that in their scenario, while the states and measurements

are indeed not trusted, it is still assumed that the devices are computationally bounded. Due to

this, the security achieved in their scenario is not information theoretic, but under the assumption

that the LWE problem cannot be solved by polynomial-time quantum computers. Hence thus far,

there has not been an uncloneable encryption scheme in the “standard” fully DI scenario, without

computational assumptions.

1.1 Our results

In this work, we develop protocols for a modiﬁed version of uncloneable encryption (of classi-

cal messages), which we term uncloneable encryption with variable keys (VKECM), as well as single-

decryptor encryption — see Remark 1below for comments regarding the security deﬁnitions used.

Our main contribution is to show that these protocols fulﬁll a standard notion of DI security,

i.e. without computational assumptions, which has not been achieved in any previous work. (As

mentioned above, [GMP23] is the only work achieving anything similar to DI security, but their re-

sult required computational assumptions; furthermore, our result is also stronger in the sense that

it achieves exponential security rather than polynomial security as in that work.) While VKECM

differs from the usual notion of uncloneable encryption, we note in particular that it is at least still

sufﬁcient to yield a quantum money scheme that is secure in the standard fully DI setting, as we

discuss later.

Remark 1. Currently, there are multiple competing security deﬁnitions in the literature for uncloneable

encryption and single-decryptor encryption. We do not aim to provide a detailed comparison of the different

deﬁnitions within the scope of this work, as they are fairly technical, though we discuss some of them brieﬂy

in Section 3when specifying the deﬁnitions we chose to use. We highlight however that for uncloneable en-

cryption, we are not studying the standard notion but are instead focusing on the modiﬁed version VKECM

described below, and hence we have to introduce appropriate new security deﬁnitions for VKECM rather

than the standard form of uncloneable encryption. Still, we note that they are similar in spirit to those used

2In this work, for simplicity of presentation we use the self-testing results described in [MYS12] which have closed-

form expressions; however, there would be no obstacles in principle if one were to instead use the more robust bounds

computed in [BNS+15] using semideﬁnite programming. The latter approach can give bounds that are quite robust to

non-maximal winning probabilities on the non-local game.

in the work [GMP23] on uncloneable encryption, and still sufﬁce to yield a DI quantum money scheme as

we discuss later. As for single-decryptor encryption, we choose to follow essentially the security deﬁnitions

used in [CLLZ21,LLQZ22].

Uncloneable encryption with variable keys. In our modiﬁed version of uncloneable encryp-

tion, the idea is that a particular ciphertext can be decrypted with several possible decryption

keys, and each adversary in a cloning attack gets an independently generated decryption key. To

further illustrate what we mean, we shall discuss this in the context of the uncloneable encryp-

tion scheme based on Wiesner states given by [BL20]. (We stress that this is merely an example

to demonstrate the key ideas, and VKECM is not restricted to such a speciﬁc implementation —

for a general formulation of VKECM, refer to Section 3.1.) For a,x∈ {0, 1}, we shall use |ax⟩to

denote the state Hx|a⟩, where His the Hadamard matrix that takes the computational basis to

the |+⟩,|−⟩ basis. For a,x∈ {0, 1}n, we shall use |ax⟩to denote Nn

i=1|(ai)xi⟩. These |ax⟩states

are called Wiesner states. The basic encryption scheme (without using the QROM) in [BL20] is as

follows: the ciphertext corresponding to a message mof nbits is (m⊕a,|ax⟩), for uniformly ran-

dom xand a, and the decryption key is x. On getting x, a single party can measure the quantum

part of the ciphertext in the bases indicated by xto recover a, and hence m. However, because

the Wiesner states satisfy a monogamy of entanglement property [TFKW13], two parties cannot

simultaneously do this.

Note that in the scheme described above, the string awhich is generated really is a “private

key”3that is required to do the encryption procedure, but which cannot be revealed to any party

if any kind of security is desired. Fortunately, after the encryption procedure is completed, adoes

not need to be stored; only the string x, which is completely independent of a, needs to be stored

and possibly released later as a decryption key.

Now consider the following modiﬁcation: we still use Wiesner states |ax⟩, but we cannot use

all the bits of aas a one-time-pad for the message — in fact we require that each party that wants

to decrypt the message has to learn a different (independently generated) subset of the bits of a

in order to do so. The reasons we need to do this are technical and have to do with the proof

style based on parallel repetition we use (we shall expand more on this in Section 1.2), but it can

be achieved by modifying the protocol in the following way. If the message length is nbits, the

Wiesner states will now be lbits, for l>n. The ciphertext will be (m⊕r,|ax⟩), where ris a

uniformly random string of nbits. (r,a,x)will all need to be stored as private key now, and there

will be a “key release" procedure that takes the private key and generates a decryption key with

a random subset Tof [l]of size n. An instance of the decryption key is (r⊕aT,T,xT), and each

time a decryption key is released from the decryption procedure, Tis generated independently.

Obviously this means there are many possible decryption keys, corresponding to different values

of T. A single decryptor given the decryption key and using |ax⟩can learn r, and thus can learn m

using the classical part of the ciphertext. This also satisﬁes the property we required, that if two

parties both want to learn the message, they have to learn independent subsets of the bits of a.

Our full DI scheme for achieving uncloneable encryption with variable keys is very similar to

the modiﬁed version of the [BL20] scheme described above, except with a “testing” step to obtain

3To avoid confusion: note that here we do not use the term “private key" in the same sense as in a public key

encryption procedure.

DI security4— basically, we play a nonlocal game on a random subset of the rounds, with the in-

formal goal of ensuring that the devices cannot both win the nonlocal game on those rounds with

high probability and still be able to usefully clone the resulting states. (Note, however, that our

results are not based on parallel self-testing theorems; rather, the only place we invoke self-testing

is to study a single protocol round, after which we separately derive a parallel-repetition theorem

to analyze the entire protocol. In particular, this means that in principle one could substitute the

self-testing argument with other methods for analyzing single protocol rounds.)

We provide a formal deﬁnition of uncloneable encryption with variable keys and its related

security criteria in Section 3.1. As indicated in the illustrative example above, the main difference

between our deﬁnition and that introduced by [BL20] is that the whole private key that was used

in the encryption needs to be stored, and there is a key release procedure that takes the private

key as input, uses additional private randomness, and outputs an independent decryption key

each time one is requested (here by independent we mean the additional private randomness is

independent for each decryption key). Additionally, since we work in the DI setting, our encryp-

tion procedure involves a small amount of interaction5to implement the “testing” step, and we

include an option to abort the procedure if this test fails. Such features are typically required in DI

cryptography protocols, which rely on rigidity properties of various interactive procedures (such

as non-local games, taking into account the need to check whether the game is won) to “test” if

the device behaviour is close to the ideal case, as mentioned above. For instance, such interaction

was also present in the [GMP23] scheme, which was DI under computational assumptions.6

Under those deﬁnitions, our main result regarding the achievability of DI uncloneable encryp-

tion with variable keys is stated in Theorem 14, and the scheme achieving this is described in

Scheme 1. Some additional notable features of our scheme are as follows:

• The uncloneable encryption scheme of [GMP23], which is device-independent with compu-

tational assumptions, allows for some noise in the devices, but their approach requires the

noise parameter to vanish in the limit of large message length n. In contrast, our protocol

tolerates a constant level of noise in the honest devices. (For the device-dependent unclone-

able encryption schemes, to our knowledge none of them have explicitly analyzed noise in

the devices, though it should be possible to modify some of the schemes to account for this.)

• Most DI cryptographic protocols that guarantee information theoretic security require that

there is no communication between the devices of different parties involved in the protocol.

Our security proof is based on the parallel repetition of a form of a non-local game; it was

4To see that the [BL20] scheme does not work if the state preparation is untrusted, observe that if the state prepared is

simply a classical record of the values (a,x)rather than the Wiesner states |ax⟩, then it is trivially insecure. If converted

to an entanglement-based protocol in which the client performs some choice of measurement xand obtains an output

a, observe that if the client’s measurements are untrusted, then the devices could just be implementing a completely

classical strategy in which for each round the output ais perfectly deterministic for each x, in which case all dishonest

parties will know the value of aonce given x. (If desired, this deterministic behaviour could be made undetectable by

any statistical checks involving only the frequency distribution of aand/or x, by instead making the value of afor each

xa function of some classical “hidden variable” Λ, a copy of which is held by all dishonest parties.)

5However, this interaction can potentially be removed if the client can impose some additional constraints on their

devices; we elaborate on this in Remark 7.

6We stress however that despite this interactive aspect, we do not assume the receiver has to be honest in our setup.

While a dishonest receiver could of course lie about the outputs of their devices, this poses no problems for a DI security

proof, because such behaviour can always be absorbed into the operations/measurements performed by the dishonest

party — this line of reasoning has been used in many previous works on cryptographic scenarios with some potentially

dishonest receiver (including uncloneable encryption) such as [FM18,GMP23,KT23]. (See also Remark 2later below.)

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

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

10 玖币 0人已下载

立即下载

摘要：

Device-independentuncloneableencryptionSrijitaKundu*ErnestY.-Z.Tan†December31,2024AbstractUncloneableencryption,firstintroducedbyBroadbentandLord(TQC2020)isaquantumencryptionschemeinwhichaquantumciphertextcannotbedistributedbetweentwonon-communicatingpartiessuchthat,givenaccesstothedecryptionkey,bot...

展开>> 收起<<

Device-independent uncloneable encryption Srijita Kundu Ernest Y.-Z. Tan December 31 2024.pdf

共72页,预览5页

还剩页未读，继续阅读

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

Device-independent uncloneable encryption Srijita Kundu Ernest Y.-Z. Tan December 31 2024

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: