PaperlayerView exact revision on arXiv

Source-linked AI summary

Realization of Quantum Digital Signatures without the requirement of quantum memory

Robert J. Collins, Ross J. Donaldson, Vedran Dunjko, Petros Wallden, Patrick J. Clarke, Erika Andersson, John Jeffers, Gerald S. Buller

arXiv:1311.5760v3quant-ph

TL;DR

Earlier quantum digital signature schemes required long-term quantum memory, despite delays between distribution and messaging. This paper realizes a no-memory scheme using USE, and reports that state elimination improves signature generation rate while requiring only classical storage after distribution.

  • Problem

    Previous QDS schemes required recipients to store signature states in long-term quantum memory, although messaging may follow distribution by days or weeks and room-temperature coherence times were only tens of minutes.

    Source: pp. 1–2

  • Method

    Recipients measure signature states directly at the end of distribution using unambiguous quantum state elimination, storing only classical information.

    Source: p. 2

  • Results

    Using state elimination improves signature generation rate because events that would be non-detections with USD can contribute to detecting forgery.

    Source: p. 3

  • Takeaways & Limitations

    The experiment demonstrates a QDS realization without long-term quantum memory, using phase-encoded coherent states and recipients’ USE measurements.

    Source: pp. 2, 5

    The security analysis excludes forging attacks involving entangling operations on successive signature states, and composable security remains an issue.

    Source: p. 3

Abstract

from arXiv · show

Digital signatures are widely used to provide security for electronic communications, for example in financial transactions and electronic mail. Currently used classical digital signature schemes, however, only offer security relying on unproven computational assumptions. In contrast, quantum digital signatures (QDS) offer information-theoretic security based on laws of quantum mechanics (e.g. Gottesman and Chuang 2001). Here, security against forging relies on the impossibility of perfectly distinguishing between non-orthogonal quantum states. A serious drawback of previous QDS schemes is however that they require long-term quantum memory, making them unfeasible in practice. We present the first realisation of a scheme (Dunjko et al 2013) that does not need quantum memory, and which also uses only standard linear optical components and photodetectors. To achieve this, the recipients measure the distributed quantum signature states using a new type of quantum measurement, quantum state elimination (e.g. Barnett 2009, Bandyopadhyay et al 2013). This significantly advances QDS as a quantum technology with potential for real applications.

1. Introduction

The supplementary material details the experiment and one-bit protocol, then explains the measurements and security analysis of the coherent-state, three-party no-memory QDS protocol. It closes with performance summaries and suggested modifications.

1. Introduction

  • The supplement outlines the experimental methods and the one-bit protocol, then describes USE, multiport properties, security definitions, and analyses of repudiation, forging, and robustness.The protocol uses coherent states with four possible phases.Source: §1 · p. 5
  • For longer messages, the one-bit protocol can be iterated, with security parameters readjusted for repeated independent use.The supplementary material states that the protocol is first formally outlined for a one-bit message.Source: §1 · p. 5
  • The paper concludes with a performance summary, proposed protocol modifications, and an estimate of their effects.Source: §1 · p. 5

2. Experimental Methods

The experiment uses phase-encoded optical pulses with a delayed reference, fiber interferometers, and active alignment. Timing and phase references coordinate sender and receivers, while temporal gating filters detector events.

2. Experimental Methods

  • The setup generates 850.17 nm coherent pulses and encodes Alice’s phase with uncertainty of ±1.6 × 10^-3 radians, or ±0.2% of phase separation.The phase uncertainty is primarily attributed to amplitude fluctuation in the phase modulator’s electrical drive.Source: §2 · p. 5
  • The optical system uses a multiport, receiver beamsplitters, demodulation interferometers, and Geiger-mode silicon avalanche photodiodes.The multiport, receiver beamsplitter, and each demodulation interferometer have losses of 7.7 dB, 5.1 dB, and 9.1 dB, respectively.Source: §2 · p. 5
  • A ±1 ns time gate retains approximately 91% of raw counts while filtering spurious events; the delayed photo-count probability is 2 × 10^-6 at 10 ns.Source: §2 · p. 6
  • Polarization routing raises the time-gated detector count rate from 43% to 91% of the raw count rate compared with a 50:50 beamsplitter.Signal and reference pulses travel through the same fiber with orthogonal polarizations; the reference is delayed by 5 ns at Alice and the delay is canceled at each receiver.Source: §2 · p. 6
  • Variable-delay air-gaps and a shared tuning signal are used to maximize fringe visibility after temperature or stress changes alter interferometer path lengths.The piezoelectric actuators have approximately 15 nm steps and 1.5 µm maximum travel.Source: §2 · p. 6
  • The demonstration uses a shared 10 MHz rubidium clock, while GPS-connected separate clocks are described as a possible shared timing reference.Source: §2 · p. 6

3. Protocol outline

Alice prepares two quantum-signature sequences for each possible message and distributes one copy to each recipient. Bob and Charlie record USE outcomes, then test Alice’s declaration against stored outcomes using different thresholds for authentication and forwarding.

3. Protocol outline

  • Alice generates two copies of a length-L coherent-state sequence for each message, randomly choosing each element from phases l ∈ {1, i, −1, −i}.The sequence is the quantum signature; the corresponding sign sequence is the private key, and each ρ^k_l is a signature element state.Source: §3 · p. 6
  • Alice sends one copy of each message’s signature sequence to Bob and one to Charlie.Source: §3 · p. 6
  • Bob and Charlie pass signature elements through the multiport, apply USE, and store which detectors click, with each detector ruling out a possible phase.They also note whether photons are registered at the multiport null-port.Source: §3 · p. 6
  • Bob authenticates a declaration by counting elements whose declared phase his USE outcomes eliminated, accepting only below the authentication threshold saL.A nonzero null-port count above rL instead makes Bob abort.Source: §3 · pp. 6–7
  • To forward the message, Bob sends Charlie the message and private key; Charlie checks mismatches against the higher verification threshold svL and checks for null-port reasons to abort.The thresholds satisfy 0 ≤ sa < sv < 1.Source: §3 · p. 7

4. The USE measurement

The recipients use unambiguous quantum state elimination (USE) to rule out possible signature states rather than only trying to identify the sent state. For four coherent phases, the optical setup maps clicks to exclusions; this can yield useful outcomes even when full state discrimination would not succeed.

4. The USE measurement

  • Unlike quantum state discrimination, quantum state elimination identifies one or more states that were not sent; eliminating N − 1 of N states identifies the sent state.Barnett introduced the term for unambiguous elimination of one state among many; the approach was later termed quantum state exclusion.Source: §4 · p. 7
  • USE can have a much higher success probability than full USD when eliminating fewer than N − 1 states, especially with experimental imperfections.Even a failed USD measurement can sometimes rule out states; the authors use this available information in QDS rather than relying on USD alone.Source: §4 · pp. 7–8
  • The setup splits the received beam and interferes its parts with reference beams in states |α/√2⟩ and |iα/√2⟩; matching signal and reference arrival times enables interference [31].Source: §4 · p. 8, Figure 3 · p. 8
  • With four coherent phases, a click in each of four output modes unambiguously rules out its corresponding phase; three detector clicks identify the sent state in the ideal case.The four outputs correspond to the four elimination outcomes.Source: §4 · pp. 8–9, Figure 3 · p. 8
  • Losses reduce the probability of successful outcomes without changing their conclusive nature, whereas dark counts and other imperfections can cause errors in conclusive outcomes.Source: §4 · p. 9
  • The described USE measurement may not be optimal, but its realization requires only linear optics and commercially available photodetectors.Source: §4 · p. 9

5. The multiport

The multiport is a four-input, four-output passive linear-optical device built from four 50/50 beamsplitters, with two inputs set to vacuum. It makes Bob’s and Charlie’s reduced signal states identical and symmetric under swapping, even for entangled inputs.

5. The multiport

  • Four 50/50 beamsplitters form a passive linear-optical device with four input and four output modes; two input modes always contain vacuum.The remaining two modes are the multiport’s input modes.Source: §5 · p. 9
  • For each signature element, Bob’s and Charlie’s reduced signal states are identical, even when Alice sends general, possibly entangled states.The stated cases include entanglement between elements, between recipients, or with a state Alice retains.Source: §5 · p. 10
  • For one signature-element position, the resulting Bob–Charlie state is symmetric under swapping their subsystems, including when Alice uses entanglement.The multiport can also be generalized to many recipients.Source: §5 · p. 10

6. Definitions of security

The paper defines security through exponentially decreasing probabilities of forging and repudiation, with robustness covering honest runs. Its analysis uses Hoeffding inequalities and bounds repudiation by considering authentication and rejection probabilities.

6. Definitions of security

  • Security against forging and repudiation requires their success probabilities to decay exponentially with signature length L; robustness requires honest authentication and verification except with exponentially decreasing probability.The definitions distinguish a forged message passing verification from a message passing one recipient’s authentication but failing another’s verification.Source: §6 · p. 10
  • The analysis considers one isolated protocol run; composable security is left for future work.Security is proven for all repudiation attacks and all forging attacks except coherent forging, which remains under analysis.Source: §6 · p. 10
  • The security level is the probability of an undesirable event when thresholds sa and sv are chosen to equalize repudiation, forging, and honest-rejection probabilities.The paper notes that security-level definition is complicated because participants may differ in whether they are honest or malicious.Source: §6 · p. 10

7. Hoeffding’s inequalities

  • Hoeffding’s inequalities are introduced for independent binary variables, using their empirical mean and expected value to bound deviations.The lemma specifies L independent variables taking values 0 or 1.Source: §7 · p. 11

8. Security against repudiation – cheating Alice

  • For repudiation, the analysis bounds success using the minimum of Bob’s authentication and Charlie’s rejection probabilities, which are not independent because of multiport symmetry.The thresholds satisfy sa < sv; Alice’s attack is treated through individual strategies, with broader strategies reduced to them.Source: §8 · p. 11

a. Security against individual repudiation

The individual-attack analysis bounds repudiation through the probabilities that Bob authenticates and Charlie rejects. With suitable thresholds, these probabilities decay exponentially, and Alice’s optimal average mismatch probability lies midway between the thresholds.

a. Security against individual repudiation

  • Bob’s and Charlie’s corresponding mismatch probabilities are identical when the multiport is appropriately adjusted and calibrated, and the empirical mismatch fraction is measured over L elements.Each declaration matches an unerased element with probability p_i1 and mismatches an eliminated element with probability p_i−1.Source: a. Security against individual… · p. 11
  • Bob authenticates when the observed mismatch fraction is at most sa, and the authentication probability decays exponentially if the average mismatch probability is at least sa + ǫ′.ǫ′ is an arbitrarily small positive number.Source: a. Security against individual… · p. 12
  • Charlie rejects when the observed mismatch fraction is at least sv; Alice’s bound considers the condition that the average mismatch probability is at most sv − ǫ′.The analysis assumes Alice has full freedom to choose the mismatch probabilities for a worst-case bound, although the measurement POVMs do not have orthogonal supports.Source: a. Security against individual… · p. 12
  • With suitable thresholds, the probability of repudiation decays exponentially for all choices of Alice’s average mismatch probability, with her optimum at (sv + sa)/2.The bound is for individual attacks; Alice’s optimal choice maximizes the minimum of Bob-authentication and Charlie-rejection probabilities.Source: a. Security against individual… · p. 12
  • Alice’s best individual repudiation strategy is no more effective with different mismatch probabilities across elements than with identical states for each element.The analysis identifies an optimal average mismatch probability from Alice’s perspective.Source: a. Security against individual… · p. 12

9. Security against forging

The forging analysis distinguishes passive from active attacks and individual, collective, and coherent strategies. It examines individual and collective forging, while coherent forging remains outside the analysis; verification is easier to forge than authentication.

9. Security against forging

  • A USE measurement rules out one or more possible phases, providing a minimum advantage to someone declaring the actual phase over someone declaring another phase.The stated condition supports choosing sa, sv, and L to make the protocol secure.Source: §9 · p. 12
  • Passive forging means guessing from a copy held by an honest recipient, whereas active forging includes modifying the other recipient’s signature during distribution.Active forging can be reduced to modified passive forging by limiting multiport null-port counts.Source: §9 · p. 12
  • The analysis examines individual and collective forging attacks but leaves coherent forging strategies for future work.Collective attacks allow classical correlations across signature elements; coherent attacks allow joint measurements and entangled responses.Source: §9 · p. 12
  • It is easier to forge during verification than authentication: convincing Charlie that Bob forwards Alice’s message is easier than impersonating Alice to Bob.Successful forging is defined as Charlie verifying Bob’s fake message without an abort.Source: §9 · p. 13

a. Security against passive individual and collective forging

Passive forging is analyzed by choosing measurements that minimize the chance Charlie eliminates Bob’s declarations, subject to the protocol’s verification threshold. A gap between the forger’s minimum mismatch probability and the honest mismatch probability supports exponentially secure parameter choices.

a. Security against passive individual and collective forging

  • Bob’s optimal declaration minimizes its overall rejection cost, rather than minimizing mismatches independently for each signature element.For collective attacks without entangled measurements, independent minimum-cost measurements are optimal because phases and Charlie’s eliminations are independent across elements.Source: a. Security against passive individual… · p. 13
  • The cost matrix models Charlie’s detector-click probability for each sent state and declaration; the tested |α|² values ranged from 1 to 11, with 1 giving the best bound.The minimum advantage is the smallest diagonal-to-off-diagonal difference within a row; losses and noise make the experimental diagonal entries nonzero.Source: a. Security against passive individual… · pp. 13–14
  • If sv ≤ Cmin, the probability of forging decays exponentially with signature length L.The security gap is g = Cmin − ph, and robust, secure choices of sa and sv should lie within that gap.Source: a. Security against passive individual… · p. 14
  • For symmetric pure states, an error-type cost matrix has the square-root measurement as its minimum-cost measurement, with minimum cost proportional to pmin.An error-type matrix assigns zero cost to correct guesses and equal positive cost to every incorrect guess.Source: a. Security against passive individual… · p. 14
  • The guaranteed advantage of a correct declaration over a wrong declaration is 1.30 × 10−5, while the honest-scenario mismatch cost is 4.18 × 10−5.For α² = 1, pmin = 0.092; the lower bound on minimum cost is Cl min = 1.20 × 10−6.Source: a. Security against passive individual… · p. 15

b. Security against active individual and collective forging

Active forging is constrained by monitoring the multiport null-port, which limits tampering and reduces the analysis to modified passive forging. With a suitably chosen abort threshold, the protocol remains exponentially secure.

b. Security against active individual and collective forging

  • Choosing r so the effective verification threshold s′v remains greater than sa makes the protocol exponentially secure.The effective threshold is lowered as a function of the abort threshold r.Source: b. Security against active individual… · p. 16
  • Null-port monitoring limits how much Bob can alter Charlie’s signature state, reducing active attacks to modified passive forging attacks.The protocol aborts if null-port detections exceed rL; fidelity and trace-distance bounds are used to bound the effect of tampering.Source: b. Security against active individual… · pp. 15–16
  • For the active-attack bound, Bob is allowed a larger-amplitude coherent state, making the bounded minimum cost C′min smaller than Cmin.The bound decays exponentially when its stated threshold condition holds.Source: b. Security against active individual… · p. 16

10. Robustness

Robustness concerns successful authentication and avoiding abort when all participants are honest. Both failure probabilities decrease exponentially with signature length under the stated threshold conditions.

10. Robustness

  • The robustness analysis treats message rejection and protocol abort as separate honest-party failure events, and both decay exponentially.The section first considers rejection and then abort.Source: §10 · p. 16
  • When all parties are honest, the probability of rejecting a message decreases exponentially with L if sa ≥ ph.Here ph is the average probability that the correct state is ruled out, computed from the cost-matrix diagonal entries.Source: §10 · p. 16
  • With honest participants, the probability of abort decreases exponentially when r exceeds the average null-port dark-count rate rh by a finite amount ǫ.Abort occurs only when null-port counts exceed rL; null-port monitoring is needed to constrain active forging.Source: §10 · p. 16

11. Summary

The experiment’s measured gap implies a very long signature for the requested security level, while proposed changes are estimated to reduce that length and raise the signing rate. The protocol’s security and robustness bounds decay exponentially with signature length when the gap is positive.

11. Summary

  • For positive gap g, suitable thresholds yield exponential security against forging and repudiation, and exponentially small honest-abort probability.The decay rate depends on g; the demonstration’s gap is small.Source: §11 · p. 17
  • The evaluation uses signature length L and signing rate; a 0.01% security level requires forging, repudiation, and honest-rejection probabilities below 10−4.The required signature length increases quadratically as the transmitted signal decreases.Source: §11 · p. 17
  • At a 0.01% security level, the measured gap g = 1.20 × 10−6 requires L = 5.10 × 10^13 to sign a “half-bit”.The authors describe this length as very large for practical use.Source: §11 · p. 17
  • Extrapolation using subsequent-experiment data and known multiport losses indicates an optimal α² around 0.5, yielding gap g = 8.05 × 10−5 and length L = 1.14 × 10^10 at a 0.01% security level.Source: §11 · p. 17
  • At a 0.01% security level, the estimated gap g = 1.96 × 10−4 and length L = 1.19 × 10^9 follow from removing the multiport and other changes.The multiport is identified as a major source of losses; non-repudiation would need another guarantee.Source: §11 · p. 17
  • The proposed changes are expected to support signing 1.4 bits per second at a 0.01% security level.The estimate follows from changes to the protocol and clock rate.Source: §11 · pp. 17–18

Related papers

Loading 1311.5760v3…