Cryptography

Digital (pseudo) signatures

Definition of pseudo signatures

Taken from [complete_pseudo_signatures]:

Three parties:

• Alice (sender), has input $b\in \{0,1\}$,
• Bob (receiver 1), has output $b_B\in \{0,1,\perp \}$, and
• Charlie (receiver 2), has output $b_C\in \{0,1,\perp \}$

Two phases:

• signature phase where Bot outputs $b_B$ and if $b_B\ne \perp$ proceed to
• transfer phase where Charlie outputs $b_C$

Properties:

• Correctness: if Alice and Bob are honest, $b_B=b$ with high probability
• Unforgeability: if Alice and Charlie are honest, then probability of $b_C\notin \{b,\perp \}$ is small
• Transferability: if Bob and Charlie are honest then the probability of having both $b_B\ne \perp$ and $b_C\ne b_B$ is small
• Secrecy (optional?): Charlie’s view in the signing phase is almost independent from $b$

Quantum algorithms

• [QDS]

  Consider a set of sufficiently orthogonal (but not orthogonal) functions: $F=|f_1⟩,|f_2⟩,\dots ,|f_N⟩$,

  NB $N$ is much higher than $2^n$, where $n$ is the number of qubits

  • public key: generate $k_0$ and $k_1$ and set public key as $(F,(0,f_{k_0^1}),(1,f_{k_1^2}),\dots ,(0,f_{k_0^l}),(1,f_{k_1^l}))$
  • signing: $b\mapsto (b,k_b^1,\dots ,k_b^l)$
  • verifying: reverse test checking that all the functions computed right plus two thresholds: $c_1$ and $c_2$

• [QDSNoMemory]

  There’re coherent states $|\alpha ⟨$ and $|-\alpha ⟨$, s.t. it’s efficient to:

  • check they’re the same (null-port must be zero)
  • symmetrize two states (giving $|(\alpha +\beta )/2⟨$)
  • identify what’s the symmetrized state is

  The protocol (Alice is sending to Bob and Charlie):

  • private key are random sequences of signs $P{K}^k=(b_1^k,\dots ,b_L^k)$ for $k\in \{0,1\}$ and $b\in \{-1,1\}$

  • public key are the two sequences of quantum states $|b_l^k\alpha ⟨$

  • preparation:

    • Bob and Charlie use QDS multiport to a) check if they get the same state b) symmetrize input
    • Bob and Charlie measure output from multiport to identify what was the sign

  • signature: Alice releases $(b,P{K}^b)$

  • verification:

    • check that there’s equivocation is unlikely (occurrences of null-port being non-zero is low)

    • check that there’s an expected number of unambiguous measurement outcomes (when doing the second step)

    • number of mismatches with the private key should not be too large

      NB thresholds for this step are different for Charlie and Bob, which is necessary if Alice tries to make one accept and another reject

Secret Sharing

See [QMPC]