Guessing probability under unlimited known-plaintext attack on secret keys for Y00 quantum stream cipher by quantum multiple hypotheses testing

Takehisa Iwakoshi

doi:10.1117/1.OE.57.12.126103

10 December 2018 Guessing probability under unlimited known-plaintext attack on secret keys for Y00 quantum stream cipher by quantum multiple hypotheses testing

Takehisa Iwakoshi

Author Affiliations +

Optical Engineering, Vol. 57, Issue 12, 126103 (December 2018). https://doi.org/10.1117/1.OE.57.12.126103

Abstract

Although quantum key distribution is regarded as promising secure communication, security of Y00 protocol proposed by Yuen in 2000 for the affinity to conventional optical communication is not well-understood yet; its security has been evaluated only by the eavesdropper’s error probabilities of detecting individual signals or masking size, the number of hidden signal levels under quantum and classical noise. Our study is the first challenge of evaluating the guessing probabilities on shared secret keys for pseudorandom number generators in a simplified Y00 communication system based on quantum multiple hypotheses testing theory. The result is that even unlimitedly long known-plaintext attack only lets the eavesdropper guess the shared secret keys of limited lengths with a probability strictly <1. This study will give some insights for detailed future works on this quantum communication protocol.

1. Introduction

Recent heating-up in the development race of quantum computers brings attention to secure communications that are resistant to quantum computers. Quantum key distribution (QKD) has been said to be the most promising technology to protect communications from cryptanalysis even with quantum computers.

On the other hand, Y00 protocol proposed by Yuen (its original name is $α η$ ) in 2000¹^–³ is compatible to conventional high-speed and long-distance optical communication technologies while it sends messages directly and hides them under quantum noise, enhancing the security of conventional cryptographies.⁴^–¹⁴ However, its security has not been well-understood except some evaluations by unicity distance,¹⁵^,¹⁶ numerical analyses by masking sizes that are the numbers of signal levels hidden under quantum noise,¹⁷^,¹⁸ or error probability in eavesdropping on individual signals.¹⁹ Therefore, since fast correlation attack on Y00 protocol was found,²⁰^,²¹ Y00 protocol has been believed to be computationally secure while QKDs are information-theoretically secure, although “irregular mapping” was equipped on Y00 systems as a countermeasure to fast correlation attack.²²

This study gives the first example of security analysis on Y00 protocol with an unlimitedly long known-plaintext attack (KPA) by quantum multiple hypotheses testing theory. It shows that Y00 protocol is secure with guessing probabilities on the two shared secret keys of 128 bits strictly $< 1$ even under unlimitedly long KPA. However, as time passes the attack increases the guessing probability, hence fresh keys have to be sent instead of messages before Y00 communication systems are breached. In this case, if the probability distribution of the provided fresh key is uniform, the guessing probability on the key has to be evaluated by ciphertext-only attack (COA). There are still some assumptions in this study, therefore, this study is not rigorous yet. However, it will give a better understanding of the security of Y00 protocol and some insights for detailed future works.

One of the major methods to evaluate information-theoretic security has been calculation of the guessing probability on secret keys since Shannon²³ and in the literature following.²⁴^,²⁵ Therefore, this study follows these concepts as well to evaluate the security of Y00 protocol.

2. Known Works on Security Evaluations on Information-Theoretic Secure Cryptography

The founder of the information theory, Shannon proved that the “perfect secrecy” is satisfied only when the length of the encryption key $k$ with its probability distribution independent and identically distributed has to be longer than the plaintext $x$ , which is one-time pad.²³ Then the ciphertext string $c$ is given by the modulo-2 addition of $x$ and $k$ :

Eq. (1)

x + k = c (\mod 2) .

Therefore,

Eq. (2)

\Pr (x | c) = \Pr (x) .

Alimomeni and Safavi-Naini²⁴ proposed “guessing secrecy,” generalizing Shannon’s concept; the encryption is not perfectly secure, but the key is obtained only probabilistically by Eve’s guess as

Eq. (3)

\sum_{c \in C} \Pr (c) \max_{x \in X} \Pr (x | c) = \max_{x \in X} \Pr (x) .

Iwamoto and Shikata²⁵ proposed “worst-case guessing secrecy,” considering the worst scenario such as

Eq. (4)

\max_{(x, c) \in (X, C)} \Pr (x | c) = \max_{x \in X} \Pr (x) .

Therefore, this study follows the above concepts “guessing probability on the key” to evaluate the security of Y00 protocol.

3. Security of Conventional Stream Ciphers Under Long Known-Plaintext Attack

This section treats the security of conventional stream ciphers with KPA; those are not randomized by quantum noise to give a better understanding on the security of Y00 protocol, which is a stream cipher randomized by quantum noise. In conventional stream ciphers, a shared secret key $k$ is fed into the pseudorandom number generator (PRNG) to generate a key stream $s$ . A plaintext string $x$ from a sender, Alice, is converted into a ciphertext string $c = x + s$ mod 2. To decode $c$ , the receiver, Bob, feeds the shared $k$ into his common PRNG, then recovers $x = c + s$ mod 2. If Eve has the same PRNG and knows $x$ during a period of $s$ , she obtains $s$ completely, hence her correspondence table of $k \leftrightarrow s$ recovers the original key $k$ no matter how much computationally complex the key expansion process is. Then Eve can read all messages from the next period. In terms of conditional probability, this means

Eq. (5)

\Pr (s | c, x) = \Pr (k | c, x) = 1 .

4. Security of Y00 protocol Under KPA During Least Common Multiple of PRNGs’ Periods

This section describes the security of Y00 protocol with KPA during the least common multiple (LCM) of the two PRNGs’ periods using quantum multiple hypotheses testing theory.²⁶^,²⁷

4.1.

Principles of Binary Y00 Quantum Stream Cipher

To start Y00 protocol, the legitimate users Alice and Bob have to share a secret key $k$ . Then they expand $k$ into a key stream $s$ using a common PRNG equipped in each transmitter/receiver. Then $s$ is chopped every $\log_{2} M$ bits to form $M$ -ary string $s (t)$ of times lot $t$ while a message bit $x (t)$ is encoded into a coherent state $| α [m (t)] ⟩$ using $s (t)$ as

Eq. (6)

m (t) ≔ Map [s (t)] + M {Map [s (t)] + x (t) \mod 2} .

Map [s (t)]

is a projection from

s (t)

to

Map [s (t)] \in {0,1, 2,3, \dots, M - 1}

. Therefore, the message bit

x (t) \in {0,1}

corresponds to a set of quantum states

{| α [m (t)] ⟩, | α [m (t) + M] ⟩}

for even number

Map [s (t)]

, otherwise

{| α [m (t) + M] ⟩, | α [m (t)] ⟩}

. On the other hand, Bob’s receiver sets an optimal threshold(s) to discriminate the set of quantum states. Therefore, he decodes

x (t)

since he knows

Map [s (t)]

thanks to the common PRNG and the shared

k

. On the other hand, the eavesdropper, Eve, has to discriminate

2 M

-ary signals hidden under overlapping quantum and classical noise since she does not know whether

Map [s (t)]

is even or odd, hence

x (t)

neither.

When Eve launches KPA, a number of the hidden signal level under noise effectively halves, hence it might help Eve to guess $k$ .

To avoid the situation, overlap-selection-keying was proposed.²⁸ An additional pair of PRNGs with another shared key $Δ k$ are equipped in both a transmitter and a receiver to randomize the plaintext $x$ with pseudorandom number $Δ x$ as

Eq. (7)

m (t) ≔ Map [s (t)] + M {Map [s (t)] + x (t) + Δ x (t) \mod 2} .

Then the transmitter Alice sends a coherent state

ρ [m (t)]

with classical randomizations named DSR and DER¹⁹ although these are omitted in this study for simplicity.

Eve obtains coherent states separated from a beam-splitter $ρ^{'} [m (t)]$ and stores its time sequence in her quantum memory. Denote the quantum sequence $ρ^{'} (x, s, Δ x)$ with the splitting ratio $η$ as

Eq. (8)

ρ^{'} (x, s, Δ x) ≔ | η α (x, s, Δ x) ⟩ ⟨ η α (x, s, Δ x) | = \otimes_{t = 0}^{T - 1} | η α [m (t)] ⟩ ⟨ η α [m (t)] | .

Note that a set of (

s, Δ x

)

\in (S, Δ X)

is generated from (

k, Δ k

)

\in (K, Δ K)

. Therefore, there are only

2^{| K | + | Δ K |}

patterns of signal sequences, although the number of signal levels is

2 M

and the period of KPA is

T

. Hence, what Eve needs is not

2 M \cdot T

-ary quantum decision theory but

2^{| K | + | Δ K |}

-ary one, no matter how long the key-stream lengths of

s

and

Δ x

are. Therefore, the main problem is whether Eve can determine the correct

(s, Δ x)

in the LCM of the periods of

(s, Δ x)

denoted as

T_{LCM}

, like in case of the conventional stream cipher explained in Sec. 3 or she needs longer than

T_{LCM}

_.

4.2.

Brief Description of $M$ -ary Quantum Detection Theory

Before this section starts, here are some assumptions to be satisfied.

• The projection Map[·] stays unchanged during the running of Y00 protocol.
• Map[·] is known to Eve according to the Kerckhoffs’ principle, as known as Shannon’s maxim.
• Map[·] is well-designed irregular mapping so that quantum noise covers all bits in $s (t)$ equally.

The set of Eve’s measurement operators ${E (s, Δ x | x)}$ satisfies

Eq. (9)

\sum_{(s, Δ x) \in (S, Δ X)} E (s, Δ x | x) = I .

By the Born rule, the measurement operator

E (s^{'}, Δ x^{'} | x)

gives Eve a measurement result

(s^{'}, Δ x^{'})

\in (S, Δ X)

from a quantum state

ρ^{'} (x, s, Δ x)

with a probability of

Eq. (10)

tr [E (s^{'}, Δ x^{'} | x) ρ^{'} (x, s, Δ x)] = \Pr (s^{'}, Δ x^{'} | x, s, Δ x) .

Quantum multiple hypotheses testing theory based on the Bayes criterion is applicable to decide which (

s^{'}, Δ x^{'}

) is the most possible. Let the Bayes cost in the theory be as described in

Eq. (11)

C (s, Δ x, s^{'}, Δ x^{'} | x) ≔ - δ_{s, s^{'}} δ_{Δ x, Δ x^{'}} .

When the prior probability is

\Pr (s, Δ x)

, the average Bayes cost is

Eq. (12)

Ex [C] = - \sum_{(s, Δ x), (s^{'}, Δ x^{'}) \in (S, Δ X)} \Pr (s, Δ x) δ_{s, s^{'}} δ_{Δ x, Δ x^{'}} tr [ρ^{'} (x, s, Δ x) E (s^{'}, Δ x^{'} | x)] .

The Hermitian risk operators are

Eq. (13)

W (x, s^{'}, Δ x^{'}) ≔ \sum_{(s, Δ x) \in (S, Δ X)} \Pr (s, Δ x) (- δ_{s, s^{'}} δ_{Δ x, Δ x^{'}}) ρ^{'} (x, s, Δ x) . = - \Pr (s^{'}, Δ x^{'}) ρ^{'} (x, s^{'}, Δ x^{'}) = - \Pr (s^{'}, Δ x^{'}) | η α (x, s^{'}, Δ x^{'}) ⟩ ⟨ η α (x, s^{'}, Δ x^{'}) | .

To minimize Eve’s error probability, the necessary and sufficient conditions are²⁶

Eq. (14)

[W (x, s, Δ x) - Γ] E (s, Δ x | x) = E (s, Δ x | x) [W (x, s, Δ x) - Γ] = 0,

Eq. (15)

E (s, Δ x | x) [W (x, s^{'}, Δ x^{'}) - W (x, s, Δ x)] E (s^{'}, Δ x^{'} | x) = 0,

Eq. (16)

W (x, s, Δ x) - Γ \geq 0,

Eq. (17)

Γ ≔ \sum_{(s, Δ x) \in (S, Δ X)} E (s, Δ x | x) W (x, s, Δ x) = \sum_{(s, Δ x) \in (S, Δ X)} W (x, s, Δ x) E (s, Δ x | x) .

Then Eve’s maximum success probability of obtaining the correct (

s, Δ x

) is

Eq. (18)

\Pr (s, Δ x | x, s, Δ x) = 1 - (1 + tr Γ) = - tr Γ = \sum_{(s, Δ x) \in (S, Δ X)} \Pr (s, Δ x) ⟨ η α (x, s, Δ x) | \cdot E (s, Δ x | x) | η α (x, s, Δ x) ⟩ .

Now, denote

E (s, Δ x | x)

as

Eq. (19)

E (s, Δ x | x) ≔ | (s, Δ x | x) ⟩ ⟨ (s, Δ x | x) | .

From Eq. (15),

Eq. (20)

\Pr (s, Δ x) ⟨ (s, Δ x | x) | η α (x, s^{'}, Δ x^{'}) ⟩ ⟨ η α (x, s^{'}, Δ x^{'}) | (s^{'}, Δ x^{'} | x) ⟩ = \Pr (s^{'}, Δ x^{'}) ⟨ (s, Δ x | x) | η α (x, s, Δ x) ⟩ ⟨ η α (x, s, Δ x) | (s^{'}, Δ x^{'} | x) ⟩ .

For pure states, from Eq. (8),

Eq. (21)

⟨ η α (x, s^{'}, Δ x^{'}) | η α (x, s^{'}, Δ x^{'}) ⟩ = 1 = \sum_{(s, Δ x) \in (S, Δ X)} {| ⟨ η α (x, s^{'}, Δ x^{'}) | (s, Δ x | x) ⟩ |}^{2} .

Therefore, Eq. (20) gives

2^{2 | K | + 2 | Δ K |} - 2^{| K | + | Δ K |}

equalities and Eq. (21) gives

2^{| K | + | Δ K |}

equalities. Thus there are

2^{2 | K | + 2 | Δ K |}

equations in total, and there are

2^{3 | K | + 3 | Δ K |}

variables including

{\Pr (s, Δ x)}

.

To remove remained variables ${\Pr (s, Δ x)}$ , apply Cauchy–Schwarz inequality to Eq. (18):

Eq. (22)

- tr Γ = \sum_{(s, Δ x) \in (S, Δ X)} \Pr (s, Δ x) | ⟨ η α (x, s, Δ x) {| (s, Δ x | x) ⟩ |}^{2} \leq {[\sum_{(s, Δ x) \in (S, Δ X)} \Pr {(s, Δ x)}^{2}]}^{1 / 2} {[\sum_{(s, Δ x) \in (S, Δ X)} {| ⟨ η α (x, s, Δ x) | (s, Δ x | x) ⟩ |}^{4}]}^{1 / 2} .

Let Eve know the prior probability

\Pr (s, Δ x)

under Shannon’s maxim. Then Eve can choose her

{E (s, Δ x | x)}

so that the equality of Eq. (23) is satisfied

Eq. (23)

\Pr (s, Δ x) = \frac{| ⟨ η α (x, s, Δ x) {| (s, Δ x | x) ⟩ |}^{2}}{\sum_{(s, Δ x) \in (S, Δ X)} | ⟨ η α (x, s, Δ x) {| (s, Δ x | x) ⟩ |}^{2}} .

Therefore, the prior probability distribution

{\Pr (s, Δ x)}

vanishes as follows:

Eq. (24)

\max [- tr Γ] = \frac{\sum_{(s, Δ x) \in (S, Δ X)} {| ⟨ η α (x, s, Δ x) | (s, Δ x | x) ⟩ |}^{4}}{\sum_{(s, Δ x) \in (S, Δ X)} {| ⟨ η α (x, s, Δ x) | (s, Δ x | x) ⟩ |}^{2}} .

The condition Eq. (23) satisfies Eq. (14) trivially, and Eqs. (15) and (16) are converted as follows:

Eq. (25)

| ⟨ η α (x, s^{'}, Δ x^{'}) {| (s^{'}, Δ x^{'} | x) ⟩ |}^{2} ⟨ (s, Δ x | x) | η α (x, s^{'}, Δ x^{'}) ⟩ ⟨ η α (x, s^{'}, Δ x^{'}) | (s^{'}, Δ x^{'} | x) ⟩ = | ⟨ η α (x, s, Δ x) {| (s, Δ x | x) ⟩ |}^{2} ⟨ (s, Δ x | x) | η α (x, s, Δ x) ⟩ ⟨ η α (x, s, Δ x) | (s^{'}, Δ x^{'} | x) ⟩ .

Eq. (26)

⟨ (s, Δ x | x) | [W (x, s, Δ x) - Γ] | (s, Δ x | x) ⟩ \sum_{(s, Δ x) \in (S, Δ X)} | ⟨ η α (x, s, Δ x) {| (s, Δ x | x) ⟩ |}^{2} = - | ⟨ η α (x, s, Δ x) {| (s, Δ x | x) ⟩ |}^{4} + \sum_{(s, Δ x) \in (S, Δ X)} | ⟨ η α (x, s, Δ x) {| (s, Δ x | x) ⟩ |}^{4} \geq 0 .

Therefore, Eq. (26) originated from Eq. (16) is also satisfied while a new condition is Eq. (25). The absolute value of Eq. (25) is

Eq. (27)

| ⟨ η α (x, s^{'}, Δ x^{'}) {| (s^{'}, Δ x^{'} | x) ⟩ |}^{4} | ⟨ (s, Δ x | x) {| η α (x, s^{'}, Δ x^{'}) ⟩ |}^{2} = | ⟨ η α (x, s, Δ x) {| (s, Δ x | x) ⟩ |}^{4} | ⟨ (s^{'}, Δ x^{'} | x) {| η α (x, s, Δ x) ⟩ |}^{2} .

4.3.

Security of Y00 under KPA on Secret Key: In Case of Exact Signal Detections for Eve

Although it is impossible for Eve to obtain the correct signal sequence without any errors because of quantum noise in Y00 protocol, it is worth considering an imaginary case where Eve could detect signals without any errors to compare Y00 protocol with conventional stream ciphers in Sec. 3.

The situation where Eve could detect signals without any errors is that, from the Born rule,

Eq. (28)

| ⟨ (s, Δ x | x) {| η α (x, s^{'} \neq s, Δ x^{'} \neq Δ x) ⟩ |}^{2} = 0 .

Equation (28) also implies from Eq. (21) that

Eq. (29)

⟨ η α (x, s^{'}, Δ x^{'}) | η α (x, s^{'}, Δ x^{'}) ⟩ = 1 = {| ⟨ η α (x, s, Δ x) | (s, Δ x | x) ⟩ |}^{2} .

Then from the left-hand side of Eq. (22),

Eq. (30)

- tr Γ = \sum_{(s, Δ x) \in (S, Δ X)} \Pr (s, Δ x) | ⟨ η α (x, s, Δ x) {| (s, Δ x | x) ⟩ |}^{2} = 1 .

Therefore, through one period of (

s, Δ x

), that is

T_{LCM}

, Eve would obtain the correct (

s, Δ x

) with a probability of 1. Then the situation is the same as conventional stream ciphers. Therefore, the effect of unavoidable quantum noise in Eq. (28) as a nonzero factor should play an important role in Y00 protocol.

4.4.

Security of Y00 under KPA on Secret Key: In Case of Erroneous Signal Detections for Eve

Unless Eve’s detections are error-free expressed by Eq. (28), from Eq. (21),

Eq. (31)

| ⟨ η α (x, s, Δ x) {| (s, Δ x | x) ⟩ |}^{2} < 1 .

Therefore, Eq. (24) satisfies the following inequality as well:

Eq. (32)

\max [- tr Γ] = \frac{\sum_{(s, Δ x) \in (S, Δ X)} {| ⟨ η α (x, s, Δ x) | (s, Δ x | x) ⟩ |}^{4}}{\sum_{(s, Δ x) \in (S, Δ X)} {| ⟨ η α (x, s, Δ x) | (s, Δ x | x) ⟩ |}^{2}} < 1 .

Even if

\Pr (s, Δ x)

is uniform, that is

\Pr (s, Δ x) = 2^{- | K | - | Δ K |}

, since Eve has to make the success probability in measurement larger than the failure probability,

Eq. (33)

| ⟨ η α (x, s, Δ x) {| (s, Δ x | x) ⟩ |}^{2} \geq {| ⟨ η α (x, s, Δ x) | (s^{'}, Δ x^{'} | x) ⟩ |}^{2} .

Then from Eqs. (21) and (22),

Eq. (34)

- tr Γ = \sum_{(s, Δ x) \in (S, Δ X)} \Pr (s, Δ x) {| ⟨ η α (x, s, Δ x) | (s, Δ x | x) ⟩ |}^{2} = 2^{- | K | - | Δ K |} \sum_{(s, Δ x) \in (S, Δ X)} {| ⟨ η α (x, s, Δ x) | (s, Δ x | x) ⟩ |}^{2} \geq 2^{- | K | - | Δ K |} .

Therefore, Eve has an advantage in obtaining the correct (

s, Δ x

) compared to pure-guessing. Thus even Eve launches KPA using quantum multiple hypotheses testing theory during an LCM of the periods of two PRNGs; she cannot pin down the keys deterministically, far different from conventional stream ciphers. The problem is how long Y00 protocol stays secure.

5. Security of Y00 Protocol under Unlimitedly Long KPA

This section describes the security of Y00 protocol under unlimitedly long KPA so that Eve guesses the most likely by the Bayes criterion.²⁹

5.1.

Y00 Protocol Under Unlimitedly Long KPA

Since ( $s, Δ x$ ) is pseudorandom of a period of $T_{LCM}$ while the plaintext $x$ is supposed not to repeat, Eve can statistically confirm the most likely ( $s, Δ x$ ) during $N \cdot T_{LCM}$ periods as shown in Table 1.

Table 1

A timetable of a set of variables (m, s, Δx, and x).

t	0	1	…	TLCM−1	TLCM	…	2TLCM–1	2TLCM	…	3TLCM–1	3TLCM	…
$m$	$m (0)$	$m (1)$	…	$m (T_{LCM} - 1)$	$m (T_{LCM})$	…	$m (2 T_{LCM} - 1)$	$m (2 T_{LCM})$	…	$m (3 T_{LCM} - 1)$	$m (3 T_{LCM})$	…
$s$	$s (0)$	$s (1)$	…	$s (T_{LCM} - 1)$	$s (0)$	…	$s (T_{LCM} - 1)$	$s (0)$	…	$s (T_{LCM} - 1)$	$s (0)$	…
$Δ x$	$Δ x (0)$	$Δ x (1)$	…	$Δ x (T_{LCM} - 1)$	$Δ x (0)$	…	$Δ x (T_{LCM} - 1)$	$Δ x (0)$	…	$Δ x (T_{LCM} - 1)$	$Δ x (0)$	…
$x$	$x (0)$	$x (1)$	…	$x (T_{LCM} - 1)$	$x (T_{LCM})$	…	$x (2 T_{LCM} - 1)$	$x (2 T_{LCM})$	…	$x (3 T_{LCM} - 1)$	$x (3 T_{LCM})$	…

At the $n^{'}$ th period of $n \in {1,2, 3, \dots, N}$ , Eve measures coherent states $| η α (x_{n}, s, Δ x) ⟩$ with a set of operators denoted as ${E (s, Δ x | x_{n})}$ based on known plaintext $x_{n}$ :

Eq. (35)

[W (x_{n}, s, Δ x) - Γ] E (s, Δ x | x_{n}) = E (s, Δ x | x_{n}) [W (x_{n}, s, Δ x) - Γ] = 0,

Eq. (36)

E (s, Δ x | x_{n}) [W (x_{n}, s^{'}, Δ x^{'}) - W (x_{n}, s, Δ x)] E (s^{'}, Δ x^{'} | x_{n}) = 0,

Eq. (37)

W (x_{n}, s, Δ x) - Γ_{n} \geq 0,

Eq. (38)

Γ_{n} ≔ \sum_{(s, Δ x) \in (S, Δ X)} E (s, Δ x | x_{n}) W (x_{n}, s, Δ x) = \sum_{(s, Δ x) \in (S, Δ X)} W (x_{n}, s, Δ x) E (s, Δ x | x_{n}) .

Since Eve just performs

2^{| K | + | Δ K |}

-ary quantum hypotheses testing to obtain (

s, Δ x

) based on known

x_{n}

, the results are independent of

n

. Therefore, from the Born rule, define as follows:

Eq. (39)

{| ⟨ (s, Δ x | x_{n}) | η α (x_{n}, s^{'}, Δ x^{'}) ⟩ |}^{2} ≔ \Pr (s, Δ x | x_{0}, s^{'}, Δ x^{'}),

Eq. (40)

Γ_{0} ≔ Γ_{n} .

Suppose that Eve has obtained

n (s, Δ x)

times of her measurement result

(s, Δ x)

during

N \cdot T_{LCM}

periods, then such a probability is

Eq. (41)

\Pr (n (s, Δ x) | x_{0}, s, Δ x) ≔ {}_{N}C_{n (s, Δ x)} \Pr {(s, Δ x | x_{0}, s, Δ x)}^{n (s, Δ x)} {[1 - \Pr (s, Δ x | x_{0}, s, Δ x)]}^{N - n (s, Δ x)} .

At the boundary where Eve makes a wrong decision, the Bayes criterion requests,

Eq. (42)

\Pr (s, Δ x) \Pr (n_{Th} | x_{0}, s, Δ x) = \Pr (s^{'}, Δ x^{'}) \Pr (n_{Th} | x_{0}, s^{'}, Δ x^{'}) .

Two nearest probability distributions give the following boundary conditions:

Eq. (43)

\Pr (n_{Th} | x_{0}, s, Δ x) = {}_{N}C_{n_{Th}} \Pr {(s, Δ x | x_{0}, s, Δ x)}^{n_{Th}} {[1 - \Pr (s, Δ x | x_{0}, s, Δ x)]}^{N - n_{Th}},

Eq. (44)

\Pr (n_{Th} | x_{0}, s^{'}, Δ x^{'}) = {}_{N}C_{n_{Th}} \Pr {(s, Δ x | x_{0}, s^{'}, Δ x^{'})}^{n_{Th}} {[1 - \Pr (s, Δ x | x_{0}, s^{'}, Δ x^{'})]}^{N - n_{Th}} .

Substituting Eqs. (43) and (44) into Eq. (42),

n_{Th}

is given in

Eq. (45)

\log_{2} \frac{\Pr (s, Δ x) \Pr (n_{Th} | x_{0}, s, Δ x)}{\Pr (s^{'}, Δ x^{'}) \Pr (n_{Th} | x_{0}, s^{'}, Δ x^{'})} = 0 = \log_{2} \frac{\Pr (s, Δ x)}{\Pr (s^{'}, Δ x^{'})} + n_{Th} \log_{2} \frac{\Pr (s, Δ x | x_{0}, s, Δ x)}{\Pr (s, Δ x | x_{0}, s^{'}, Δ x^{'})} + (N - n_{Th}) \log_{2} \frac{1 - \Pr (s, Δ x | x_{0}, s, Δ x)}{1 - \Pr (s, Δ x | x_{0}, s^{'}, Δ x^{'})},

Eq. (46)

n_{Th} = \frac{N \log_{2} \frac{1 - \Pr (s, Δ x | x_{0}, s^{'}, Δ x^{'})}{1 - \Pr (s, Δ x | x_{0}, s, Δ x)} + \log_{2} \frac{\Pr (s^{'}, Δ x^{'})}{\Pr (s, Δ x)}}{\log_{2} \frac{\Pr (s, Δ x | x_{0}, s, Δ x) [1 - \Pr (s, Δ x | x_{0}, s^{'}, Δ x^{'})]}{\Pr (s, Δ x | x_{0}, s^{'}, Δ x^{'}) [1 - \Pr (s, Δ x | x_{0}, s, Δ x)]}} .

This situation is depicted in Fig. 1.

Fig. 1

Schematic view of how the security of Y00 system is evaluated by Eve’s failure probability.

There are $2^{| K | + | Δ K |}$ patterns of possible probability distributions, and only one is for the correct $(s, Δ x)$ . Therefore, maximizing $n_{Th}$ by all wrong sets of $(s^{'}, Δ x^{'})$ and defining it as max $n_{Th}$ ,

Eq. (47)

\Pr (fail) = \sum_{n (s, Δ x) = 0}^{\max n_{Th}} {}_{N}C_{n (s, Δ x)} \Pr {(s, Δ x | x_{0}, s, Δ x)}^{n (s, Δ x)} {[1 - \Pr (s, Δ x | x_{0}, s, Δ x)]}^{N - n (s, Δ x)} .

Thus Eve’s success probability in obtaining the correct

(s, Δ x)

corresponding to the shared secret keys

(k, Δ k)

in the Y00 system is Pr(success) = 1–Pr(fail).

To perform numerical simulation, all conditional probabilities ${\Pr (s, Δ x | x_{0}, s^{'}, Δ x^{'})}$ defined in Eq. (39) have to be determined. However, those parameters are dependent on implementations of Y00 systems including key-expansion algorithms. Therefore, this study gives numerical examples as follows. Assume initial key lengths are $| K | = | Δ K | = 128$ bits and

Eq. (48)

\Pr (s, Δ x | x_{0}, s, Δ x) = \Pr (x^{'}, Δ x^{'} | x_{0}, x^{'}, Δ x^{'}) ≔ p,

Eq. (49)

\Pr ({}^{\forall}{s^{'}} \neq s, {}^{\forall}Δ x^{'} \neq Δ x | x_{0}, s, Δ x) = \Pr ({}^{\forall}s \neq s^{'}, {}^{\forall}Δ x \neq Δ x^{'} | x_{0}, s^{'}, Δ x^{'}) = (1 - p) / (2^{2 \times 128} - 1),

Eq. (50)

\Pr ({}^{\forall}s, {}^{\forall}Δ) = 2^{- 2 \times 128} .

The numerical simulation result with the above situation is shown in Fig. 2.

Fig. 2

Eve’s success probability in guessing the correct keys in the long run. From the top, $p = 2^{- 8}$ , $p = 2^{- 16}$ , $p = 2^{- 32}$ , and $p = 2^{- 64}$ in Eqs. (48)–(50).

As Eve’s success probability of obtaining the correct ( $s, Δ x$ ) in one $T_{LCM}$ smaller, Eve needs a larger number of $N$ , which is a repetition number of the period $T_{LCM}$ of the two PRNGs. However, note that even with $p = 2^{- 16}$ , Eve needs $N = 10^{4}$ periods to pin-down the correct ( $k, Δ k$ ) with a probability of almost 1. When $p = 2^{- 64}$ , even $N = 10^{6}$ periods are not enough for Eve, only allowing her to guess the correct ( $k, Δ k$ ) with a probability of about $10^{- 13}$ . Therefore, it was shown that Y00 protocol can go beyond the Shannon Limit of cryptography.³⁰

While Eve’s success probability is small enough, Alice has to send fresh keys to Bob to continue secure quantum communications. In this case, Eve’s probability of obtaining the fresh keys has to be evaluated by COA with probabilistically known ( $k, Δ k$ ), that is,

Eq. (51)

\Pr (k_{new}, Δ k_{new}) = \sum_{(s, Δ x) \in (S, Δ X)} \Pr (s, Δ x) \Pr (k_{new}, Δ k_{new} | s, Δ x) .

6. Results and Discussions: Assumptions Used in Security Analysis and Future Works

In this work, it was shown that even a Y00 system with a few-hundred bits of shared keys can be secure far longer than the period of its PRNGs, such as $10^{6}$ periods if its implementations are well-designed. The security analyses in this study applied the following assumptions.

1. Irregular mapping³ makes quantum noise cover all bits in the chopped key stream equally.
2. Irregular mapping is fixed and known to Eve during her eavesdropping.

Hence, there are still necessities of further studies to give mathematically more rigorous analyses when the above assumptions are not satisfied. Also, the security of fresh keys is not given in this study yet. Hence, it has to be analyzed in the next work.

7. Appendix A: Simulation Code for Fig. 2 on Mathematica 11.3

Simulation code for Fig. 2 on Mathematica 11.3

ps[p_]: = p;

pf[p_]: = (1 - ps[p])/(2^(128*2)-1);

nth[n_, p_]: = n*Log[2, (1 - pf[p])/(1 - ps[p])]/Log[2, ps[p]*(1 - pf[p]) / pf[p] / (1 - ps[p])];

prob[n_,p_]: = 1 - CDF[BinomialDistribution[n, ps[p]], Floor[nth[n, p]]];

Show [Table [LogLogPlot [prob [Floor[m], 2^(-b)], {m, 1,10^6},

PlotRange -> {{1, 10^6}, {5*10^(-21), 4}}, Frame -> True,

PlotLegends -> {Switch[b, 8, “p=2^-8”, 16, “p=2^-16”, 32, “p=2^-32”, 64, “p=2^-64”]},

PlotStyle->{Switch[b, 8, Blue, 16, Orange, 32, Green, 64, Red]}], {b, {8, 16, 32, 64}}]]

References

1.

H. P. Yuen, “KCQ: a new approach to quantum cryptography I. General principles and key generation,” (2003). Google Scholar

2.

G. A. Barbosa et al., “Secure communication using mesoscopic coherent states,” Phys. Rev. Lett., 90 (22), 227901 (2003). https://doi.org/10.1103/PhysRevLett.90.227901 PRLTAO 0031-9007 Google Scholar

3.

H. P. Yuen, “Key generation: foundations and a new quantum approach,” IEEE J. Sel. Top. Quantum Electron., 15 1630 –1645 (2009). https://doi.org/10.1109/JSTQE.2009.2025698 IJSQEN 1077-260X Google Scholar

4.

E. Corndorf et al., “Quantum-noise randomized data encryption for wavelength-division-multiplexed fiber-optic networks,” Phys. Rev. A, 71 062326 (2005). https://doi.org/10.1103/PhysRevA.71.062326 Google Scholar

5.

C. Liang et al., “Quantum noise protected data encryption in a WDM network,” IEEE Photonic Technol. Lett., 17 1573 –1575 (2005). https://doi.org/10.1109/LPT.2005.848264 Google Scholar

6.

O. Hirota et al., “Quantum stream cipher by the Yuen 2000 protocol: design and experiment by an intensity-modulation scheme,” Phys. Rev. A, 72 022335 (2005). https://doi.org/10.1103/PhysRevA.72.022335 Google Scholar

7.

Y. Doi et al., “360 km field transmission of 10 Gbit/s stream cipher by quantum noise for optical network,” in Proc. Optical Fiber Communication Conf. (OFC), OWC4 (2010). https://doi.org/10.1364/OFC.2010.OWC4 Google Scholar

8.

K. Harasawa et al., “Quantum encryption communication over a 192-km 2.5-Gbit/s line with optical transceivers employing Yuen-2000 protocol based on intensity modulation,” J. Lightwave Technol., 29 (3), 316 –323 (2011). https://doi.org/10.1109/JLT.2010.2099207 JLTEDG 0733-8724 Google Scholar

9.

F. Futami, “Experimental demonstrations of Y-00 cipher for high capacity and secure optical fiber communications,” Quantum Inf. Process., 13 2277 –2291 (2014). https://doi.org/10.1007/s11128-014-0771-5 QIPUAT 1570-0755 Google Scholar

10.

M. Nakazawa et al., “QAM quantum stream cipher using digital coherent optical transmission,” Opt. Express, 22 4098 –4107 (2014). https://doi.org/10.1364/OE.22.004098 OPEXFF 1094-4087 Google Scholar

11.

M. Yoshida et al., “Single-channel 40 Gbit/s digital coherent QAM quantum noise stream cipher transmission over 480 km,” Opt. Express, 24 652 –661 (2016). https://doi.org/10.1364/OE.24.000652 OPEXFF 1094-4087 Google Scholar

12.

F. Futami et al., “Experimental investigation of security parameters of Y-00 quantum stream cipher transceiver with randomization technique, part I,” Proc. SPIE, 10409 104090I (2017). https://doi.org/10.1117/12.2273462 PSISDG 0277-786X Google Scholar

13.

F. Futami et al., “Dynamic routing of Y00 quantum stream cipher in field-deployed dynamic optical path network,” in Optical Fiber Communication Conf., Tu2G-5 (2018). Google Scholar

14.

F. Futami et al., “Y-00 quantum stream cipher overlay in a coherent 256-Gbit/s polarization multiplexed 16-QAM WDM system,” Opt. Express, 25 (26), 33338 –33349 (2017). https://doi.org/10.1364/OE.25.033338 OPEXFF 1094-4087 Google Scholar

15.

R. Nair et al., “Quantum-noise randomized ciphers,” Phys. Rev. A, 74 052309 (2006). https://doi.org/10.1103/PhysRevA.74.052309 Google Scholar

16.

R. Nair and H. P. Yuen, “Comment on: ‘Exposed-key weakness of $α η$ ’ [Phys. Lett. A 370 (2007) 131],” Phys. Lett. A, 372 7091 –7096 (2008). https://doi.org/10.1016/j.physleta.2008.10.037 PYLAAG 0375-9601 Google Scholar

17.

O. Hirota, “Practical security analysis of a quantum stream cipher by the Yuen 2000 protocol,” Phys. Rev. A, 76 032307 (2007). https://doi.org/10.1103/PhysRevA.76.032307 Google Scholar

18.

T. Iwakoshi, F. Futami and O. Hirota, “Quantitative analysis of quantum noise masking in quantum stream cipher by intensity modulation operating at G-bit/sec data rate,” Proc. SPIE, 8189 818915 (2011). https://doi.org/10.1117/12.897783 PSISDG 0277-786X Google Scholar

19.

K. Kato, “Enhancement of quantum noise effect by classical error control codes in the intensity shift keying Y00 quantum stream cipher,” Proc. SPIE, 9225 922508 (2014). https://doi.org/10.1117/12.2060631 PSISDG 0277-786X Google Scholar

20.

S. Donnet et al., “Security of Y-00 under heterodyne measurement and fast correlation attack,” Phys. Lett. A, 356 406 –410 (2006). https://doi.org/10.1016/j.physleta.2006.04.002 PYLAAG 0375-9601 Google Scholar

21.

M. J. Mihaljevic, “Generic framework for the secure Yuen 2000 quantum-encryption protocol employing the wire-tap channel approach,” Phys. Rev. A, 75 052334 (2007). https://doi.org/10.1103/PhysRevA.75.052334 Google Scholar

22.

T. Shimizu, O. Hirota and Y. Nagasako, “Running key mapping in a quantum stream cipher by the Yuen 2000 protocol,” Phys. Rev. A, 77 034305 (2008). https://doi.org/10.1103/PhysRevA.77.034305 Google Scholar

23.

C. E. Shannon, “Communication theory of secrecy systems,” Bell Syst. Tech. J., 28 (4), 656 –715 (1949). https://doi.org/10.1002/bltj.1949.28.issue-4 BSTJAN 0005-8580 Google Scholar

24.

M. Alimomeni and R. Safavi-Naini, “Guessing secrecy,” Lect. Notes Comput. Sci., 7412 1 –13 (2012). https://doi.org/10.1007/978-3-642-32284-6 LNCSD9 0302-9743 Google Scholar

25.

M. Iwamoto and J. Shikata, “Information theoretic security for encryption based on conditional Rényi entropies,” Lect. Notes Comput. Sci., 8317 103 –121 (2013). https://doi.org/10.1007/978-3-319-04268-8_7 LNCSD9 0302-9743 Google Scholar

26.

C. W. Helstrom, “Quantum detection and estimation theory,” J. Stat. Phys., 1 (2), 231 –252 (1969). https://doi.org/10.1007/BF01007479 JSTPBS 0022-4715 Google Scholar

27.

H. P. Yuen, R. Kennedy and M. Lax, “Optimum testing of multiple hypotheses in quantum detection theory,” IEEE Trans. Inf. Theory, 21 (2), 125 –134 (1975). https://doi.org/10.1109/TIT.1975.1055351 IETTAW 0018-9448 Google Scholar

28.

O. Hirota et al., “Quantum key distribution with unconditional security for all-optical fiber network,” Proc. SPIE, 5161 320 –332 (2004). https://doi.org/10.1117/12.504978 PSISDG 0277-786X Google Scholar

29.

H. L. Van Trees, K. L. Bell and Z. Tian, Detection, Estimation, and Modulation Theory, Part I: Detection, Estimation, and Linear Modulation Theory, 2nd edn.Kindle, John Wiley & Sons, New York (2004). Google Scholar

30.

O. Hirota et al., “Getting around the Shannon limit of cryptography,” SPIE Newsroom, (2010). https://doi.org/10.1117/2.1201008.003069 Google Scholar

Biography of the author is not available.

CC BY: © The Authors. Published by SPIE under a Creative Commons Attribution 4.0 Unported License. Distribution or reproduction of this work in whole or in part requires full attribution of the original publication, including its DOI.

Citation Download Citation

Takehisa Iwakoshi "Guessing probability under unlimited known-plaintext attack on secret keys for Y00 quantum stream cipher by quantum multiple hypotheses testing," Optical Engineering 57(12), 126103 (10 December 2018). https://doi.org/10.1117/1.OE.57.12.126103

Received: 4 September 2018; Accepted: 14 November 2018; Published: 10 December 2018

Access the abstract

JOURNAL ARTICLE
7 PAGES

DOWNLOAD PAPER SAVE TO MY LIBRARY

GET CITATION

CITATIONS

Cited by 12 scholarly publications.

Explore citations on Lens.org

KEYWORDS

Signal detection

Probability theory

Quantum communications

Quantum physics

Interference (communication)

Information security

Optical communications

1.

Introduction

2.

Known Works on Security Evaluations on Information-Theoretic Secure Cryptography