Editing Gottesman and Chuang Quantum Digital Signature
Jump to navigation
Jump to search
The edit can be undone. Please check the comparison below to verify that this is what you want to do, and then publish the changes below to finish undoing the edit.
Latest revision | Your text | ||
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. | 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, using quantum memory. It comes with all the [[Quantum Digital Signature#Properties|Properties]] of QDS. Such protocols require parties to store quantum states for comparison at a later stage. <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)]] | '''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]] | [[Category:Multi Party Protocols]][[Category:Quantum Enhanced Classical Functionality]][[Category:Specific Task]] | ||
Line 7: | Line 7: | ||
* It has been assumed that all recipients have received correct and identical copies of Seller's public key (explained later) | * 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>) | * 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>) | ||
==Outline== | ==Outline== | ||
Gottesman and Chuang signature scheme is based on quantum [https://en.wikipedia.org/wiki/One-way_function one way functions], which take classical bit string as input and give quantum states as output. Quantum Digital Signature (QDS) protocols can be divided 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. | |||
*''' | *'''Distribution:''' For each message bit (say 0 and 1) seller selects some (say M) classical bit strings. 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 function and key distribution method by the authors. | ||
'''Quantum One Way Functions:''' The author suggests [[ | ** '''Quantum One Way Functions:''' The author suggests [[quantum fingerprint states]], [[stabilizer states]] 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 | ** '''Key Distribution:''' The author suggests 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 [[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 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. | ||
*'''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. | *'''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. | ||
Line 23: | Line 21: | ||
* M: number of private keys chosen/produced for each message bit | * M: number of private keys chosen/produced for each message bit | ||
* k: classical string/ private key | * k: classical string/ private key | ||
* <math>|f_k\rangle</math>: quantum output of quantum one way function (public key) | |||
* <math>| | |||
* L: length of private key | * L: length of private key | ||
* n: number of qubits in the quanutm state <math>|f_k\rangle</math> | * n: number of qubits in the quanutm state <math>|f_k\rangle</math> | ||
* <math>c_1</math>: threshold for acceptance | * <math>c_1</math>: threshold for acceptance | ||
* <math>c_2</math>: threshold for rejection | * <math>c_2</math>: threshold for rejection | ||
Line 48: | Line 44: | ||
*'''Benchmark values:''' No experimental implementation using qubits. See [[Gottesman and Chuang Quantum Digital Signature#Further Information|Experimental Papers (1)]] for implementation using coherent states. | *'''Benchmark values:''' No experimental implementation using qubits. See [[Gottesman and Chuang Quantum Digital Signature#Further Information|Experimental Papers (1)]] for implementation using coherent states. | ||
== | ==Pseudocode== | ||
==Pseudocode== | |||
== | |||
<u>'''Stage 1'''</u> Distribution | <u>'''Stage 1'''</u> Distribution | ||
*'''Input''' L | *'''Input''' L | ||
*'''Output''' Seller: <math>\{k_0^i, k_1^i\}</math>, <math>1\le i\ | *'''Output''' Seller: <math>\{k_0^i, k_1^i\}</math>, <math>1\le i\ge M</math>, <math>\{f_{k_0^i}, f_{k_1^i}\}</math> | ||
**'''Key | **'''Key Distribution:''' | ||
#For | #For k = 0,1 | ||
##For i=0,M | ##For i=0,M | ||
### | ##Seller | ||
## | **'''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> | ||
#For | |||
## | **'''Symmetrisation''' | ||
### | ##For k = 0,1 | ||
### Buyer chooses I<math>\subset_R\{1,2,...,L\}, |I|=[L/2]</math> | |||
### | ### <math>\forall i\epsilon I</math>, Buyer sends Verifier <math>(k,i,b^k_i,B^k_i)</math> | ||
### | ### Verifier chooses J<math>\subset_R\{1,2,...,L\}, |J|=[L/2]</math> | ||
### | ### <math>\forall j\epsilon J</math>, Verifier sends Buyer <math>(k,j,v^k_j,V^k_j)</math> | ||
### | ### <math>\forall j\epsilon J</math> Buyer replaces <math>B^k_l=V^k_l</math> | ||
### <math>\forall i\epsilon I</math> Verifier replaces <math>V^k_l=B^k_l</math> | |||
<u>'''Stage 2'''</u> Messaging | <u>'''Stage 2'''</u> Messaging | ||
*'''Input''' Seller: Message | *'''Input''' Seller: Message m, Private Key for m: <math>\{\beta^m_1,...,\beta^m_L\}</math> | ||
*'''Output''' Buyer: | *'''Output''' Buyer: accept or abort, Verifier: accept or abort | ||
**'''Signing:''' | **'''Signing:''' ’mismatch’ is when Buyer finds an eliminated signature element in Seller’s private key | ||
# Seller sends Buyer (m,<math>\{\beta^m_1,...,\beta^m_L\}</math>) | |||
# Seller sends Buyer ( | |||
# For l = 1,2,..,L | # For l = 1,2,..,L | ||
## Buyer | ##Buyer counts the number of mismatches (<math>B^m_l=V^m_l</math>) and returns <math>S_b</math> | ||
# | # If <math>S_b < s_aL/2</math>, Buyer accepts m else he aborts | ||
# | **'''Transfer''' | ||
# Buyer sends Verifier (m,<math>\{\beta^m_1,...,\beta^m_L\}</math>) | |||
#If <math> | # For l = 1,2,....,L | ||
##Verifier counts the number of mismatches (<math>V^m_l=B^m_l</math>) and returns <math>S_v</math> | |||
# If <math>S_v < s_vL/2</math>, Verifier accepts m else he aborts | |||
==Further Information== | ==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.. | 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. | Following is the list of a 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/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. | #[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]]. | ##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]] | ##Security: [[Information-theoretic]] | ||
#[https://www.sciencedirect.com/science/article/pii/S0030402617308069 | #[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. | ##'''Requires''' [[random number generator]], [[one-way hash function]], quantum memory, key distribution. | ||
##'''Security:''' [[Computational]] | ##'''Security:''' [[Computational]] | ||
'''Experimental Papers''' | |||
#[https://www.nature.com/articles/ncomms2172 | #[https://www.nature.com/articles/ncomms2172 CCDAJB (2012)] uses phase encoded coherent states, [[coherent state comparison]] | ||
##Loss from multiport=7.5 dB, Length of the key= <math>10^6</math> | ##Loss from multiport=7.5 dB, Length of the key= <math>10^6</math> | ||
<div style='text-align: right;'>''*contributed by Shraddha Singh''</div> | <div style='text-align: right;'>''*contributed by Shraddha Singh''</div> |