Top

Published in:

2020 | OriginalPaper | Chapter

CSH: A Post-quantum Secret Handshake Scheme from Coding Theory

Authors : Zhuoran Zhang, Fangguo Zhang, Haibo Tian

Published in: Computer Security – ESORICS 2020

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In secret handshake schemes, the members in the same organization can anonymously authenticate each other and commonly negotiate a secret key for communication. Since its proposing in 2003, secret handshake schemes become an important privacy protection cryptographic technique on internet applications. In this paper, a secret handshake scheme based on coding theory (we call \(\mathsf {CSH}\)) is presented. This is the first code-based secret handshake scheme. \(\mathsf {CSH}\) is constructed by combining the CFS signature system and Stern’s identification system, thus the security of \(\mathsf {CSH}\) relies on the syndrome decoding problem just like the two above systems. Moreover, as far as we know, \(\mathsf {CSH}\) is the first scheme to use a generic construction of Fiat-Shamir paradigm in secret handshake schemes. This may lead to a more generic framework construction.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Towards Post-Quantum Security for Cyber-Physical Systems: Integrating PQC into Industrial M2M Communication

next chapter A Verifiable and Practical Lattice-Based Decryption Mix Net with External Auditing

Ateniese, G., Kirsch, J., Blanton, M.: Secret handshakes with dynamic and fuzzy matching. In: Network and Distributed System Security Symposium, NDSS 2007, pp. 783–788. The Internet Society (2007)

Balfanz, D., Durfee, G., Shankar, N., Smetters, D., Staddon, J., Wong, H.: Secret handshakes from pairing-based key agreements. In: IEEE Symposium on Security and Privacy 2003, pp. 180–196. IEEE (2003)

Becker, A., Joux, A., May, A., Meurer, A.: Decoding random binary linear codes in 2\(^{\mathit{n}/20}\): how 1 + 1 = 0 improves information set decoding. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 520–536. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29011-4_31CrossRefMATH

Berlekamp, E., McEliece, R., van Tilborg, H.: On the inherent intractability of certain coding problems. IEEE Trans. Inf. Theory 24(3), 384–386 (1978)MathSciNetCrossRef

Cayrel, P.-L., Véron, P., El Yousfi Alaoui, S.M.: A zero-knowledge identification scheme based on the q-ary syndrome decoding problem. In: Biryukov, A., Gong, G., Stinson, D.R. (eds.) SAC 2010. LNCS, vol. 6544, pp. 171–186. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-19574-7_12CrossRef

Castelluccia, C., Jarecki, S., Tsudik, G.: Secret handshakes from CA-oblivious encryption. In: Lee, P.J. (ed.) ASIACRYPT 2004. LNCS, vol. 3329, pp. 293–307. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-30539-2_21CrossRef

Courtois, N.T., Finiasz, M., Sendrier, N.: How to achieve a McEliece-based digital signature scheme. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 157–174. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-45682-1_10CrossRef

Dallot, L.: Towards a concrete security proof of Courtois, Finiasz and Sendrier signature scheme. In: Lucks, S., Sadeghi, A.-R., Wolf, C. (eds.) WEWoRC 2007. LNCS, vol. 4945, pp. 65–77. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-88353-1_6CrossRef

Faugère, J., Gauthier-Umaña, V., Otmani, A., Perret, L., Tillich, J.: A distinguisher for high-rate McEliece cryptosystems. IEEE Trans. Inf. Theory 59(10), 6830–6844 (2013)MathSciNetCrossRef

10.

Fiat, A., Shamir, A.: How to prove yourself: practical solutions to identification and signature problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186–194. Springer, Heidelberg (1987). https://doi.org/10.1007/3-540-47721-7_12CrossRef

11.

Finiasz, M.: Parallel-CFS. In: Biryukov, A., Gong, G., Stinson, D.R. (eds.) SAC 2010. LNCS, vol. 6544, pp. 159–170. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-19574-7_11CrossRef

12.

Gaborit, P., Girault, M.: Lightweight code-based identification and signature. In: ISIT 2007, pp. 191–195. IEEE (2007)

13.

Gu, J., Xue, Z.: An improved efficient secret handshakes scheme with unlinkability. IEEE Commun. Lett. 15(2), 259–261 (2011)CrossRef

14.

Huang, H., Cao, Z.: A novel and efficient unlinkable secret handshake scheme. IEEE Commun. Lett. 13(5), 363–365 (2009)CrossRef

15.

Jarecki, S., Kim, J., Tsudik, G.: Beyond secret handshakes: affiliation-hiding authenticated key exchange. In: Malkin, T. (ed.) CT-RSA 2008. LNCS, vol. 4964, pp. 352–369. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-79263-5_23CrossRef

16.

Li, S., Ephremides, A.: Anonymous routing: a cross-layer coupling between application and network layer. In: 2006 40th Annual Conference on Information Sciences and Systems, pp. 783–788. IEEE (2006)

17.

Massey, J.: Shift-register synthesis and BCH decoding. IEEE Trans. Inf. Theory 15(1), 122–127 (1969)MathSciNetCrossRef

18.

May, A., Meurer, A., Thomae, E.: Decoding random linear codes in \(\tilde{\cal{O}}(2^{0.054n})\). In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 107–124. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25385-0_6CrossRefMATH

19.

May, A., Ozerov, I.: On computing nearest neighbors with applications to decoding of binary linear codes. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 203–228. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46800-5_9CrossRef

20.

Mceliece, R.J.: A public-key cryptosystem based on algebraic coding theory. DSN Progress report 42-44, pp. 114–116 (1978)

21.

Niederreiter, H.: Knapsack-type cryptosystems and algebraic coding theory. Prob. Control Inf. Theory 15(2), 159–166 (1986)MathSciNetMATH

22.

Sakai, R., Ohgishi, K., Kasahara, M.: Cryptosystems based on pairings. In: Symposium on Cryptography and Information Security, SCIS 2000 (2000)

23.

Shor, P.: Algorithms for quantum computation: discrete logarithms and factoring. In: FOCS 1994, pp. 124–134. IEEE (1994)

24.

Stern, J.: A new identification scheme based on syndrome decoding. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 13–21. Springer, Heidelberg (1994). https://doi.org/10.1007/3-540-48329-2_2CrossRef

25.

Stern, J.: A new paradigm for public key identification. IEEE Trans. Inf. Theory 42(6), 1757–1768 (1996)MathSciNetCrossRef

26.

Vergnaud, D.: RSA-based secret handshakes. In: Ytrehus, Ø. (ed.) WCC 2005. LNCS, vol. 3969, pp. 252–274. Springer, Heidelberg (2006). https://doi.org/10.1007/11779360_21CrossRef

27.

Wagner, D.: A generalized birthday problem. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 288–304. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45708-9_19CrossRef

28.

Wen, Y., Zhang, F.: Delegatable secret handshake scheme. J. Syst. Softw. 84(12), 2284–2292 (2011)CrossRef

29.

Wen, Y., Zhang, F., Xu, L.: Secret handshakes from ID-based message recovery signature: a new generic approach. Comput. Electr. Eng. 38(1), 96–104 (2012)CrossRef

30.

Xu, S., Yung, M.: K-anonymous secret handshakes with reusable credentials. In: CCS 2004, pp. 158–167. ACM (2004)

31.

Zhou, L., Susilo, W., Mu, Y.: Three-round secret handshakes based on ElGamal and DSA. In: Chen, K., Deng, R., Lai, X., Zhou, J. (eds.) ISPEC 2006. LNCS, vol. 3903, pp. 332–342. Springer, Heidelberg (2006). https://doi.org/10.1007/11689522_31CrossRef

Title: CSH: A Post-quantum Secret Handshake Scheme from Coding Theory
Authors: Zhuoran Zhang
Fangguo Zhang
Haibo Tian
Publisher: Springer International Publishing
Book: Computer Security – ESORICS 2020
Print ISBN: 978-3-030-59012-3

Electronic ISBN: 978-3-030-59013-0

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-59013-0_16

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner