PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum Digital Signatures without quantum memory

Verdan Dunjko, Petros Wallden, Erika Andersson

arXiv:1309.1375v1quant-ph

TL;DR

The paper establishes security properties for a linear-optical quantum-signature protocol without relying on stronger composable-security claims. It shows that general repudiation and collective active-forging strategies can be bounded through reductions to simpler attacks, with correctness approaching unity and repudiation and forging probabilities decreasing exponentially with signature length.

  • Problem

    The protocol's stated security definitions concern one isolated run, while stronger composable-security claims remain unaddressed.

  • Method

    Security is analyzed by reducing general repudiation and active-forging strategies to individual or IID attacks, using the multiport's Bob–Charlie symmetry.

  • Results

    For L = 10^6, P(correct) ≥ 1 − 10^-52, P(rep) ≤ 2 × 10^-6, and P(forge) ≤ 0.7 × 10^-18 under the derived bounds.

  • Takeaways & Limitations

    Correctness approaches unity while repudiation and forging probabilities tend to zero exponentially quickly as the signature length increases.

Abstract

from arXiv · show

Quantum Digital Signatures (QDS) allow for the exchange of messages from one sender to multiple recipients, with the guarantee that messages cannot be forged or tampered with. Additionally, messages cannot be repudiated -- if one recipient accepts a message, she is guaranteed that others will accept the same message as well. While messaging with these types of security guarantees are routinely performed in the modern digital world, current technologies only offer security under computational assumptions. QDS, on the other hand, offer security guaranteed by quantum mechanics. All thus far proposed variants of QDS require long-term, high quality storage of quantum information, making them unfeasible in the foreseeable future. Here, we present the first QDS scheme where no quantum memory is required, and all quantum information processing can be performed using just linear optics. This makes QDS feasible with current technology.

A. Outline and Definitions

The protocol defines distribution and messaging stages, acceptance events, abort conditions, and security criteria for correctness, repudiation, and forging. Its formal security claims bound repudiation and forging probabilities by quantities that decay exponentially with signature length L, while stronger composable security and realistic imperfections remain outside scope.

  • Protocol definition: The protocol sends L-element coherent-state signatures during distribution, then uses Alice’s classical declaration to authenticate and verify a selected message during messaging.Bob authenticates below the mismatch threshold sa, while Charlie verifies below the larger threshold sv.
  • Protocol definition: Bob and Charlie abort when their unambiguous-outcome counts leave [(pUSD −δ)L, (pUSD + δ)L] or when null-port detections exceed the allowed threshold.The tolerance δ controls acceptable variation around the expected USD count, while r controls null-port detections.
  • Security definitions: The security definitions require correctness, repudiation, and forging failure probabilities to decay exponentially with signature length L.Repudiation concerns Bob authenticating while Charlie rejects; forging concerns Bob’s undeclared message being accepted by Charlie.
  • Proof scope: The analysis uses Hoeffding inequalities to control empirical outcomes and establishes the protocol’s claims for an isolated stand-alone execution.Composable security claims are explicitly left for future work.
  • Proof scope: The supplementary analysis treats ideal apparatus behavior, while experimentally implementable losses and imperfections remain ongoing work.The protocol retains parameters intended to accommodate non-ideal implementations, but their full analysis is deferred.

B. The multiport

The multiport is a four-beamsplitter linear-optical device that processes two coherent-state inputs alongside two vacuum inputs. Its output signal ports give Bob and Charlie equal reduced states and a stronger swap symmetry, supporting later security arguments.

  • B. The multiport: The multiport has four input and four output modes, uses four 50:50 beamsplitters, and receives vacuum in two input modes.The remaining two modes carry the coherent-state inputs controlled by Alice.
  • B. The multiport: Figure 2 represents the multiport’s coherent-state input-output relations, with Bob holding the top beamsplitters and Charlie the lower ones.The two non-vacuum inputs are the modes whose transformations determine the signal and null outputs.
  • B. The multiport: The output signal-port reduced density matrices of Bob and Charlie are equal, ρ_Bs = ρ_Cs.This equality follows after tracing out the other signal, null-port, and environment systems.
  • B. The multiport: The complete output state is invariant under swapping Bob’s and Charlie’s matching signal-port elements, a stronger property than equality of their reduced states.The symmetry persists even when the input element is mixed or entangled with an environment.
  • B. The multiport: The two-recipient multiport can be generalized to protocols with more recipients.The passage states this generalization without supplying its construction details.

C. Security against repudiation

Repudiation is analyzed through the multiport’s Bob–Charlie symmetry and the gap between their authentication thresholds. The appendix extends the argument from individual attacks to separable and coherent strategies by reducing general attacks to the individual case.

  • C. Security against repudiation: Repudiation occurs when Alice’s declaration is accepted by Bob but rejected by Charlie without either party aborting.Bob uses the lower threshold sa, whereas Charlie’s verification threshold sv is higher.
  • C. Security against repudiation: The proof first analyzes individual attacks and then reduces separable and coherent repudiation attacks to individual strategies.The stated conclusion is that Alice’s best strategy is an individual attack.

1. Security against individual repudiation

Under individual attacks, the multiport makes Bob’s and Charlie’s outcome statistics symmetric, so Alice cannot reliably make one accept while the other rejects. The resulting repudiation and verification-error probabilities decrease exponentially with signature length L under suitable thresholds.

  • Symmetry and mismatch statistics: Bob and Charlie receive equal reduced states for each signature element, so their mismatch statistics are equal on average despite Alice’s choice of input states.This symmetry follows from the multiport and applies even when Alice sends different states to Bob and Charlie.
  • Verification bounds: P(BA) ≤ exp(−2(¯p−1 − s_a p_USD)^2L) when ¯p−1 ≥ s_a p_USD + ǫ′, so the authentication-bound violation decays exponentially in L.Here BA denotes Bob authenticating under the stated mismatch threshold condition.
  • Verification bounds: P(CR) ≤ exp(−2(s_v p_USD − ¯p−1)^2L), provided ¯p−1 ≤ s_v p_USD − ǫ′, so Charlie’s rejection probability also decays exponentially in L.The bound uses Charlie’s verification threshold and the same average mismatch probability.
  • Individual-attack optimization: Alice’s best individual repudiation strategy uses the same average mismatch probability for every signature element, rather than varying it across elements.The optimal average is p_USD(s_v + s_a)/2, and differing element-wise choices are no more effective under the derived bound.

2. Security against collective and coherent repudiation

The proof reduces collective and coherent repudiation attacks to individual-attack bounds by representing measurement outcomes as classical mixtures and exploiting multiport-induced Bob/Charlie symmetry. Consequently, general repudiation attacks cannot have a larger success probability and also decay exponentially with L.

  • Symmetry conditions: Element independence and equal Bob/Charlie marginal outcome distributions provide the two conditions needed to reduce the post-measurement state to a symmetric form.The first condition comes from the allowed attack structure; the second follows from multiport symmetrization.
  • Convexity argument: Because repudiation success depends only on ρ_meas and the repudiation map is linear, convexity bounds the success probability by one component of a mixture.The map outputs success or failure probabilities from the post-measurement state.
  • Reduction to individual attacks: General repudiation attacks cannot have a higher success probability than individual repudiation attacks, so their probability also decreases exponentially with signature length L.The reduction uses the previously established individual-attack bound.
  • Propagation of symmetry: The multiport’s action is independent across signature elements, preserving Bob/Charlie symmetry after each measurement and enabling iteration across all elements.The residual states remain symmetric for every measurement outcome.
  • Reduction to individual attacks: The post-measurement state therefore satisfies the required swap symmetry, establishing that the individual repudiation bound also holds for general attacks.This completes the reduction for collective and coherent attacks.

D. Security against Forging

Forging occurs when Bob makes Charlie accept a fake message, requiring Bob to guess Alice’s declaration. The analysis distinguishes attack powers and identifies verification-stage forging as easier than authentication-stage forging.

  • Forging definition: Forging is successful when Charlie verifies Bob’s fake message without an abort, meaning Bob must guess enough of Alice’s declared signs.The probability is bounded conditionally on Charlie not aborting.
  • Attack classes: The attack taxonomy separates individual, collective, and coherent powers, and also distinguishes attacks beginning during distribution from those launched only during messaging.Individual attacks include identical and non-identical uncorrelated strategies.
  • Verification versus authentication: Forging during verification is easier than forging during authentication: convincing Charlie that Bob forwards Alice’s message is easier than convincing Bob that Bob received it directly from Alice.This comparison follows from the protocol’s asymmetric verification conditions.

1. Security against passive collective forging

For passive collective forging, Bob’s optimal strategy is independent and identically distributed minimum-error measurement on each signature element. The resulting forging probability decreases exponentially with signature length L.

  • Optimal passive strategy: The passive collective optimum is an IID attack using the same minimum-error measurement independently on each signature element.Independent signature-element distributions make adaptive dependence on prior measurements unnecessary for the optimal per-element strategy.
  • Success condition: Bob succeeds only if his guessed signs contain a sufficient percentage of correct values among Charlie’s unambiguous outcomes.The analysis uses the observed mismatch percentage over the unambiguous outcomes and the worst-case non-abort count K = (p_USD − δ)L.
  • Forging bound: The passive collective forging probability decays exponentially in the signature length L.The bound is obtained after applying the protocol’s verification threshold to Bob’s minimum-error guessing strategy.

2. Security against active forging

Active forging attacks are analyzed from IID strategies through more general independent, non-identically distributed and collective strategies, which are shown not to be more powerful than IID attacks.

  • General collective active-forging strategies reduce to IID strategies and are therefore no more powerful.The analysis first considers IID attacks, then extends the reduction to INID and collective strategies.

3. IID active forging attacks

The IID active-forging analysis uses null-port detections to constrain Bob’s ability to alter Charlie’s signature and derives an upper bound on forging probability.

  • Null-port photon detections constrain how much Bob can alter Charlie’s signature during active forging.The protocol aborts when too many null-port photons are detected, bounding the distance between passive and active signal states.
  • The null-port no-detection probability equals the expected fidelity between Charlie’s passive- and active-attack signature states.This relation lets null-port statistics estimate the distance between the states used in Charlie’s USD measurement.
  • The forging bound is deliberately non-tight because it assumes Bob can both measure the entire state and use it to prepare his response state.That capability is physically impossible in the stated model, so the assumption only upper-bounds cheating probability.
  • The active analysis modifies the passive bound using fewer USD outcomes, a lower minimum-error probability, and Bob’s ability to steer Charlie’s outcomes.These changes are represented through pUSD −δ, p′min, and the effective verification-threshold adjustment.
  • The same null-port method extends from identical IID response states to position-dependent INID attacks through an average response state.Hoeffding bounds remain applicable because the relevant binary variables are independent even when they are not identically distributed.

5. Collective active forging attacks

For collective active forging, Bob’s sequential actions can be represented as a mixture of factorized states, so the maximum cheating probability is attained by one factorized strategy.

  • Collective strategies may depend on Bob’s prior actions, but Charlie’s verification probability remains linear in the resulting cumulative state.Bob’s declaration is represented as a classical system, and verification projects onto the accepted-message subspace.
  • The cheating probability is a convex combination of the cheating probabilities of factorized states and is maximized by one such state.The argument uses the linearity of Charlie’s verification process and the no-signalling separation between Bob’s and Charlie’s internal histories.

E. Correctness of the protocol

In the ideal honest case, the protocol never rejects messages, and the probability that neither recipient aborts approaches one exponentially quickly with signature length.

  • In the ideal honest case, neither Bob nor Charlie rejects a message; aborts arise only from atypical USD outcome counts.The allowed unambiguous-outcome interval is [(pUSD −δ)L, (pUSD + δ)L].
  • The probability that neither recipient aborts approaches unit probability exponentially quickly in the signature length L.Correctness therefore requires authentication, verification, and no abort except with negligible probability.

F. Constraints and Choices of Parameters

The protocol parameters are chosen to make correctness, repudiation, and forging probabilities decay exponentially with message length while accommodating implementation imperfections. The coherent-state amplitude must balance unambiguous discrimination against forgery resistance, with α ∼ 0.2 giving indicative performance bounds.

  • The ideal-case simplifications r = 0 and s_a = 0 improve the parameter expressions but are undesirable under imperfections because they increase honest aborts and reduce robustness.
  • The choices δ = 0.1p_USD and s_v = √p'_min/4 provide one parameter setting that guarantees correctness and security.
  • Correctness approaches unity, while repudiation and forging probabilities tend to zero exponentially quickly with L.
  • Very low α yields few unambiguous outcomes, whereas very high α makes forging easier because the states become effectively classical.
  • At α ∼ 0.2, p'_min = 0.27 and p_USD = 0.077; for L = 10^6, P(correct) ≥ 1 − 10^-52, P(rep) ≤ 2×10^-6, and P(forge) ≤ 0.7×10^-18.
Loading 1309.1375v1…