Abstract
Multivariate Public Key Cryptography (MPKC) is one of the main candidates for secure communication in a post-quantum era. Recently, Yasuda and Sakurai proposed in [8] a new multivariate encryption scheme called SRP, which is very efficient and resists all known attacks against multivariate schemes. However, the key sizes of the scheme are quite large. In this paper we propose a new strategy to reduce the key size of the SRP scheme, which enables us to reduce the size of the public key by up to \(54\,\%\). Furthermore, we can use the additional structure in the public key polynomials to speed up the encryption process of the scheme by up to \(50\,\%\). We show by experiments that our modifications do not weaken the security of the scheme.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
By increasing r, the probability of both \((y^{(1)}_1, \dots , y^{(1)}_d)\) and \((y^{(2)}_1, \dots , y^{(2)}_d)\) leading to a solution of the linear system can be reduced arbitrarily.
References
Billet, O., Gilbert, H.: Cryptanalysis of rainbow. In: De Prisco, R., Yung, M. (eds.) SCN 2006. LNCS, vol. 4116, pp. 336–347. Springer, Heidelberg (2006)
Duong, D.H., Petzoldt, A., Takagi, T.: Reducing the Key Size of the SRP Encryption Scheme - Extended Version. IACR eprint, https://eprint.iacr.org/2016/383.pdf
Clough, C., Baena, J., Ding, J., Yang, B.Y., Chen, M.S.: Square, a new multivariate encryption scheme. In: Fischlin, M. (ed.) CT-RSA 2009. LNCS, vol. 5473, pp. 252–264. Springer, Heidelberg (2009)
Ding, J., Gower, J.E., Schmidt, D.S.: Multivariate Public Key Cryptosystems. Advances in Information Security, vol. 25. Springer US, New York (2006)
Ding, J., Schmidt, D.: Rainbow, a new multivariable polynomial signature scheme. In: Ioannidis, J., Keromytis, A.D., Yung, M. (eds.) ACNS 2005. LNCS, vol. 3531, pp. 164–175. Springer, Heidelberg (2005)
Ding, J., Yang, B.Y., Chen, C.H.O., Chen, M.S., Cheng, C.M.: New differential-algebraic attacks and reparametrization of rainbow. In: Bellovin, S.M., Gennaro, R., Keromytis, A.D., Yung, M. (eds.) ACNS 2008. LNCS, vol. 5037, pp. 242–257. Springer, Heidelberg (2008)
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)
Yasuda, T., Sakurai, K.: A multivariate encryption scheme with rainbow. In: Qing, S., et al. (eds.) ICICS 2015. LNCS, vol. 9543, pp. 236–251. Springer, Heidelberg (2016). doi:10.1007/978-3-319-29814-6_19
Acknowledgements
This research is supported by JSPS KAKENHI no. 15F15350 and 16K17644.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Duong, D.H., Petzoldt, A., Takagi, T. (2016). Reducing the Key Size of the SRP Encryption Scheme. In: Liu, J., Steinfeld, R. (eds) Information Security and Privacy. ACISP 2016. Lecture Notes in Computer Science(), vol 9723. Springer, Cham. https://doi.org/10.1007/978-3-319-40367-0_27
Download citation
DOI: https://doi.org/10.1007/978-3-319-40367-0_27
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-40366-3
Online ISBN: 978-3-319-40367-0
eBook Packages: Computer ScienceComputer Science (R0)