Gottesman and Chuang Quantum Digital Signature: Difference between revisions

From Quantum Protocol Zoo
Jump to navigation Jump to search
 
(119 intermediate revisions by 4 users not shown)
Line 1: Line 1:
The [https://arxiv.org/abs/quant-ph/0105032 example protocol] achieves the functionality of [[Quantum Digital Signature|(Quantum) Digital Signatures (QDS)]] allowing the exchange of classical messages from sender to multiple recipients, with a guarantee that the signature has come from a genuine sender. This protocol achieves all the [[Quantum Digital Signature#Properties|properties]] of QDS. Further it requires the parties to store quantum states for comparison at a later stage thus necessitating the requirement of quantum memory. This protocol is based quantum public key cryptography.<br/><br/>
'''Tags:''' [[:Category:Multi Party Protocols|Multi Party (three)]], [[:Category:Quantum Enhanced Classical Functionality|Quantum Enhanced Classical Functionality]], [[:Category:Specific Task|Specific Task]], [[Quantum Digital Signature]], [[Prepare and Measure Quantum Digital Signature]], [[Measurement Device Independent Quantum Digital Signature (MDI-QDS)]]
[[Category:Multi Party Protocols]][[Category:Quantum Enhanced Classical Functionality]][[Category:Specific Task]]


== Functionality Description==
==Assumptions==
Digital Signatures (QDS) allow the exchange of classical messages from sender to multiple recipients, with a guarantee that the signature has come from a genuine sender. Additionally, it comes with the properties of (i) [[transferability]] i.e. messages with DS can be forwarded from one recipient to another such that DS is verifiable to have come from the original sender, (ii) [[non-repudiation]] i.e at any stage after sending the message to one recipient, sender cannot deny having sent the message and corresponding DS, and (iii) [[unforgeability]] i.e. a dishonest recipient cannot alter or fake the sender's DS and forward it to other recipients successfully.<br/> Such protocols require parties to store quantum states for comparison at a later stage. For simplicity, most protocols take into account the case of one sender and two recipients (Seller, buyer and verifier) exchanging single-bit classical messages.
* Perfect devices and channels have been assumed
* It has been assumed that all recipients have received correct and identical copies of Seller's public key (explained later)
* All participants know, the map which takes private keys to public keys, threshold value of acceptance (<math>c_1</math>) and threshold value for rejection (<math>c_2</math>)
* Distribution of public keys requires [[authenticated]] quantum and classical channels between all parties


'''Tags:''' [[Multi Party Protocols|Multi Party (three)]], [[Quantum Enhanced Classical Functionality|Quantum Enhanced Classical Functionality]], [[Specific Task|Specific Task]], [[Quantum Digital Signature]], [[Prepare and Measure Quantum Digital Signature]], [[Measurement Device Independent Quantum Digital Signature (MDI-QDS)]]
==Outline==
The signature scheme proposed by Gottesman and Chuang is based on [[Glossary#Quantum One Way Function|quantum one way functions]], which takes classical bit string as input and outputs quantum states. Quantum Digital Signature (QDS) protocols can be divided into two phases: the distribution phase, where quantum signals (public keys) are sent to all recipients, and the messaging phase, where classical messages are signed, sent and verified. Here, we take the case of three parties, one sender (referred to as seller) and two receivers (buyer and verifier) sharing a one bit message. Distribution phase can be divided into the following two steps:
*'''Key Generation:''' For each message bit (say 0 and 1), seller selects some (say M) classical bit strings randomly. These are chosen to be her private keys for that message bit. Using this private key as input, seller generates output of the quantum one-way function/map, which she calls her public key and as assumed above, distributes them to each recipient, for each message bit. In the end of this step, each recipient has 2M public keys, M for message bit 0 and M for message bit 1. Following are a few suggestions for the quantum one way functions, by the authors.
'''Quantum One Way Functions:''' The author suggests [[Gottesman and Chuang Quantum Digital Signature#References|quantum fingerprint states (1)]], [[Gottesman and Chuang Quantum Digital Signature#References|stabilizer states (2)]] to represent classical strings in terms of quantum states. The number of qubits for the quantum state used, to represent each bit in the classical string, depends on which of the above methods is used. Another method where each classical bit is represented by one quantum bit, is also suggested.
* '''Key Distribution:''' The authors suggest a few methods for key distribution. One of them is the assumption of a trusted third party who receives public keys from seller, checks all the keys using [[Quantum SWAP Test]] and then if test is passed by each key sent, the trusted party distributes it to the recipients. A second method eliminates the requirement of a trusted third party and instead requires Sender to send two copies of each public key to each recipient, such that, in the end each recipient has 4M keys (2M public keys for each message bit). Both buyer and verifier perform quantum swap test on their supposedly identical copies of public keys. Then, if passed, Buyer sends one copy of his public key to the verifier, who then performs the SWAP test between the received copy and his copy of public key.
Similarly, messaging stage can be described as follows:
*'''Messaging:''' Seller sends her message bit with the associated private keys to the buyer. Buyer performs the map on the private key (quantum one way function takes the sent private key as input) and then compares the output thus generated with the public key received in the distribution stage. If the number of unmatched bits are below rejection threshold, the message is declared valid, else invalid. If the number of unmatched bits is below acceptance threshold, it is declared transferable, else not transferable.


== Requirements ==
A generalized scheme for more than three parties is given in the article. Also, for multi-bit messages, a scheme using error correcting codes has been suggested in brief.
*'''Network Stage:''' Quantum Memory
*'''Relevant Network Parameters:'''
*'''Benchmark values:'''


==Use Case==
==Notations==
Online Transactions, Signing Marksheets
* m: message bit (0 or 1)
* M: number of private keys chosen/produced for each message bit
* k: classical string/ private key
*<math>k_m^i</math>: <math>i^{th}</math> bit of private key k for message bit m
* <math>|f(k)\rangle</math>: quantum output of quantum one way function (public key) with classical input bit k
* L: length of private key
* n: number of qubits in the quanutm state <math>|f_k\rangle</math>
*<math>f_{new}</math>: quantum output of buyer when he uses the seller's sent signature (private key <math>k_b^i</math> to sign message bit b) as an input to publicly known quantum one way function.
* <math>c_1</math>: threshold for acceptance
* <math>c_2</math>: threshold for rejection


==Example:==  
==Properties==
===Outline===
*The public keys can be used only once.
----
*Only limited (T) distribution of public keys should be allowed, such that <math>T < L/n</math>, where quantum public key is an 'n' qubit state.
Quantum Digital Signature (QDS) protocols can be separated into two stages: the distribution stage, where quantum signals (public keys) are sent to all recipients, and the messaging stage, where classical messages are signed, sent and verified. Here, we take the case of three parties, one sender (referred to as seller) and two receivers (buyer and verifier) sharing a one bit message.  
* Unlike some classical information-theoretic (unconditional security) schemes which require secure anonymous broadcast channel or noisy channel, which are hard to achieve resources, the quantum scheme provides information-theoretic security by only demanding plausible quantum channels and modest interaction between parties involved.
Distribution phase can be divided into the following steps:
* The scheme is secure against forgery if <math>(1-\delta^2)(M-G)>c_2M</math>, where <math>G=2^{-(L-Tn)}2M</math> and <math>\delta</math> depends on public keys and hence, on quantum one way functions. <math>\delta\sim 0.9</math> for quantum fingerprint states; <math>\delta\sim 1/\sqrt{2}</math> for stabilizer states. For the method where one classical bit is represented by one qubit, which consists of the states <math>cos(j\theta)+sin(j\theta)</math>, for <math>\theta=\pi/2^L</math>, <math>\delta=cos(\theta)</math>.
*''' Key Distribution:'''
* The Seller can successfully repudiate by probability, <math>p_{cheat}\sim O(d^{-M})</math>, for some <math>d>1</math>.
Figure
Similarly, Messaging Phase is divided into the following steps:
*''' Signing:'''
*''' Transfer:'''


===Properties===
== Requirements ==
----
*'''Network Stage:''' [[Category: Quantum Memory Network Stage]][[:Category: Quantum Memory Network Stage|Quantum Memory]]
*The protocol-
* '''Required parameters:''' Size of public key (n), private key (L), signed message (1, in above case)
**involves three parties (Seller, Buyer, Verifier) exchanging one-bit classical messages.
* '''Scalability:'''
**'''Requires''' [[BB84 QKD]] setup, [[authenticated]] quantum and classical channels
**Size of public key increases as logarithm of number of recipients.
**assumes maximum number of participating parties are honest. In the present case at least two parties are honest.
** Size of private key, <math>L\ge T</math> where T must be linear or quadratic in the number of recipients.
**provides information-theoretic security
**Size of signed message scales linearly with L.
**provides security against repudiation, i.e. the probability that seller succeeds in making buyer and seller disagree on the validity of her sent quantum signature decays exponentially with L, as stated by the formula <math>P(\text{rep})\le e^{-(s_v-s_a)^2L}</math>.
**Total amount of keys consumed scales linearly with number of messages sent.
**provides security against forgery, i.e. any recipient (verifier) with high probability rejects any message which was not originally sent by the seller herself. Forging probability is given by the formula, <math>P(\text{forge})\le e^{-(c_{\min}-2s_v)^2L}</math>, where <math>c_{\min}</math> is 3/8 (calculated using uncertainty principle).
*'''Benchmark values:''' No experimental implementation using qubits. See [[Gottesman and Chuang Quantum Digital Signature#Further Information|Experimental Papers (1)]] for implementation using coherent states.


===Pseudo Code===
==Knowledge Graph==
----
{{graph}}
*'''Notations Used:'''
 
**L: Length of keys used
==Protocol Description==
**<math>s_a</math>: Threshold value for signing
**<math>s_v</math>: Threshold value for verification
**<math>|\psi^k\rangle</math>: Quantum Public key for message k 
**<math>\{\beta^k_1,...,\beta^k_L\}</math>: Classical Private key for classical one-bit message k
**<math>\beta^k_l</math>: Classical description of <math>l^{th}</math> qubit in <math>|\psi^k\rangle</math>
**<math>B^m</math>: Buyer's Eliminated Signature for message m
**<math>V^m</math>: Verifier's Eliminated Signature for message m
**<math>b^k_l</math>: Buyer’s random bit to determine the measurement basis of <math>l^{th}</math> qubit in <math>|\psi^k\rangle</math>
**<math>v^k_l</math>: Verifier’s random bit to determine the measurement basis of <math>l^{th}</math> qubit in <math>|\psi^k\rangle</math>
**<math>m_{b^k_l}</math>: measurement outcome of <math>b^k_l</math>


<u>'''Stage 1'''</u> Distribution
<u>'''Stage 1'''</u> Distribution
*'''Input''' L
*'''Input''' L
*'''Output''' Seller: <math>\{\beta^0_1,...,\beta^0_L\},\{\beta^1_1,...,\beta^1_L\}</math>; Buyer: <math>B^0,B^1</math>; Verifier: <math>V^0,V^1</math>
*'''Output''' Seller: <math>\{k_0^i, k_1^i\}</math>, <math>1\le i\le M</math>, <math>|\{f(k_0^i)\rangle, |f(k_1^i)\rangle\}</math>
**'''Key Distribution:'''
**'''Key Generation'''
#For k = 0,1
#For m = 0,1
## Seller prepares quantum public key <math>|\psi^k\rangle=\bigotimes^L_{l=1}|\beta^k_l\rangle</math>, where <math>\beta^k_l\in_R \{0,1,+,-\}</math>
##For i=0,M
## She sends Buyer (k,<math>|\psi^k\rangle</math>)
###Seller generates classical bits <math>k_m^i</math>
## She sends Verifier (k,<math>|\psi^k\rangle</math>)
##Seller performs quantum one way map: <math>k_m^i\rightarrow |f(k_m^i)\rangle</math> 4 times for each element, so to have 4 copies denoted <math>|f(k_m^i)\rangle^j</math> with j from 1 to 4
**'''State Elimination:'''  
#For k = 0,1
##For l = 1,2,...,L
### Buyer chooses <math>b^k_l \epsilon_R {0,1}</math>  
###If <math>b^k_l=0</math>, Buyer measures his qubit in X basis <math>\{|+\rangle,|-\rangle\}</math>
###If <math>b^k_l=0</math>, Buyer measures his qubit in Z basis <math>\{|0\rangle,|1\rangle\}</math>
###'''return''' <math>m_{b^k_l}</math>
###<math>B^k_l=1-m_{b^k_l}</math>


**Verifier repeats steps 2(a)-2(b) with randomly chosen basis <math>v^k_l</math> to get his eliminated signature elements <math>V^k_l</math>
**'''Key Distribution:''' (No Trusted Third Party Assumption)
 
#For m = 0,1
**'''Symmetrisation'''
##For i=0,M
##For k = 0,1
###Seller sends <math>|f(k_m^i)\rangle^j</math> to buyer for j=1,2 and verifier for j=3,4
### Buyer chooses I<math>\subset_R\{1,2,...,L\}, |I|=[L/2]</math>
###Buyer performs '''QSWAP TEST'''<math>(|f(k_m^i)\rangle^1, |f(k_m^i)\rangle^2)</math>
### <math>\forall i\epsilon I</math>, Buyer sends Verifier <math>(k,i,b^k_i,B^k_i)</math>  
###If QSWAP TEST= '''False''', protocol aborted
### Verifier chooses J<math>\subset_R\{1,2,...,L\}, |J|=[L/2]</math>
###If QSWAP TEST= '''True''', Buyer sends any of <math>|f(k_m^i)\rangle^2, |f(k_m^i)\rangle^1</math> (supposedly equal) to verifier, we will denote it with b superscript
### <math>\forall j\epsilon J</math>, Verifier sends Buyer <math>(k,j,v^k_j,V^k_j)</math>  
###Verifier performs similar steps and sends any of <math>|f(k_m^i)\rangle^3, |f(k_m^i)\rangle^4</math> (supposedly equal) to buyer, we will denote it with v superscript
### <math>\forall j\epsilon J</math> Buyer replaces <math>B^k_l=V^k_l</math>
###Both perform '''QSWAP TEST'''<math>(|f(k_m^i)\rangle^{b},|f(k_m^i)\rangle^{v})</math> on the copies they have
### <math>\forall i\epsilon I</math> Verifier replaces <math>V^k_l=B^k_l</math>
###If QSWAP TEST= '''False''', protocol aborted
###If QSWAP TEST= '''True''', distribution successful


<u>'''Stage 2'''</u> Messaging
<u>'''Stage 2'''</u> Messaging
   
   
*'''Input''' Seller: Message m, Private Key for m: <math>\{\beta^m_1,...,\beta^m_L\}</math>
*'''Input''' Seller: Message b, Private Key for <math>k_b</math>
*'''Output''' Buyer: accept or abort, Verifier: accept or abort
*'''Output''' Buyer: '''1-ACC''' (Message is valid and transferable), '''0-ACC''' (Message is valid but not transferable), '''REJ''' (Message is invlaid)
**'''Signing:''' ’mismatch’ is when Buyer finds an eliminated signature element in Seller’s private key
**'''Signing:'''  
# Seller sends Buyer (m,<math>\{\beta^m_1,...,\beta^m_L\}</math>)
# For i=1,M
# Seller sends Buyer (b,<math>k_b^i</math>)
# For l = 1,2,..,L
# For l = 1,2,..,L
##Buyer counts the number of mismatches (<math>B^m_l=V^m_l</math>) and returns <math>S_b</math>
## Buyer performs <math>k_b^i\rightarrow f_{new}</math>
# If <math>S_b < s_aL/2</math>, Buyer accepts m else he aborts
## Buyer performs '''QSWAP TEST'''<math>(f_{new},f_{k_b^i})</math>
**'''Transfer'''
## If QSWAP TEST= False, <math>s_B=s_B+1</math>
# Buyer sends Verifier (m,<math>\{\beta^m_1,...,\beta^m_L\}</math>)  
#If <math>s_B<c_1M</math>, result '''1-ACC'''
# For l = 1,2,....,L
#If <math>c_1M<s_B<c_2M</math>, result '''0-ACC'''
##Verifier counts the number of mismatches (<math>V^m_l=B^m_l</math>) and returns <math>S_v</math>
#If <math>s_B>c_2M</math>, result '''REJ'''
# If <math>S_v < s_vL/2</math>, Verifier accepts m else he aborts
 
==Further Information==
This protocol was the first ever scheme designed for Quantum Digital Signatures. Due to unavailability of quantum memory at the current stage, this scheme has not seen enough experimental implementations, yet variations of the same without the need of quantum memory has some progress such as [[Prepare and Measure Quantum Digital Signature]], [[Measurement Device Independent Quantum Digital Signature (MDI-QDS)]], etc..
Following is the list of few more protocols with similar requirement (quantum memory) but small variations.
*'''Theoretical Papers'''
# [https://arxiv.org/abs/quant-ph/0105032 GC (2001)] above protocol
#[https://arxiv.org/abs/quant-ph/0601130 ACJ (2006)] discusses coherent states comparison with a QDS scheme outlined in the last section.
##Protocol uses the same protocol as (2) but replaces qubits with [[coherent states]], thus replacing SWAP-Test with [[Coherent State Comparison]]. Additionally, it also requires quantum memory, authenticated quantum and classical channels, [[multiports]].  
##Security: [[Information-theoretic]]
#[https://www.sciencedirect.com/science/article/pii/S0030402617308069 Shi et al (2017)] Discusses an attack and suggests corrections on existing QDS scheme using single qubit rotations. Protocol uses rotation, qubits, [[one-way hash function]]; Private keys: angle of rotation, Public keys: string of rotated quantum states.
##'''Requires''' [[random number generator]], [[one-way hash function]], quantum memory, key distribution.
##'''Security:''' [[Computational]]
*'''Experimental Papers'''
#[https://www.nature.com/articles/ncomms2172 Clarke et al (2012)] uses phase encoded coherent states, [[coherent state comparison]]
##Loss from multiport=7.5 dB, Length of the key= <math>10^6</math>
==References==
# [https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.87.167902 Burhman et al (2001)]
# Nielsen M. A. and Chuang I. L. Quantum computation and quantum information. Cambridge University Press, Cambridge, UK, 2000.


==Discussion==
<div style='text-align: right;'>''*contributed by Shraddha Singh''</div>
*Theoretical Papers
#[https://arxiv.org/abs/1403.5551  WDKA (2015)] above example
# [https://arxiv.org/abs/quant-ph/0105032 GC-QDS (2001)] uses [[quantum one way function]] f(); Private keys: classical input x, Public keys: quantum output f(x). '''Requires''' quantum memory, quantum one way function, authenticated quantum and classical channels, [[SWAP Test]] (universal quantum computer). [[Unconditionally Secure]]. [[Network Stage: Quantum Memory]]
#[https://arxiv.org/abs/quant-ph/0601130 ACJ (2006)] discusses coherent states comparison with a QDS scheme outlined in the last section. Protocol uses the same protocol as (2) but replaces qubits with [[coherent states]], thus replacing SWAP-Test with [[Coherent State Comparison]]. Additionally, it also requires quantum memory, authenticated quantum and classical channels, [[multiports]]. [[Unconditionally Secure]], [[Network Stage: Quantum Memory]]
#[https://arxiv.org/abs/1309.1375 DWA (2013)] first QDS scheme without quantum memory based on [https://arxiv.org/abs/quant-ph/0601130 (3)]. '''Requires''' [[Coherent States]], authenticated quantum and classical channels, [[multiports]], [[Unambiguous State Discrimination (USD)]] (State Elimination), no symmetrisation required. [[Unconditionally Secure]]. [[Network Stage: Prepare and Measure]]
#[https://journals.aps.org/pra/abstract/10.1103/PhysRevA.90.042335 AL (2014)] Establishes coherent state mapping of (2). Replaces SWAP Test with beam splitters. Uses [[Unambiguous State Discrimination (USD)]] (State Elimination). '''Requires''' [[Phase encoded Coherent states]], [[Balanced Beam Splitters]]. No explicit security proof provided. [[Network Stage: Prepare and Measure]]
#[https://arxiv.org/abs/1505.07509 AWA (2015)] security proof for generalisation of [https://arxiv.org/abs/1403.5551  WDKA (2015)] and [https://arxiv.org/abs/1309.1375 DWA (2013)] to more than two recipients case.
#[https://www.researchgate.net/publication/280062082_Practical_Quantum_Digital_Signature YFC (2016)] first QDS scheme without authenticated (trusted) quantum channels. Demonstrates one protocol with two implementation, [[two copies of single photon]] method and  [[decoy state]] method. First uses single qubit photons in three bases; Private key: classical description of states, Public key: pair of [[non-orthogonal states]] in any two of the three bases. '''Requires''' authenticated classical channels, [[polarisation measurement]] in three bases, [[Unambiguous State Discrimination (USD)]] (State Elimination), uses quantum correlations to check authentication.  Decoy State method uses [[phase-randomised weak coherent states]], [[50:50 Beam Splitter (BS)]], [[Unconditionally Secure]] [[Network Stage: Prepare and Measure]].
#[https://www.researchgate.net/publication/280034032_Secure_Quantum_Signatures_Using_Insecure_Quantum_Channels  AWKA (2015)] QDS scheme without authenticated quantum channels using parameter estimation phase. Uses a Key Generations Protocol (KGP) where noise threshold for Seller-Buyer and Seller-Verifier is better than when distilling secret key from QKD. Seller sends different key to Buyer and Verifier using KGP. This anamoly is justifiable due to symmetrisation.'''Requires''' authenticated classical channels, [[decoy state BB84 QKD]] setup. [[Unconditionally Secure]] [[Network Stage: Prepare and Measure]].
#[http://iopscience.iop.org/article/10.1088/1742-6596/766/1/012021 MH (2016)] security proof for generalisation of [https://www.researchgate.net/publication/280034032_Secure_Quantum_Signatures_Using_Insecure_Quantum_Channels  AWKA (2015)] to more than two recipients case.
#[https://www.nature.com/articles/srep09231 WCRZ (2015)] demonstrates sending multi-bit classical messages using [https://www.researchgate.net/publication/280034032_Secure_Quantum_Signatures_Using_Insecure_Quantum_Channels  AWKA (2015)] or other similar protocols.
#[https://www.sciencedirect.com/science/article/pii/S0030402617308069 SWZY (2017)] Discusses an attack and suggests corrections on existing QDS scheme using single qubit rotations. Protocol uses rotation, qubits, [[one-way hash function]]; Private keys: angle of rotation, Public keys: string of rotated quantum states. '''Requires''' [[random number generator]], [[one-way hash function]], quantum memory, key distribution. [[Computationally Secure]], [[Third Network Stage: Quantum Memory|Third Network Stage (Quantum Memory)]]
*Experimental Papers

Latest revision as of 10:53, 10 May 2024

The example protocol achieves the functionality of (Quantum) Digital Signatures (QDS) allowing the exchange of classical messages from sender to multiple recipients, with a guarantee that the signature has come from a genuine sender. This protocol achieves all the properties of QDS. Further it requires the parties to store quantum states for comparison at a later stage thus necessitating the requirement of quantum memory. This protocol is based quantum public key cryptography.

Tags: Multi Party (three), Quantum Enhanced Classical Functionality, Specific Task, Quantum Digital Signature, Prepare and Measure Quantum Digital Signature, Measurement Device Independent Quantum Digital Signature (MDI-QDS)

Assumptions[edit]

  • Perfect devices and channels have been assumed
  • It has been assumed that all recipients have received correct and identical copies of Seller's public key (explained later)
  • All participants know, the map which takes private keys to public keys, threshold value of acceptance () and threshold value for rejection ()
  • Distribution of public keys requires authenticated quantum and classical channels between all parties

Outline[edit]

The signature scheme proposed by Gottesman and Chuang is based on quantum one way functions, which takes classical bit string as input and outputs quantum states. Quantum Digital Signature (QDS) protocols can be divided into two phases: the distribution phase, where quantum signals (public keys) are sent to all recipients, and the messaging phase, where classical messages are signed, sent and verified. Here, we take the case of three parties, one sender (referred to as seller) and two receivers (buyer and verifier) sharing a one bit message. Distribution phase can be divided into the following two steps:

  • Key Generation: For each message bit (say 0 and 1), seller selects some (say M) classical bit strings randomly. These are chosen to be her private keys for that message bit. Using this private key as input, seller generates output of the quantum one-way function/map, which she calls her public key and as assumed above, distributes them to each recipient, for each message bit. In the end of this step, each recipient has 2M public keys, M for message bit 0 and M for message bit 1. Following are a few suggestions for the quantum one way functions, by the authors.

Quantum One Way Functions: The author suggests quantum fingerprint states (1), stabilizer states (2) to represent classical strings in terms of quantum states. The number of qubits for the quantum state used, to represent each bit in the classical string, depends on which of the above methods is used. Another method where each classical bit is represented by one quantum bit, is also suggested.

  • Key Distribution: The authors suggest a few methods for key distribution. One of them is the assumption of a trusted third party who receives public keys from seller, checks all the keys using Quantum SWAP Test and then if test is passed by each key sent, the trusted party distributes it to the recipients. A second method eliminates the requirement of a trusted third party and instead requires Sender to send two copies of each public key to each recipient, such that, in the end each recipient has 4M keys (2M public keys for each message bit). Both buyer and verifier perform quantum swap test on their supposedly identical copies of public keys. Then, if passed, Buyer sends one copy of his public key to the verifier, who then performs the SWAP test between the received copy and his copy of public key.

Similarly, messaging stage can be described as follows:

  • Messaging: Seller sends her message bit with the associated private keys to the buyer. Buyer performs the map on the private key (quantum one way function takes the sent private key as input) and then compares the output thus generated with the public key received in the distribution stage. If the number of unmatched bits are below rejection threshold, the message is declared valid, else invalid. If the number of unmatched bits is below acceptance threshold, it is declared transferable, else not transferable.

A generalized scheme for more than three parties is given in the article. Also, for multi-bit messages, a scheme using error correcting codes has been suggested in brief.

Notations[edit]

  • m: message bit (0 or 1)
  • M: number of private keys chosen/produced for each message bit
  • k: classical string/ private key
  • 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_m^i} : bit of private key k for message bit m
  • 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 |f(k)\rangle} : quantum output of quantum one way function (public key) with classical input bit k
  • L: length of private key
  • n: number of qubits in the quanutm state
  • 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 f_{new}} : quantum output of buyer when he uses the seller's sent signature (private key to sign message bit b) as an input to publicly known quantum one way function.
  • : threshold for acceptance
  • 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 c_2} : threshold for rejection

Properties[edit]

  • The public keys can be used only once.
  • Only limited (T) distribution of public keys should be allowed, such that 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 T < L/n} , where quantum public key is an 'n' qubit state.
  • Unlike some classical information-theoretic (unconditional security) schemes which require secure anonymous broadcast channel or noisy channel, which are hard to achieve resources, the quantum scheme provides information-theoretic security by only demanding plausible quantum channels and modest interaction between parties involved.
  • The scheme is secure against forgery if 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 (1-\delta^2)(M-G)>c_2M} , where and 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 \delta} depends on public keys and hence, on quantum one way functions. for quantum fingerprint states; for stabilizer states. For the method where one classical bit is represented by one qubit, which consists of the states 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 cos(j\theta)+sin(j\theta)} , for , 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 \delta=cos(\theta)} .
  • The Seller can successfully repudiate by probability, , for some .

Requirements[edit]

  • Network Stage:Quantum Memory
  • Required parameters: Size of public key (n), private key (L), signed message (1, in above case)
  • Scalability:
    • Size of public key increases as logarithm of number of recipients.
    • Size of private key, 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 L\ge T} where T must be linear or quadratic in the number of recipients.
    • Size of signed message scales linearly with L.
    • Total amount of keys consumed scales linearly with number of messages sent.
  • Benchmark values: No experimental implementation using qubits. See Experimental Papers (1) for implementation using coherent states.

Knowledge Graph[edit]

Protocol Description[edit]

Stage 1 Distribution

  • Input L
  • Output Seller: , ,
    • Key Generation
  1. For m = 0,1
    1. For i=0,M
      1. Seller generates classical bits
    2. Seller performs quantum one way map: 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_m^i\rightarrow |f(k_m^i)\rangle} 4 times for each element, so to have 4 copies denoted 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 |f(k_m^i)\rangle^j} with j from 1 to 4
    • Key Distribution: (No Trusted Third Party Assumption)
  1. For m = 0,1
    1. For i=0,M
      1. Seller sends to buyer for j=1,2 and verifier for j=3,4
      2. Buyer performs QSWAP TEST
      3. If QSWAP TEST= False, protocol aborted
      4. If QSWAP TEST= True, Buyer sends any of (supposedly equal) to verifier, we will denote it with b superscript
      5. Verifier performs similar steps and sends any of 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 |f(k_m^i)\rangle^3, |f(k_m^i)\rangle^4} (supposedly equal) to buyer, we will denote it with v superscript
      6. Both perform QSWAP TESTFailed 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 (|f(k_m^i)\rangle^{b},|f(k_m^i)\rangle^{v})} on the copies they have
      7. If QSWAP TEST= False, protocol aborted
      8. If QSWAP TEST= True, distribution successful

Stage 2 Messaging

  • Input Seller: Message b, Private Key for
  • Output Buyer: 1-ACC (Message is valid and transferable), 0-ACC (Message is valid but not transferable), REJ (Message is invlaid)
    • Signing:
  1. For i=1,M
  2. Seller sends Buyer (b,)
  3. For l = 1,2,..,L
    1. Buyer performs
    2. Buyer performs QSWAP TEST
    3. If QSWAP TEST= False, 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 s_B=s_B+1}
  4. If , result 1-ACC
  5. If , result 0-ACC
  6. If 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 s_B>c_2M} , result REJ

Further Information[edit]

This protocol was the first ever scheme designed for Quantum Digital Signatures. Due to unavailability of quantum memory at the current stage, this scheme has not seen enough experimental implementations, yet variations of the same without the need of quantum memory has some progress such as Prepare and Measure Quantum Digital Signature, Measurement Device Independent Quantum Digital Signature (MDI-QDS), etc.. Following is the list of few more protocols with similar requirement (quantum memory) but small variations.

  • Theoretical Papers
  1. GC (2001) above protocol
  2. ACJ (2006) discusses coherent states comparison with a QDS scheme outlined in the last section.
    1. Protocol uses the same protocol as (2) but replaces qubits with coherent states, thus replacing SWAP-Test with Coherent State Comparison. Additionally, it also requires quantum memory, authenticated quantum and classical channels, multiports.
    2. Security: Information-theoretic
  3. Shi et al (2017) Discusses an attack and suggests corrections on existing QDS scheme using single qubit rotations. Protocol uses rotation, qubits, one-way hash function; Private keys: angle of rotation, Public keys: string of rotated quantum states.
    1. Requires random number generator, one-way hash function, quantum memory, key distribution.
    2. Security: Computational
  • Experimental Papers
  1. Clarke et al (2012) uses phase encoded coherent states, coherent state comparison
    1. Loss from multiport=7.5 dB, Length of the key= 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 10^6}

References[edit]

  1. Burhman et al (2001)
  2. Nielsen M. A. and Chuang I. L. Quantum computation and quantum information. Cambridge University Press, Cambridge, UK, 2000.
*contributed by Shraddha Singh
Retrieved from "https://wiki.veriqloud.fr/index.php?title=Gottesman_and_Chuang_Quantum_Digital_Signature&oldid=4501"