An adaptive attack on Wiesner’s quantum money

(1)

An adaptive attack on Wiesner’s quantum money

Thomas Gimpel, Marius Gebhardt

Institut für Physik der Universität Augsburg

Reference: Brodutch, A.; Nagaj, D.; Sattath, O.; Unruh, D.

"An adaptive attack on Wiesner’s quantum money",

Quantum Information & Computation 16(11&12): 1048-1070 (2016)

(2)

Table of Contents

Quantum money

Elitzur-Vaidmans bomb quality tester

Bomb-testing attack on quantum money

Protective Measurement Attack

Comparison of the two attacks

(3)

Quantum money

I Goal: Create money which is impossible to forge

I Method: Use quantumsystem

I No-Cloning Theoremshould prohibit copying

S. Wiesner proposed system with single-qubit memory and single qubit measurement:

I Bank creates public serial number s with private key k^(s)∈ {0,1,+,−}ⁿ

I The Banknote then is (s,|$_si) with |$_si=|k₁^(s)i ⊗...⊗ |k_n^(s)i

(4)

Quantum money

Quantum Money: Security

I Banknote gets validated by the bank, which measures each qubit in corresponding basis and sends the banknote back after successful validation

I Measuring in the false basis would change the qubit and later Validation would fail

⇒ Use interaction free measurement

I Loophole: Bank returns correctly validated banknote

(5)

Elitzur-Vaidman bomb quality tester

I General Idea: Detect some property without disturbing it.

⇒ e.g. Detect a photon that never interacted with an object.

I Using quantum zeno effect

⇒ One can be sure about the system’s property

I Problem: There might be a light activated bomb

I Principal aim of the algorithm: Reducing the probability of the bomb to detonate but nevertheless gaining information if there is a bomb

(6)

Figure:A quality-testing procedure for bombs: run N rounds and end with a

measurement of the first register. a) A dud can’t explode, and the first register slowly rotates from|0ito|1i. b) With a live bomb, we can really trigger the bomb by flipping the second register to|1i. This does not happen often asδis small, and we are much more likely to measure|0ion the second register. The first register is then also projected back to|0i.

(7)

After first round:

I Dud: (cosδ|0i+ sinδ|1i)|0i

I Bomb: cosδ|0i |0i+ sinδ|1i |1i ⇒ probability of explosion: sin²δ

I No explosion ⇒ both registers get projected to|0i |0i Probability of no Explosion afterN steps:

(1−sin²δ)^N ≥1− π²

4N; δ= π 2N

I This behavior is called quantum Zeno effect

I AfterN steps we measure the first register: |1i ⇒ dud,

|0i ⇒bomb

(8)

Bomb-testing attack on quantum money

I Goal: Find state of i^th qubit |αi of quantummoney|$iwithout going to jail (changing it)

I Procedure is similar to Elitzur-Vaidman’s bomb tester

(9)

Figure:An adaptive attack on Wiesner’s quantum money with a strict testing procedure. We can identify whether the qubit|αiis in the state|+iwithout going to jail (being detected). If we do not identify it, we can use controlled- (−X) instead to test for|−iIf we do not detect it either, we just measure the qubit in the computational basis.

(10)

What happens to the four possible states with theX-Operation

I |0i,|1i: Flipping maps the states |0i ↔ |1i, this is the "bomb" case

⇒ Successful validation will keep first register in |0i

I |+i: Flip does nothing ("Dud" case)⇒ First register will move to|1i

I |−i: Flip gives minus sign. Initial states is|0i |−i

I First iteration:

R_δ⊗I: ((cosδ)|0i+ (sinδ)|1i)|−i

CNOT: ((cosδ)|0i −(sinδ)|1i)|−i

First register is rotated by−δcompared to|0i

I Second iteration will rotate first register back to|0i

⇒after even number of iteration fist register is|0i

⇒ We can identify if|αi is in the |+i state

(11)

I We can test for|−iusing the controlled-(−X) operation

I If we can rule out|+i and|−i we can measure in the{|0i,|1i}basis

I We can submit a banknote for validation where all qubits are slightly changed

I If we want to have a success rate of 1−f we needN = ^π_2f²ⁿ verification rounds (n: Number of qubits)

(12)

Protective Measurement Attack

I Uses weak interaction between the probe state and the money state with the unitary operatorU = e^−iδ(σ^x^⊗A)

I At each step the validation protects the money state by projecting it back to its original state with high probability

I The probe state evolves linear with the weakness parameterδ, whereas the chance of getting caught will be quadratic inδ

(13)

Process

I |0i |αi−−−−−−→≈ |0i |αi −^e^−iδ(σx^⊗A) iδ|1iA|αi

bank measures{|αihα|,11−|αihα|}

−−−−−−−−−−−−−−−−−−−−→≈e^−iδhAiσ^x |0i⊗ |αi

repeatNtimes

−−−−−−−−−→≈e^−ichAiσ^x|0i⊗ |αi with δ = c

N

I The probe system is now rotated proportional to hAi

I Then approximatehAi=hα|A|αi and thus |αi

(14)

Calculations

I WithA=P−P^⊥ ,the Taylor series of e^P andP²=P we get U = e^−iδ(σ^x^⊗A) = e^−iδ(σ^x^⊗P−σ^x^⊗P^⊥⁾= e^−iδσ^x^⊗Pe^iδσ^x^⊗P^⊥ =

= (e^−iδσ^x ⊗e^P)(e^iδσ^x ⊗e^P^⊥) =

=^he^−iδσ^x ⊗(11 + (e−1)P)^{i h}e^iδσ^x ⊗(11 + (e−1)P^⊥)ⁱ=

= e^−iδσ^x ⊗P+ e^iδσ^x ⊗P^⊥

I W|ϕ_ki= (11⊗ hα|)U|ϕ_ki |αi=√

p_k|ϕ_k+1i=

= (11⊗ hα|)(e^−iδσ^x ⊗P + e^iδσ^x ⊗P^⊥)(|ϕ_ki ⊗ |α)i=

=hα|P|αie^−iδσ^x|ϕ_ki+hα|P^⊥|αie^iδσ^x |ϕ_ki

(15)

Calculations

I W |ϕ_ki=hα|P|αie^−iδσ^x |ϕ_ki+hα|P^⊥|αie^iδσ^x|ϕ_ki ⇒ W =hα|P|αie^−iδσ^x +hα|P^⊥|αie^iδσ^x =

=hα|P|αi(cosδ11−i sinδσx) +hα|P^⊥|αi(cosδ11 + i sinδσx) =

= cosδ11hα|P +P^⊥|αi −i sinδhα|P −P^⊥|αi=

= cosδ11−i sinδhAiσx

I λ∓= cosδ∓ihAisinδ

⇒ eigenstates: |+i,|−i

(16)

Calculations

I W^N|ϕ₀i=

N−1

Y

k=0

√p_k|ϕ_Ni=√

p_pass|ϕ_Ni

I λ^N_∓= ( cosδ∓i sinδhAi

| {z }

1+ihAiδ−^δ₂²−¹₆ihAiδ³

)^N = ( e^∓iδhAi

| {z }

1+ihAiδ−^hAi²^δ²

2 −¹

6ihAiδ³

+O(δ²))^N =

=e^∓iδhAi(1 +O(δ²))^N = e^∓iNδhAi(1 +N× O(δ²)) =

= e^∓ichAi+O(N⁻¹)

(17)

Calculations

I Look at a new Matrix: cos(chAi) −i sin(chAi)

−i sin(chAi) cos(chAi)

!

⇒eigenvalues: cos(chAi)∓i sin(chAi) = e^∓ichAi

I W^N = e^−ichAiσ^x +O(1

N) (rotation with phase shift)

I √

p_pass|ϕ_Ni= e^−ichAiσ^x |ϕ₀i+O 1

N

|ϕi˜

I ⇒p_pass = 1− O

1 N

I |ϕ_Ni= e^−ichAiσ^x |ϕ₀i+O 1

N

|ϕ0i=

= cos (chAi)|0i −i sin (chAi)|1i+O 1

|ϕ0i

(18)

Approximating hAi and thus |αi

I After N validation rounds with weak coupling (c = ^π₈):

|ϕ_Ni= cos π

8hAi

|0i −i sin π

8hAi

|1i+O 1

N

|ϕi˜

I EstimatehAiby measuring the probe state in the σy basis:

¯ py+= 1

2

1−sin π

4hAi

+O 1

N

I Repeat estimationmN times to get:

hAi − 4

π arcsin1−2p_y^(m)

≤ν+O 1

N

I Overall failure probability ispfail =O ^m_N

(19)

Example: the four Wiesner money states

I Choose A=σx,c = ^π₂ and|ϕ₀i=|0i

I h0|σ_x|0i=h1|σ_x|1i= 0 andh+|σ_x|+i=− h−|σ_x|−i= 1

I Thus if|αi was initially|+i or |−i,

the final probe state will be W^N|0i=∓i|1i

I If|αi was|0i or |1i , the probe state will remain close to|0i

I By measuring the final probe state|ϕ_Ni we can identify the basis of the money state, which allows us to measure the money state |αi in that basis directly

(20)

Comparison of the two attacks

I BT-attack does not work for general unknown states or if the range of states is continuous

I PM-attack does not have this problem, but in general only estimates the money state (however modifications like in our example can be used to identify a state instead of estimating it)

I In the processes suggested by this paper the BT-attack does not have an advantage over the PM-attack in terms of resources, but neither methods are optimized (might be an advantage for the BT-attack in the future)