Arbitrated Quantum Digital Signature

This example protocol provides a quantum digital signature scheme where the public (known to all) and private (secret key preserved with the seller) keys are classical in nature, however the signature has a quantum nature. This is based directly on public-key cryptography where the seller's identity is used to generate the public-key and one-time pad generates the private key.

Tags: Quantum Digital Signature, Public key cryptography, Specific Task, Multi Party

Assumptions

• The protocol assumes perfect state preparation, transmissions, and measurements.
• Private-key generation (PKG) is a trusted third party, arbitrator.
• In the signing process, the quantum one-way function used to create the quantum digest is assumed to take polynomial time to compute and is hard to invert.
• Seller and PKG are assumed to have a pre-shared quantum key (say, using QKD)

Outline

Like other QDS protocols, it is divided into two phases: Distribution (Key Generation) and Messaging (Signing and Verification). This scheme is presented between seller (one who signs the message), buyer (one whom the signed message is sent) and PKG (generates and distributes public-private key for seller) and a buyer.

• Key Generation: In this step, PKG generates derives the public key of the seller and generates a private key which is secretly sent to Seller over insecure classical channel. Seller's public key is derived from her personal information such as her email-id over a public channel. A one way function is chosen by PKG randomly and secretly (known as master key), which uses the classical public key as its input. A random OTP of the same length as the function outcome (random key), is used to convert it (the outcome) into seller's private key by performing bit-wise modulo 2 sum (exclusive OR gate). The quantum pre-shared common key (assumption) is then used to one-time pad the private key via Quantum Vernam Cipher (1), (2). The one-time padded cipher-text was communicated to seller (over insecure channel). Seller un-pads the cipher-text to obtain the private key using the pre-shared common key. Hence, in the end, everyone knows seller's public key and, only PKG and seller know her private key.
• Signing: In this step, the seller generates a signature quantum state using the message she wants to send, her public key and private key. The seller selects a quantum one way function publicly to generate a quantum digest (directory) using these classical inputs.
  • The Signer selects two random strings and generates a quantum state of the message using these random strings.
  • The public and the private key are used to generate the signature quantum state from the state produced in the previous step.
  • The Signer then generates a private key state using the two selected random numbers and the private key. Along with that a basis state is generated, which is a set of basis of each qubit in the private key state.
  • Signer then generates a quantum digital digest using the quantum one way function with the message and private key state as input. This process is repeated several times to generate few copies of the quantum digest.
  • The shared key with PKG is used to encrypt the quantum digest using the quantum Vernam cipher and then it is delivered to PKG.
  • PKG decrypts the received ciphertext state and announces publicly that the messages are ready for the Verifier to download and verify.
  • Signers sends the signature to Verifier which includes the signature quantum state, plain text message, timestamp and basis state.

• Verify: In this method, the verifier checks the authenticity of the signature.
  • The Verifier uses Signer's public key and the signature sent to generate a quantum state. According to the Basis state set, the Verifier measures this quantum state and the result of this measurement is converted to a set of classical 2-bit string.
  • One of the randomly selected string by the Signer can be easily inferred by the Verifier from the state after the measurement. The Verifier is then able to generate their own copy of quantum digital digest using the publicly announced quantum one way function.
  • Verifier now publicly gains the timestamp and quantum digital digest from PKG and verifies that state with the produced quantum digital digest in the above step with the SWAP test. As the SWAP test has a probabilistic result, it is performed several times with the copies of quantum digital digest and then verified.
  • If the test is passed the message from the Signer would be valid otherwise it is rejected.

Notation

• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} : Total number of qubits of message.
• $k_{pub}$: Signer's public key, where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k_{pub} \in \{0,1\}^n} .
• $k_{pri}$: Signer's private, where $k_{pri}\in \{0,1\}^{n}$.
• $k_{r}$: Random OTP number selected by PKG to denote each of Signer's signatures, where $k_{r}\in \{0,1\}^{n}$.
• $k_{at}$: Shared key between the Signer and PKG where $k_{at}\in \{0,1\}^{n}$.
• $E_{k_{at}}$: Quantum Vernam cipher encrypted state which uses $k_{at}$.
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} : PKG's master key which is a one way function where $\{0,1\}^{n}{\xrightarrow {}}\{0,1\}^{n}$ .
• $F$: Public quantum one way function selected by Signer to generate quantum digest.
• $m$: Message sent by Signer to the Verifier, where $m\in \{0,1\}^{n}$.
• $s$: Random string of uniform distribution selected by the Signer, where $s\in \{0,1\}^{n}$.
• $t$: Random string of uniform distribution selected by the Signer, where $t\in \{0,1\}^{n}$.
• $|\phi \rangle _{a_{l},b_{l}}$: Quantum state which is defined by

$|\phi \rangle _{a_{l},b_{l}}:=H^{a_{l}}U_{\frac {\pi }{4}}H^{b_{l}}|0\rangle$

• $|\phi \rangle _{a_{l},b_{l},c_{l}}$: Quantum state which is defined by

$|\phi \rangle _{a_{l},b_{l},c_{l}}:=Y^{c_{l}}|\phi \rangle _{a_{l},b_{l}}$

• $|S\rangle _{k_{pri},m}$: Signature quantum state for message $m$ which is the quantum state

$|S\rangle _{k_{pri},m}=\bigotimes _{l=1}^{n}H^{k_{pub_{l}}\oplus k_{pri_{l}}}|\phi \rangle _{s_{l},t_{l}\oplus m_{l},m_{l}}$

• $|P\rangle$: Private key quantum state where $|P\rangle \in \{|+\rangle ,|-\rangle ,|1\rangle ,|0\rangle \}^{n}$ and it is the quantum state:

$|P\rangle :=H^{k_{pri}}|\phi \rangle _{s,t\oplus m}$

• $P$: Classical 2n-bit for $n$-qubit $|P\rangle$ where $|+\rangle$ is encoded to 10, $|-\rangle$ to 11, $|1\rangle$ to 00 and $|0\rangle$ is encoded to 01.
• $B_{P}$: This is the set of the basis of each qubit state in $|P\rangle$.

$B_{P}=Basis(|P\rangle )\in \{+,\times \}$

• $|F\rangle$: Quantum digital digest received by PKG.
• $|F\rangle '$: Quantum digital digest generated by Verifier.
• $u$: The most number of verifiers in this scheme.
• $w$: Safety parameter threshold for acceptance.
• $w_{0}$: Security threshold decided in advance.
• $w'$: Number of times SWAP test is performed.
• $|V\rangle _{m,k_{pub},S}$: A quantum state, where

$|V\rangle _{m,k_{pub},S}:=Y^{m}H^{k_{pub}}|S\rangle _{k_{pri},m}$ This state is also expressed as $\beta |\phi \rangle _{k_{pri}\oplus s,t\oplus m}$ where $\beta \in \{1,-1,\iota ,-\iota \}$

• $|Q\rangle$: Result of Verifier's measurement of $|V\rangle _{m,k_{pub},S}$.
• $Q$: Classical bit string denoted as $Q\in \{00,01,10,11\}^{n}$. It is proven that $P=Q$.
• $\delta$: $\langle F|F\rangle '$, where $\delta \in [0,1)$.

Hardware Requirements

• The total number of qubits used in this protocol is equal to the total number of qubits in the message.
• Secure quantum channel between Signer and Verifier
• Quantum channel between Signer and PKG
• Private database for both Signer and PKG
• Measurement devices for the Verifier.

Properties

• The protocol assumes the PKG to be a trusted party.
• This protocol cannot be broken even if the adversary had unlimited computing power.
• In this protocol, it is proven that no adversary can break the secrecy of the Signer's signature private key.
• The quantum digital signature produces in this protocol is impossible to repudiate and cannot be forged in any condition.
• In the protocol the public and the private key belong to the classical bits, only the signature cipher has quantum nature.
• No Certificate Authority is required to manage digital public-key certificate of Signers.
• If $|F\rangle =|F\rangle '$, the measuring result $|0\rangle$ occurs with probability 1, otherwise it occurs with probability ${\frac {1+\delta ^{2}}{2}}$. Hence, when repeated for $w$ times, the probability of equality is at least 1-$({\frac {1+\delta ^{2}}{2}})^{w}$.

Pseudocode

Stage 1: Key Generation
Output: Signer receives $k_{pri}$ from the PKG.

• $k_{pub}$ is generated on the basis of Signer's public identity information like email or person ID-card.
• PKG aquires $k_{pub}$ through open channels.
• PKG selects $G$ randomly as its master key.
• PKG selects $k_{r}$ randomly.
• PKG calculates $k_{pri}$ as

$k_{pri}:=G(k_{pub})\oplus k_{r}$

• PKG uses $k_{at}$ to encrypt $k_{pri}$ and transmits $E_{k_{at}}$ to Signer.
• Signer decrypts $E_{k_{at}}$ using $k_{at}$ and receives $k_{pri}$.

Stage 2: Signature
Output: PKG receives the quantum digest $|F\rangle$ and the Verifier receives the Signature $(ts,m,B_{P},|S\rangle _{k_{pri},m})$ from the Signer.

• Signer wants to sign the message $m$.
• Signer selects $s$ and $t$.
• For $l=1,2,...n$:
  • Signer generates the state $|\phi \rangle _{s_{l},t_{l}\oplus m_{l},m_{l}}$, which is:

$|\phi \rangle _{s_{l},t_{l}\oplus m_{l},m_{l}}=Y^{m_{l}}H^{s_{l}}U_{\frac {\pi }{4}}H^{t_{l}\oplus m_{l}}|0\rangle$

• For $l=1,2,...n$:
  • Signer generates the Signature quantum state $|S\rangle _{{k_{pri}}_{l},m_{l}}$, which is

$|S\rangle _{{k_{pri}}_{l},m_{l}}=H^{k_{pub_{l}}\oplus k_{pri_{l}}}|\phi \rangle _{s_{l},t_{l}\oplus m_{l},m_{l}}$

• For $l=1,2,...n$:
  • Signer generates the private key quantum state $|P\rangle _{l}$, which is

$|P\rangle _{l}=H^{k_{pri_{l}}}|\phi \rangle _{s_{l},t_{l}\oplus m_{l}}$

• • The classical $P_{l}$ is calculated based on $|P\rangle _{l}$.
  • The basis set is formed by Signer is:

$B_{P_{l}}=Basis(|P\rangle _{l})\in \{+,\times \}$

• For $k=1,2,...uw$: Different copies of the quantum digital digest state is prepared.
  • For $l=1,2,...n$:

1. The quantum digital digest state $|F\rangle _{l}$ is prepared by Signer, where:

$|F\rangle _{l}=|F(t_{l}||m_{l}||P_{l}||t_{l}s_{l})\rangle _{l}$

• Signer encrypts $|F\rangle$ using quantum Vernam cipher and sends $E_{k_{at}}(ts,\otimes _{l=1}^{uw}|F\rangle )$ to PKG.
• PKG decrypts $E_{k_{at}}(ts,\otimes _{l=1}^{uw}|F\rangle )$ using $k_{at}$ and gets $(ts,\otimes _{l=1}^{uw}|F\rangle )$.
• PKG announces publicly that the quantum digest is ready.
• Signer transmits $(ts,m,B_{P},|S\rangle _{k_{pri},m})$ to Verifier, which is the signature.

Stage 3: Verification
Output: $m$ is considered valid or is rejected by the Verifier.

• Verifier receives $|k\rangle _{pub}$ from open channels.
• Verifier generates the state $|V\rangle _{m,k_{pub},S}$.
• For $l=1,2,...w$:
  • Verifier measure the state $|V\rangle _{{(m,k_{pub},S)}_{l}}$ according to the basis (diagonal or horizontal) in $B_{P_{l}}$.
  • The result of the measurement is recorded as $|Q\rangle _{l}$, which is converted to $Q_{l}$.
• $t$ is inferred by the Verifier using $Q$
• Verifier gains $(ts,\otimes _{l=1}^{w}|F\rangle )$ from PKG.
• For $k=1,2,...w'$:
  • Verifier generates $|F\rangle '$ using $F$ by the calculation

$|F\rangle '=|F(t||m||Q||ts)\rangle$

• • Verifier gains $(ts,|F\rangle )$ from PKG.
  • Verifier performs SWAP test between $|F\rangle$ and $|F\rangle '$.
• If $w'>w_{0}$ and measurement result everytime = $|0\rangle '$:
  • Verifier counts the message $m$ as valid.
• else:
  • $m$ is rejected by the Verifier.

Further Information

Like most other classical digital signature schemes which provide unconditional security, this scheme also requires a trusted arbitrator who distributes public key to the recipients.

References

1. BR (2000)
2. Zhou et al. (2006)

*contributed by Rhea Parekh