Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Cover of the book

2017 | OriginalPaper | Chapter

RingRainbow – An Efficient Multivariate Ring Signature Scheme

Authors : Mohamed Saied Emam Mohamed, Albrecht Petzoldt

Published in: Progress in Cryptology - AFRICACRYPT 2017

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

Multivariate Cryptography is one of the main candidates for creating post-quantum cryptosystems. Especially in the area of digital signatures, there exist many practical and secure multivariate schemes. However, there is a lack of more advanced schemes, such as schemes for oblivious transfer and signature schemes with special properties. While, in the last years, a number of multivariate ring signature schemes have been proposed, all of these have weaknesses in terms of security or efficiency. In this paper we propose a simple and efficient technique to extend arbitrary multivariate signature schemes to ring signature schemes and illustrate it using the example of Rainbow. The resulting scheme provides perfect anonymity for the signer (as member of a group), as well as shorter ring signatures than all previously proposed post-quantum ring signature schemes.

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
next chapter Pinocchio-Based Adaptive zk-SNARKs and Secure/Correct Adaptive Function Evaluation
Footnotes
1
Of course, the attacker could try to transform the given system of high degree into a quadratic one. However, even if the given system is very sparse, this increases the number of equations and variables in the quadratic system drastically. Furthermore, the ratio between the number of variables and the number of equations gets close to 1.
 
Literature
1.
Aguilar, C., Cayrel, P.L., Gaborit, P., Laguillaumie, F.: A new efficient threshold ring signature scheme based on coding theory. IEEE Trans. Inf. Theory 57(7), 4833–4842 (2011)MathSciNetCrossRef
2.
Asaar, M.R., Salmasizadeh, M., Susilo, W.: A short identity-based proxy ring signature scheme from RSA. Comput. Stand. Interfaces 38, 144–151 (2015)CrossRef
3.
Bender, A., Katz, J., Morselli, R.: Ring signatures: stronger definitions and constructions without random oracles. IACR eprint 2005/304
4.
Bernstein, D.J., Buchmann, J., Dahmen, E. (eds.): Post Quantum Cryptography. Springer, Heidelberg (2009)MATH
5.
Bogdanov, A., Eisenbarth, T., Rupp, A., Wolf, C.: Time-area optimized public-key engines: \(\cal{MQ}\)-cryptosystems as replacement for elliptic curves? In: Oswald, E., Rohatgi, P. (eds.) CHES 2008. LNCS, vol. 5154, pp. 45–61. Springer, Heidelberg (2008). doi:10.​1007/​978-3-540-85053-3_​4 CrossRef
6.
Chen, A.I.-T., Chen, M.-S., Chen, T.-R., Cheng, C.-M., Ding, J., Kuo, E.L.-H., Lee, F.Y.-S., Yang, B.-Y.: SSE implementation of multivariate PKCs on modern x86 CPUs. In: Clavier, C., Gaj, K. (eds.) CHES 2009. LNCS, vol. 5747, pp. 33–48. Springer, Heidelberg (2009). doi:10.​1007/​978-3-642-04138-9_​3 CrossRef
7.
Cayrel, P.-L., Lindner, R., Rückert, M., Silva, R.: A lattice-based threshold ring signature scheme. In: Abdalla, M., Barreto, P.S.L.M. (eds.) LATINCRYPT 2010. LNCS, vol. 6212, pp. 255–272. Springer, Heidelberg (2010). doi:10.​1007/​978-3-642-14712-8_​16 CrossRef
8.
Ding, J., Gower, J.E., Schmidt, D.S.: Multivariate Public Key Cryptosystems. Springer, USA (2006)MATH
9.
Ding, J., Schmidt, D.: Rainbow, a new multivariable polynomial signature scheme. In: Ioannidis, J., Keromytis, A., Yung, M. (eds.) ACNS 2005. LNCS, vol. 3531, pp. 164–175. Springer, Heidelberg (2005). doi:10.​1007/​11496137_​12 CrossRef
10.
11.
12.
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York (1979)MATH
13.
Kravitz, D.: Digital signature algorithm. US patent 5231668, July 1991
14.
Kipnis, A., Patarin, J., Goubin, L.: Unbalanced oil and vinegar signature schemes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 206–222. Springer, Heidelberg (1999). doi:10.​1007/​3-540-48910-X_​15
15.
Miura, H., Hashimoto, Y., Takagi, T.: Extended algorithm for solving underdefined multivariate quadratic equations. In: Gaborit, P. (ed.) PQCrypto 2013. LNCS, vol. 7932, pp. 118–135. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-38616-9_​8 CrossRef
16.
Petzoldt, A., Bulygin, S., Buchmann, J.: A multivariate based threshold ring signature scheme. Appl. Algebra Eng. Commun. Comput. 24(3–4), 255–275 (2012)MathSciNetMATH
17.
18.
Petzoldt, A., Bulygin, S., Buchmann, J.: CyclicRainbow – a multivariate signature scheme with a partially cyclic public key. In: Gong, G., Gupta, K.C. (eds.) INDOCRYPT 2010. LNCS, vol. 6498, pp. 33–48. Springer, Heidelberg (2010). doi:10.​1007/​978-3-642-17401-8_​4 CrossRef
19.
Petzoldt, A., Bulygin, S., Buchmann, J.: A multivariate threshold ring signature scheme. AAECC 25(3–4), 255–275 (2012)MATH
20.
Petzoldt, A., Bulygin, S., Buchmann, J.: Fast verification for improved versions of the UOV and rainbow signature schemes. In: Gaborit, P. (ed.) PQCrypto 2013. LNCS, vol. 7932, pp. 188–202. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-38616-9_​13 CrossRef
21.
Petzoldt, A., Chen, M.-S., Yang, B.-Y., Tao, C., Ding, J.: Design principles for HFEv-based multivariate signature schemes. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015. LNCS, vol. 9452, pp. 311–334. Springer, Heidelberg (2015). doi:10.​1007/​978-3-662-48797-6_​14 CrossRef
22.
Rivest, R.L., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21(2), 120–126 (1978)MathSciNetCrossRefMATH
23.
24.
Shor, P.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484–1509 (1997)MathSciNetCrossRefMATH
25.
Sakumoto, K., Shirai, T., Hiwatari, H.: Public-key identification schemes based on multivariate quadratic polynomials. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 706–723. Springer, Heidelberg (2011). doi:10.​1007/​978-3-642-22792-9_​40 CrossRef
26.
Thomae, E., Wolf, C.: Solving underdetermined systems of multivariate quadratic equations revisited. In: Fischlin, M., Buchmann, J., Manulis, M. (eds.) PKC 2012. LNCS, vol. 7293, pp. 156–171. Springer, Heidelberg (2012). doi:10.​1007/​978-3-642-30057-8_​10 CrossRef
27.
Wang, L.L.: A new multivariate-based ring signature scheme. In: Proceeedings of ISCCCA (2013)
28.
Wang, S., Ma, R., Zhang, Y., Wang, X.: Ring signature scheme based on multivariate public key cryptosystems. Comput. Math. Appl. 62, 3973–3979 (2011)MathSciNetCrossRefMATH
29.
Wang, S., Zhao, R.: Lattice-based ring signature scheme under the random oracle model (2014). CoRR abs/1405.3177
30.
Yang, B.-Y., Chen, J.-M., Chen, Y.-H.: TTS: high-speed signatures on a low-cost smart card. In: Joye, M., Quisquater, J.-J. (eds.) CHES 2004. LNCS, vol. 3156, pp. 371–385. Springer, Heidelberg (2004). doi:10.​1007/​978-3-540-28632-5_​27 CrossRef
31.
Zhang, J., Zhao, Y.: A new multivariate based threshold ring signature scheme. In: Au, M.H., Carminati, B., Kuo, C.-C.J. (eds.) NSS 2014. LNCS, vol. 8792, pp. 526–533. Springer, Cham (2014). doi:10.​1007/​978-3-319-11698-3_​42
Metadata
Title
RingRainbow – An Efficient Multivariate Ring Signature Scheme
Authors
Mohamed Saied Emam Mohamed
Albrecht Petzoldt
Copyright Year
2017
Book
Progress in Cryptology - AFRICACRYPT 2017

Print ISBN: 978-3-319-57338-0

Electronic ISBN: 978-3-319-57339-7

Copyright Year: 2017

DOI
https://doi.org/10.1007/978-3-319-57339-7_1

Premium Partner

    Image Credits