[go: up one dir, main page]
Skip to main content

Advertisement

Springer Nature Link
Log in

Efficient arbitrated quantum signature and its proof of security

  • Published:
Quantum Information Processing Aims and scope Submit manuscript

Abstract

In this paper, an efficient arbitrated quantum signature scheme is proposed by combining quantum cryptographic techniques and some ideas in classical cryptography. In the presented scheme, the signatory and the receiver can share a long-term secret key with the arbitrator by utilizing the key together with a random number. While in previous quantum signature schemes, the key shared between the signatory and the arbitrator or between the receiver and the arbitrator could be used only once, and thus each time when a signatory needs to sign, the signatory and the receiver have to obtain a new key shared with the arbitrator through a quantum key distribution protocol. Detailed theoretical analysis shows that the proposed scheme is efficient and provably secure.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Wiesner, S.: Conjugate coding. SIGACT News 15, 78–88 (1983)

    Article  Google Scholar 

  2. Bennett, C.H., Brassard, G.: Quantum cryptography: public key distribution and coin tossing. In: Proceedings of the IEEE International Conference on Computers Systems and, Signal Processing, pp. 175–179 (1984)

  3. Ekert, A.: Quantum cryptography based on Bell’s theorem. Phys. Rev. Lett. 67, 661–664 (1991)

    Article  MathSciNet  ADS  MATH  Google Scholar 

  4. Bennett, C.H.: Quantum cryptography using any two nonorthogonal states. Phys. Rev. Lett. 68, 3121–3124 (1992)

    Article  MathSciNet  ADS  MATH  Google Scholar 

  5. Hillery, M., Buzek, V.: Quantum secret sharing. Phys. Rev. A 59, 1829–1834 (1999)

    Article  MathSciNet  ADS  Google Scholar 

  6. Karlsson, A., Koashi, M., Imoto, N.: Quantum entanglement for secret sharing and secret splitting. Phys. Rev. A 59, 162–168 (1999)

    Article  ADS  Google Scholar 

  7. Li, Q., Long, D.Y., Chan, W.H., Qiu, D.W.: Sharing a quantum secret without a trusted party. Quantum Inf. Process. 10, 97–106 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  8. Barnum, H., Crepeau, C., Gottesman, D., Smith, A., Tapp, A.: Authentication of quantum messages. In: Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, pp. 449–458 (2002)

  9. Lo, H.K., Chau, H.F.: Is quantum bit commitment really possible? Phys. Rev. Lett. 78, 3410–3413 (1997)

    Article  ADS  Google Scholar 

  10. Mayers, D.: Unconditionally secure quantum bit commitment is impossible. Phys. Rev. Lett. 78, 3414–3417 (1997)

    Article  ADS  Google Scholar 

  11. Deng, F.G., Long, G.L.: Secure direct communication with a quantum one-time pad. Phys. Rev. A 69, article no. 052319 (2004)

    Google Scholar 

  12. Gottesman, D., Chuang, I.L.: Quantum digital signatures (2001) ArXiv:quant-ph/0105032

  13. Zeng, G.H., Keitel, C.H.: Arbitrated quantum-signature scheme. Phys. Rev. A 65, article no. 042312 (2002)

    Google Scholar 

  14. Li, Q., Chan, W.H., Long, D.Y.: Arbitrated quantum signature scheme using Bell states. Phys. Rev. A 79, article no. 054307 (2009)

    Google Scholar 

  15. Zou, X.F., Qiu, D.: Security analysis and improvements of arbitrated quantum signature schemes. Phys. Rev. A 82, article no. 042325 (2010)

    Google Scholar 

  16. Lee, H., Hong, C., Kim, H., Lim, J., Yang, H.J.: Arbitrated quantum signature scheme with message recovery. Phys. Lett. A 321, 295–300 (2004)

    Article  MathSciNet  ADS  MATH  Google Scholar 

  17. Lü, X., Feng, D.G.: An arbitrated quantum message signature scheme. In: Proceedings of the 1st International Symposium on Computational and Information Science, pp. 1054–1060 (2004)

  18. Lü, X., Feng, D.G.: Quantum digital signature based on quantum one-way functions. In: Proceedings of the 7th International Conference on Advanced Communication Technology, pp. 514–517 (2005)

  19. Wang, J., Zhang, Q., Tang, C.J.: Quantum signature scheme with message recovery. In: Proceedings of the 8th International Conference on Advanced Communication Technology, pp. 1375–1378 (2006)

  20. Wang, J., Zhang, Q., Tang, C.J.: Efficient quantum signature protocol of classical messages. J. Commun. 28, 64–68 (2007) (In Chinese)

    Google Scholar 

  21. Lo, H.K., Chau, H.F.: Unconditional security of quantum key distribution over arbitrarily long distances. Science 283, 2050–2056 (1999)

    Article  ADS  Google Scholar 

  22. Shor, P.W., Preskill, J.: Simple proof of security of the BB84 quantum key distribution protocol. Phys. Rev. Lett. 85, 441–444 (2000)

    Article  ADS  Google Scholar 

  23. Inamori, H., Lutkenhaus, N., Mayers, D.: Unconditional security of practical quantum key distribution. Eur. Phys. J. D 41, 599–627 (2007)

    Article  ADS  Google Scholar 

  24. Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, pp. 124–134 (1994)

  25. Wang, J., Zhang, Q., Liang, L.M., Tang, C.J.: Comment on: “Arbitrated quantum signature scheme with message recovery”. Phys. Lett. A 347, 262–263 (2005)

    Article  ADS  Google Scholar 

  26. Li, Q., Du, R.G., Long, D.Y., Wang, C.J., Chan, W.H.: Entanglement enhances the security of arbitrated quantum signature. Int. J. Quantum Inf. 7, 913–925 (2009)

    Article  MATH  Google Scholar 

  27. Zeng, G.H., Lee, M., Guo, Y., He, G.Q.: Continuous variable quantum signature algorithm. Int. J. Quantum Inf. 5, 553–573 (2007)

    Article  MATH  Google Scholar 

  28. Wen, X.J., Liu, Y., Sun, Y.: Quantum multi-signature protocol based on teleportation. Z Naturforsch A: Phys. Sci. 62, 147–151 (2007)

    MATH  Google Scholar 

  29. Yang, Y.G., Wen, Q.Y.: Quantum threshold group signature. Sci. China Ser. G-Phys. Mech. Astron. 38, 1162 (2008) (In Chinese)

    Google Scholar 

  30. Yang, Y.G., Zhou, Z., Teng, Y.W., Wen, Q.Y.: Arbitrated quantum signature with an untrusted arbitrator. Eur. Phys. J. D 61, 773–778 (2011)

    Article  ADS  Google Scholar 

  31. Gao, F., Qin, S.J., Guo, F.Z., Wen, Q.Y.: Cryptanalysis of the arbitrated quantum signature protocols. Phys. Rev. A 84, article no. 022344 (2011)

  32. Choi, J.W., Chang, K.Y., Hong, D.: Security problem on arbitrated quantum signature schemes. Phys. Rev. A 84, article no. 062330 (2011)

  33. Hwang, T., Lee, K.C., Li, C.M.: Provably secure three-party authenticated quantum key distribution protocols. IEEE Trans. Dependable Secur. Comput. 4, 71–80 (2007)

    Article  Google Scholar 

  34. Wootters, W.K., Zurek, W.H.: A single quantum cannot be cloned. Nature 299, 802–803 (1982)

    Article  ADS  Google Scholar 

  35. Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Higher Education, Beijing (2003)

  36. Bellare, M., Rogaway, P.: In: Proceedings of the 27th ACM Symposium on Theory of Computing, pp. 57–66 (1995)

  37. Pointcheval, D., Stern, J.: Security proofs for signature schemes. In: Maurer, U.M. (ed.) Advances in Cryptology-Eurocrypt’96, Lecture Notes in Computer Science, vol. 1070, pp. 387–398. Springer, Berlin (1996)

  38. Bellare, M., Canetti, R., Krawczyk, H.: Keying hash functions for message authentication. In: Koblitz, N. (ed.) Advances in Cryptology-Crypto’96, Lecture Notes in Computer Science, vol. 1109, pp. 1–15. Springer, Berlin (1996)

  39. Goldwasser, S., Micali, S., Rivest, R.: A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Comput. 17, 281–308 (1988)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

We thank the anonymous reviewers for their constructive comments that are helpful for the improvement of the paper. This work was supported by National Natural Science Foundation of China (Grant Nos. 61202398, 61100216, and 61105052), Scientific Research Fund of Hunan Provincial Education Department (Grant No. 12C0400), and Science Fund of Xiangtan University (Grant No. 2011XZX16). The work of Wai Hong Chan is partially supported by Internal Research Grant at The Hong Kong Institute of Education (Grant No. RG 66/2011-2012).

Author information

Authors and Affiliations

  1. College of Information Engineering, Xiangtan University, Xiangtan, 411105, Hunan, China

    Qin Li & Chengqing Li

  2. Key Laboratory of Intelligent Computing and Information Processing of the Ministry of Education, Xiangtan University, Xiangtan, China

    Qin Li & Chengqing Li

  3. Department of Computer Science, Sun Yat-sen University, Guangzhou, 510006, China

    Dongyang Long & Changji Wang

  4. Department of Mathematics and Information Technology, The Hong Kong Institute of Education, Tai Po, Hong Kong

    Wai Hong Chan

Authors
  1. Qin Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Chengqing Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Dongyang Long
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Wai Hong Chan
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Changji Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Qin Li.

Appendix

Appendix

Here we give the proof of Theorem 1.

Theorem 1 If the keyed hash function \(h\) is \((\varepsilon ^{\prime }, t^{\prime }, q,l)\) -weakly collision-resistant, then the proposed QS scheme is an \((\varepsilon , t, q_{sig},q_h)\) -secure QS scheme. And \(\varepsilon , \varepsilon ^{\prime }, t\), and \(t^{\prime }\) meet the following relation

$$\begin{aligned} \left(1-\left(\frac{1}{2}\right)^{l+n}\right)\cdot \varepsilon \cdot \frac{1}{q_{sig}+q_h} \le \varepsilon ^{\prime }, \end{aligned}$$

where \(q \le q_{sig}+q_h, t^{\prime } \le t + q\cdot T_{rn}; T_{rn}\) is the time to generate a random number.

Proof

Assume an adversary \(E\) who is restricted to make signature queries for at most \(q_{sig}\) times and hash queries up to \(q_h\) times, has potential to produce a valid signature of a message without being asked with probability greater than \(\varepsilon \) in the time bound \(t\), then we can prove that a challenger \(C\) can break the weak collision resistance property of \(h\) with probability larger than \(\varepsilon ^{\prime }\) within \(t^{\prime }\) using this event, which is in contradict with that \(h\) is a \((\varepsilon ^{\prime },t^{\prime },q,l)\)-weakly collision-resistant hash function.

Let the length of binary string \(M\) be \(l+n\). The target of \(C\) is to find a different binary string \(M^{\prime }\) which makes \(h(M^{\prime })=h(M)\).

  • Set up: \(C\) lets \(K_{UT}\) be the shared key between \(U\) and \(T\), chooses a random number \(r(1\le r \le q_h+q_{sig})\), and sets the counter \(c = 0\).

  • Hash queries: \(E\) asks the value of \(h\) when inputting \(P_j\). In order to respond to \(E\)’s queries, \(C\) has to keep a hash table in which each element is a triad \((P_j,r_j,w_j)\) and the number of elements before running the procedure is 0. At some time when \(E\) begins to request the value of \(h\) corresponding to the input \(P_j, C\) increases the counter \(c\) by 1 and makes different responses as follows:

    • If \(c<r , C\) chooses a random number \(r_j\), and sends \(r_j\) and \(P_j\) queried by \(E\) to oracle \(h\). \(h\) returns \(h(r_j,P_j)\) as a response. \(C\) keeps \((P_j,r_j,w_j) \) in the hash table and then forwards \(w_j\) to \(E\).

    • If \(c=r, C\) guesses that \(E\) may attempt to attack the QS scheme at the moment, so he sends \(M\) to \(h\). \(h\) responds by offering \(w_j=h(M) \) to \(C\). The triad \((P_j,r_j,w_j)\) is saved in the hash table and \(w_j\) is forwarded to \(E\).

    • Otherwise, C loses the game and stops the currently running procedure.

  • Signature queries: \(E\) asks the signature of message \(P_j\). \(C\) sets \(c=c+1\) and makes different responses according to whether the corresponding triad \((P_j,r_j,w_j)\) is in the hash table:

    • If \((P_j,r_j,w_j)\) is in the hash table and \(c\ne r, C\) returns the signature \(|S_j\rangle \) of message \(P_j\) in light of \(r_j, w_j, U\), and \(K_{UT}\).

    • If \((P_j,r_j,w_j)\) is in the hash table and \(c = r, C\) fails and terminates the implementation.

    • If \((P_j,r_j,w_j)\) is not in the hash table, \(C\) runs the procedure for hash query to obtain \(w_j=h(r_j,P_j) \), and keep \((P_j,r_j,w_j)\) in the hash table. If \(c = r, C\) announces failure and puts an end to the procedure, else responds \(E\) with the signature \(|S_j\rangle \) of message \(P_j\) according to \(r_j, w_j, U\), and \(K_{UT}\).

  • Output: \(E\) outputs a message-signature pair \((P_i,|S_i\rangle )\) and the signature query for \(P_i\) has not been made before. \(C\) checks whether \((P_i,r_i,w_i)\) has been in the hash table. If not, \(C\) makes a hash query procedure and adds the corresponding element to the hash table. If \(c\ne r, C\) fails and terminates the procedure; else measures \(|S_i\rangle \) to get \(r_i^{\prime }||R_i^{\prime }\) depending on \(K_{UT}\). If the signature \(|S_i\rangle \) is valid, then

    $$\begin{aligned} w_i ||U= \left(Truc_l (K)\oplus r_A^{\prime }\right)\oplus R_A^{\prime }, \end{aligned}$$

    and

    $$\begin{aligned} w_i = h\left(r_i^{\prime }, P_i\right)= h(M). \end{aligned}$$

    So \(C\) can output \(r_i^{\prime }||P_i \). If \(|S_i\rangle \) is invalid, \(C\) loses the game and stops the procedure.

Assume \(E\) outputs a valid message-signature pair \((P_i,|S_i\rangle ) \). Then if \(C\) wants to succeed in find collisions, the following three conditions should be satisfied at the same time.

  • Condition 1 \((C1)\): when \(c=r, E\) makes a hash query instead of a signature query;

  • Condition 2 \((C2)\): the finally outputted message \(P_i\) should be queried when \(c=r\);

  • Condition 3 \((C3)\): the output of \(C r_i^{\prime }||P_i \) is not equal to \(M\).

The probability that \(C1\) holds is \(P(C1)\ge \frac{q_h}{q_{sig}+q_h}\) and the conditional probability \(P(C2|C1)\ge \frac{1}{q_h}\) since \(E\) may make illegal queries. In addition, due to the randomness of \(r_i^{\prime }\) and \(P_i\), so \(P(C3|C1, C2)\approx 1-(\frac{1}{2})^{l+n} \). Therefore,

$$\begin{aligned}&\frac{q_h}{q_{sig}+q_h}\cdot \frac{1}{q_h}\cdot \left(1-\left(\frac{1}{2}\right)^{l+n}\right) \cdot \varepsilon \\&= \left(1-\left(\frac{1}{2}\right)^{l+n}\right)\cdot \varepsilon \cdot \frac{1}{q_{sig}+q_h}\\&\le \varepsilon ^{\prime }, \end{aligned}$$

where \(q \le q_{sig}+q_h, t^{\prime } \le t + q\cdot T_{rn} , T_{rn} \) is the time to generate a random number.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Li, Q., Li, C., Long, D. et al. Efficient arbitrated quantum signature and its proof of security. Quantum Inf Process 12, 2427–2439 (2013). https://doi.org/10.1007/s11128-013-0538-4

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11128-013-0538-4

Keywords