Quantum Digital Signature: Difference between revisions

From Quantum Protocol Zoo
Jump to navigation Jump to search
No edit summary
 
(64 intermediate revisions by 4 users not shown)
Line 1: Line 1:
==Functionality==
==Functionality==
Digital Signatures (DS) allow for the exchange of single or multiple bit classical messages from sender to multiple recipients, with a guarantee that the signature has come from a genuine sender. 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.
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 [[Quantum Digital Signature#Properties|transferability]], [[Quantum Digital Signature#Properties|non-repudiation]] and [[Quantum Digital Signature#Properties|unforgeability]]. In contrast, classical digital signatures rely on authentication (taken as an assumption for some QDS protocols) i.e. the message has come from the claimed party; integrity i.e. the message has not been altered (if authentication is confirmed, this property is unforgeability) and non-repudiation (same as QDS). These properties distinguish quantum digital signatures from [[Authentication of Quantum Messages|quantum authentication]]. Quantum messages can be authenticated but not signed [[Quantum Digital Signature#References|(1), (2)]]. Note that QDS schemes sign classical messages and not quantum messages. <br/>
==Protocols==
 
For simlicity, most protocols use the case of three parties, one sender (Seller) and two recipients (Buyer and Verifier) exchanging one-bit classical messages signed by Quantum Digital Signatures (QDS).  
'''Tags:'''  [[:Category: Multi Party Protocols|Multi Party (three)]],  [[:Category: Quantum Enhanced Classical Functionality|Quantum Enhanced Classical Functionality]],  [[:Category: Specific Task|Specific Task]]
[[Category: Multi Party Protocols]]  [[Category: Quantum Enhanced Classical Functionality]] [[Category:Specific Task]]


*[[Quantum Digital Signatures from quantum one-way function]]
==Use-cases==
*[[Prepare and Measure Quantum Digital Signature|Prepare and Measure Quantum Digital Signature]]
* Classical task
*[[Quantum Digital Signatures without quantum memory]]
* Classical analogue: RSA, Post-Quantum Secure analogue: XMSS
*[[Quantum Digital Signatures with insecure quantum channels]]
*QDS implementation specifications (best achieved) per half bit message (0 or 1):
*[[Quantum Digital Signatures for multiple-bit classical messages]]
** best estimated time: 3.5 secs
*[[Measurement Device Independent Quantum Digital Signature (MDI-QDS)]]
**key length: 2Mbits
*[[Blind Quantum Digital Signature]]
** maximum transmission distance: 200 kms
** scalability: linear in time, not linear in key length
* [[New threat models on authentication]]
* [[Cross-platform finance]]


==Use Case==
==Protocols==
Signing e-Marksheet, Financial Transactions, Software Distribution, Cryptocurrencies, e-voting


Tags: [[Multi Party Protocols|Multi Party]], [[Quantum Enhanced Classical Functionality]], [[Specific Task]]
*[[Gottesman and Chuang Quantum Digital Signature]]: [[:Category: Quantum Memory Network Stage|Quantum Memory Network Stage]]
*[[Prepare and Measure Quantum Digital Signature]]: [[:Category: Prepare and Measure Network Stage|Prepare and Measure Network Stage]]
*[[Measurement Device Independent Quantum Digital Signature (MDI-QDS)]]: [[:Category: Prepare and Measure Network Stage|Prepare and Measure Network Stage]]
*[[Arbitrated Quantum Digital Signature]]: [[:Category: Quantum Memory Network Stage|Quantum Memory Network Stage]]
Below are few signature protocols with slightly modified functionality but same properties and requirements.
*[[Blind Delegation of Quantum Digital Signature]]
*[[Designated Verifiable Quantum Signature]]
*[[Limited Delegation of Quantum Signature]]
*[[Quantum Proxy Signature]]


==Properties==
==Properties==
All QDS protocols are divided into two phases, distribution and messaging. Distribution phase enables sender to generate private keys (kept secret with sender) and public keys (distributed to recipients) while messaging phase enables exchange of messages using the above keys.
All QDS protocols are divided into two phases, distribution and messaging. Distribution phase enables sender to generate private keys (kept secret with sender) and public keys (information distributed to recipients) while messaging phase enables exchange of messages using the above keys. For simplicity, most protocols use the case of three parties, one sender (Seller) and two recipients (Buyer and Verifier) exchanging one-bit classical messages signed by Quantum Digital Signatures (QDS). 
 
*A QDS scheme is correct if a message signed by a genuine sender is accepted by a recipient with unit probability.
*A QDS scheme is correct if a message signed by a genuine sender is accepted by a recipient with unit probability.
*A QDS scheme is secure if no one but the sender can sign a message such that it is accepted by a recipient with non-negligible probability.  
*A QDS scheme is secure if no one but the sender can sign a message such that it is accepted by a recipient with non-negligible probability.  
Line 25: Line 37:
*'''Non-Repudiation''' implies that at any point a dishonest sender (seller) cannot deny having signed the message sent to a genuine recipient (Buyer).
*'''Non-Repudiation''' implies that at any point a dishonest sender (seller) cannot deny having signed the message sent to a genuine recipient (Buyer).


==Discussion==
==Further Information==
(Review Paper by Petros)
Unlike classical digital signature schemes which generalize a two party model, QDS protocols always study a three party model as transferability is not inherent and has to be proved in the quantum case. Given this situation, usually, the third party acts as the judge (a verififer) who would gain nothing out of cheating, and hence, cheating strategy is only studied for seller (repudiation) and buyer (forgery). Quantum digital signatures provide unconditional security, not relying on any computational assumption which is its basic advantage over the classical schemes. However, over time classical unconditionally secure digital signature schemes have been realized. These classical protocols take extra some assumptions like trusted omnipotent (one who distributes everyone signatures) or authenticated message broadcast. QDS does not require any such assumption. Yet, the low key rate could render QDS impractical over classical digital signature schemes. At the same time, there exist post quantum secure Digital signature schemes based on hash-key cryptography which cannot be broken by quantum computers.  Still, if someone requires a lifetime security without the above mentioned assumptions, QDS is the answer. Areas to improve QDS could be addressing the key rate and scalability of key length with length of message. Following are a few articles useful for those interested in a more detailed overview of QDS. 
 
==Knowledge Graph==
{{graph}}
 
*Review Papers
#[https://www.semanticscholar.org/paper/Unconditionally-Secure-Quantum-Signatures-Amiri-Andersson/2c9a298c9e902c5162496cc13f5d560427873412 AA (2015)] Discusses various classical and quantum digital signature schemes
#Wallden P. (2018) (In preparation): Discusses the development of Quantum Digital Signatures from the first protocol by Gottesman and Chuang, elaborating advancements in further protocols to turn it into a practical QDS scheme.
==References==
#[https://arxiv.org/abs/quant-ph/0205128 Barum et al (2002)] First intuition towards impossibility of signing quantum states
#[https://arxiv.org/abs/1302.4528 Li et al (2013)] Discusses the possibility of arbitrated Quantum Signature schemes for quantum signatures
#[https://eprint.iacr.org/2018/1164 Alagic et al (2018)] Impossibility result of signing quantum states established and the article rules out all weak schemes for quantum messages
 
 
<div style='text-align: right;'>''contributed by Shraddha Singh''</div>

Latest revision as of 17:54, 21 December 2020

Functionality[edit]

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 transferability, non-repudiation and unforgeability. In contrast, classical digital signatures rely on authentication (taken as an assumption for some QDS protocols) i.e. the message has come from the claimed party; integrity i.e. the message has not been altered (if authentication is confirmed, this property is unforgeability) and non-repudiation (same as QDS). These properties distinguish quantum digital signatures from quantum authentication. Quantum messages can be authenticated but not signed (1), (2). Note that QDS schemes sign classical messages and not quantum messages.

Tags: Multi Party (three), Quantum Enhanced Classical Functionality, Specific Task

Use-cases[edit]

  • Classical task
  • Classical analogue: RSA, Post-Quantum Secure analogue: XMSS
  • QDS implementation specifications (best achieved) per half bit message (0 or 1):
    • best estimated time: 3.5 secs
    • key length: 2Mbits
    • maximum transmission distance: 200 kms
    • scalability: linear in time, not linear in key length
  • New threat models on authentication
  • Cross-platform finance

Protocols[edit]

Below are few signature protocols with slightly modified functionality but same properties and requirements.

Properties[edit]

All QDS protocols are divided into two phases, distribution and messaging. Distribution phase enables sender to generate private keys (kept secret with sender) and public keys (information distributed to recipients) while messaging phase enables exchange of messages using the above keys. For simplicity, most protocols use the case of three parties, one sender (Seller) and two recipients (Buyer and Verifier) exchanging one-bit classical messages signed by Quantum Digital Signatures (QDS).

  • A QDS scheme is correct if a message signed by a genuine sender is accepted by a recipient with unit probability.
  • A QDS scheme is secure if no one but the sender can sign a message such that it is accepted by a recipient with non-negligible probability.
  • Transferability means that at any point a recipient (buyer) can prove it to another recipient (verifier) that the concerned message has been signed by the claimed sender (Seller).
  • Unforgeability ensures that a dishonest recipient (buyer) can neither alter a DS nor sign a message with a fake DS (DS that has not come from a genuine sender) and forward it to other recipients (verifier) successfully.
  • Non-Repudiation implies that at any point a dishonest sender (seller) cannot deny having signed the message sent to a genuine recipient (Buyer).

Further Information[edit]

Unlike classical digital signature schemes which generalize a two party model, QDS protocols always study a three party model as transferability is not inherent and has to be proved in the quantum case. Given this situation, usually, the third party acts as the judge (a verififer) who would gain nothing out of cheating, and hence, cheating strategy is only studied for seller (repudiation) and buyer (forgery). Quantum digital signatures provide unconditional security, not relying on any computational assumption which is its basic advantage over the classical schemes. However, over time classical unconditionally secure digital signature schemes have been realized. These classical protocols take extra some assumptions like trusted omnipotent (one who distributes everyone signatures) or authenticated message broadcast. QDS does not require any such assumption. Yet, the low key rate could render QDS impractical over classical digital signature schemes. At the same time, there exist post quantum secure Digital signature schemes based on hash-key cryptography which cannot be broken by quantum computers. Still, if someone requires a lifetime security without the above mentioned assumptions, QDS is the answer. Areas to improve QDS could be addressing the key rate and scalability of key length with length of message. Following are a few articles useful for those interested in a more detailed overview of QDS.

Knowledge Graph[edit]

  • Review Papers
  1. AA (2015) Discusses various classical and quantum digital signature schemes
  2. Wallden P. (2018) (In preparation): Discusses the development of Quantum Digital Signatures from the first protocol by Gottesman and Chuang, elaborating advancements in further protocols to turn it into a practical QDS scheme.

References[edit]

  1. Barum et al (2002) First intuition towards impossibility of signing quantum states
  2. Li et al (2013) Discusses the possibility of arbitrated Quantum Signature schemes for quantum signatures
  3. Alagic et al (2018) Impossibility result of signing quantum states established and the article rules out all weak schemes for quantum messages


contributed by Shraddha Singh