ARTICLE POSTPRINT 1 Private Randomness Agreement and its Application in Quantum Key Distribution Networks

2025-04-24 0 0 367.86KB 6 页 10玖币

侵权投诉

ARTICLE POSTPRINT 1

Private Randomness Agreement and its Application

in Quantum Key Distribution Networks

Ren´

e Bødker Christensen and Petar Popovski

Abstract—We deﬁne a variation on the well-known problem

of private message transmission. This new problem called private

randomness agreement (PRA) gives two participants access to a

public, authenticated channel alongside the main channels, and

the ‘message’ is not ﬁxed a priori. Instead, the participants

aim to agree on a random string completely unknown to a

computationally unbounded adversary. We deﬁne privacy and

reliability, and show that PRA cannot be solved in a single round.

We then show that it can be solved in three rounds, albeit with

exponential cost, and give an efﬁcient four-round protocol based

on polynomial evaluation.

Index Terms—private message transmission, quantum key

distribution, secret sharing, privacy

I. INTRODUCTION

Exchanging key material is a fundamental problem in

cryptography. By using quantum mechanics, the so-called

BB84 protocol [1] allows two parties connected via a direct

quantum link to establish shared material for generating a

key in such a way that eavesdroppers are detected with

overwhelming probability. Over large distances, however, the

achievable key rate of direct, repeaterless quantum links drops

dramatically1[2].

When no direct quantum link exists between parties it

has been suggested – see e.g. [3, Sec. 4.2] and [4] – that

they instead route their key material through a quantum key

distribution (QKD) network, in which each connection is a

direct quantum link. Thereby, the parties can exchange keys

securely as long as each node in the QKD network is trusted. If

any node in the QKD network is malicious, the security breaks

down as this node learns any key material routed through it.

Furthermore, it could potentially alter the key, so the parties

exchanging keys end up with different keys.

Taking this problem as our point of departure, we deﬁne a

more general problem that can be seen as a variation on the

problem of private message transmission (PMT), which has

been extensively studied [5]–[11]. In PMT, two participants,

Alice and Bob, are connected via

channels, some of which

are controlled by an adversary. The exact channels under

adversarial control, referred to as the corrupted channels, are

This paper was supported in part by the Villum Investigator Grant “WATER”

from the Velux Foundations, Denmark.

R.B. Christensen is with the Department of Mathematical Sciences, Aalborg

University, and Department of Electronic Systems, Aalborg University. (e-mail:

rene@math.aau.dk)

P. Popovski is with the Department of Electronic Systems, Aalborg

University. (e-mail: petarp@es.aau.dk)

E.g. requiring almost

7·109

channel uses per secret bit if a 500km optical

link with a loss of 0.2dB/km is used.

unknown to Alice and Bob, however. The aim is to devise

some strategy on how to use these channels to allow Alice

to send a message to Bob privately and reliably – even if

the adversary alters the information sent across the corrupted

channels.

Returning to the QKD-setting, we can solve the QKD

problem using PMT. Namely, if the QKD-network contains

vertex-disjoint paths between Alice and Bob, we can consider

these as the

channels in the PMT-setting. The secret message

is then the secret key chosen by Alice. Thus, the existing

literature on PMT [5]–[11] provides a solution to the QKD-

problem as long as the power of the adversary is sufﬁciently

limited. We argue, however, that the model used in PMT is

overly restrictive for the QKD-setting. The reason for this is

twofold. First, in PMT the two parties cannot communicate

outside the

channels, whereas the goal in the QKD setting

is to exchange a key which can later be used to communicate

securely via another channel, which is public and authenticated.

Otherwise, they might as well use the QKD-network to transmit

the message itself rather than a key to encrypt the message

later. Second, in PMT Alice has a speciﬁc message that she

wants to transmit to Bob. In QKD, Alice and Bob still need

to exchange information to establish a shared key, but not one

speciﬁc key – they need only agree on some random key. As

we will show in this work, this changes the feasibility and

optimality of the problem.

The public channel introduced in this work illustrates an

interesting point in relation to QKD: the secrecy in QKD

relies on the physical properties of the quantum channel such

as non-cloneability, superpositions, and entanglement. As we

demonstrate in this work, a classical public channel can amplify

the security of the quantum channel, improving the overall

secrecy of the system.

II. PROBLEM DEFINITION

We now deﬁne the details of our model. The two participants,

Alice and Bob, are connected via

channels, which will

be indexed by

1,2, . . . , n

. We will refer to these as the

main channels. In addition, they are connected via a public,

authenticated channel which we will denote by index

. A

computationally unbounded and active adversary

controls

t<n

of the main channels. That is,

sees the information

sent across the channels under its control, and

being

active means that it can also alter this information or block

2022 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including

reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or

reuse of any copyrighted component of this work in other works. DOI: 10.1109/LCOMM.2022.3225262

arXiv:2210.05408v3 [cs.IT] 14 Feb 2023

ARTICLE POSTPRINT 2

it completely.

Furthermore, the adversary also receives the

information sent across the public channel, but cannot alter

or block this in any case.

The goal for Alice and Bob is to

transmit data via the channels in a number of rounds such that

they at the end know a shared random key, that is completely

unknown to the adversary. As is done in [11], each round

allows Alice to send information to Bob, or Bob to send

information to Alice, but not both within the same round. We

will refer to this problem as private randomness agreement

(PRA). Note that the BB84 protocol [1] also aims to provide

private randomness, but in the setting where Alice and Bob

are connected via a direct quantum link.

Regarding the number of corrupted channels, we consider

the case

t=n−1

, which is the worst case.

As we will

show, the problem does actually have a solution in this case.

This highlights a key difference between PMT and PRA, as

it is well-known that PMT cannot be solved for

2t≥n

[11,

Thm. 5.2] in the case of actively corrupted channels. Thus, the

changes introduced in PRA allows us to tolerate a much more

powerful adversary.

We now turn to deﬁning precisely what we mean by privacy

and reliability in the PRA-setting. The deﬁnitions resemble

those used in PMT [11], [12], but there is an important

difference in the case of privacy. In PMT, a protocol being

private essentially means that the adversary cannot distinguish

between protocol transcripts when sending

and when

sending

. But in that setting, the intended message

known a priori. In PRA, Alice and Bob have not decided on a

desired key beforehand. Furthermore, if the protocol fails, and

Alice and Bob output different keys, it is unclear what should

be considered the ‘intended’ key in that execution. Thus, we

will consider transcripts conditioned on the output of both Alice

and Bob. More precisely, let

be a PRA-protocol, and assume

that Alice and Bob will output keys

and

, respectively,

where

kA, kB

are both sampled from a set

of possible keys.

Let

be an adversary and assume that its input randomness

. That is, the random choices made by

is speciﬁed by

similarly to how the random tape is used to deﬁne probabilistic

Turing machines. For such an adversary and a protocol

, we

then deﬁne the random variable

AΠ(kA, kB, r)

describing the

transcript of

from the view of

conditioned on the output of

Alice being

and the output of Bob being

. The probability

distribution of this variable depends on the randomness of both

Alice and Bob.

In the following deﬁnition and throughout the work, we

assume that the key space

has the structure of an additive

group. This is not an unreasonable assumption if the key is later

to be used as a one-time pad. With this assumption, addition

of keys in Kis well-deﬁned and gives another key in K.

Otherwise,

would be passive. This has a trivial solution: Alice samples

a random key

k∈F`

, creates an additive sharing

k=Pn

i=1 ki

, and then

routes

via the

’th channel. When

is passive, Bob is guaranteed to receive

the original shares sent by Alice, meaning that he can always reconstruct

The key

remains private by the

(n−1)

-privacy of additive secret sharing.

If the adversary could tamper with the public channel, it would simply be

another channel with the same properties as the main channels. That is, the

problem reduces to standard PMT.

Clearly, the case

t=n

is impossible to solve since an adversary could

block all channels under its control.

Deﬁnition 1: A PRA-protocol

is called

-reliable if the

following holds.

•Π

is perfectly private. That is, for any

kA, k0

A, e ∈ K

the

transcripts

AΠ(kA, kA+e, r)

and

AΠ(k0

A, k0

A+e, r)

are

perfectly indistinguishable.

•

When using

, the probability that Alice and Bob output

different keys is at most δ.

In essence, the guarantee provided by Deﬁnition 1 is that the

adversary cannot learn the speciﬁc keys that Alice and Bob

output. It may learn whether the protocol has succeeded or

not as well as the difference

e=kB−kA

, but the reliability

requirement ensures that

e= 0

except with some (typically

very small) probability. Note that this is in line with the security

in PMT: we require Alice’s message to remain private, but do

not guarantee anything about the output of Bob when reliability

fails.

We note here that it is possible to deﬁne a stronger privacy

notion, namely to require

AΠ(kA, kB, r)∼ AΠ(k0

A, k0

B, r)

for

any

kA, k0

A, kB, k0

B∈ K

. This stronger privacy notion implies

that the adversary is not even allowed to learn whether the

protocol has succeeded or not – and hence it also learns nothing

about the difference

kB−kA

. This seems to be a much more

difﬁcult problem to solve, so we limit ourselves to the security

provided by Deﬁnition 1.

We note that the statement of protocol privacy is somewhat

verbose. In particular, perfect privacy implies that for any error

, the transcript of the adversary must be distributed in the

same way regardless of the output of Alice,

. Thus, we can

drop

from the notation, and simply use

AΠ(e, r)

to denote

the random transcript in an execution of Π. Translating these

observations to statements on entropy, the protocol

being

perfectly private implies

H(KA| AΠ(e, r)) = H(KA)

H(KB| AΠ(e, r)) = H(KB),(1)

where

denotes the usual binary Shannon entropy [13], and

and

denote the random variables describing the output

of Alice and Bob, respectively.

To illustrate the requirements of Deﬁnition 1, we consider

a minimal example similar to the case of a passive adversary

described above. This gives a protocol that is private against

an active adversary, but provides virtually no reliability.

Example 1: Let

n= 2

, meaning that the channels are the

public channel, one honest channel, and one corrupt channel.

Assume for clarity that the corrupt channel has index

Consider a protocol where Alice samples a key

kA∈F`

uniformly at random, and creates a sharing

k0+k1+k2=kA

of the key. She then sends

across the public channel, and

across the

’th main channel. Bob receives

k1=k1

and

where the latter may be altered by the adversary (but

Bob does not know if

is the one provided by the

adversary). Our toy-protocol speciﬁes that he should then

output kB=k0+˜

k1+˜

k2.

Note now that regardless of the outputs of Alice and Bob,

and

, the transcript

AΠ(kA, kB, r)

always comprises

only

, and

. This speciﬁes the difference

e=kB−

kA=˜

k2−k2

chosen by the adversary. Further,

acts as

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

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

10 玖币 0人已下载

立即下载

摘要：

ARTICLEPOSTPRINT1PrivateRandomnessAgreementanditsApplicationinQuantumKeyDistributionNetworksRen´eBødkerChristensenandPetarPopovskiAbstractWedeneavariationonthewell-knownproblemofprivatemessagetransmission.Thisnewproblemcalledprivaterandomnessagreement(PRA)givestwoparticipantsaccesstoapublic,authen...

展开>> 收起<<

ARTICLE POSTPRINT 1 Private Randomness Agreement and its Application in Quantum Key Distribution Networks.pdf

共6页,预览2页

还剩页未读，继续阅读

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

ARTICLE POSTPRINT 1 Private Randomness Agreement and its Application in Quantum Key Distribution Networks

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: