Abstract
We construct a public-key cryptosystem based on an NP-complete problem in algebraic geometry. It is a problem of finding sections on fibered algebraic surfaces; in other words, we use a solution to a system of multivariate equations of high degrees. Our cryptosystem is a revised version of the algebraic surface cryptosystem (ASC) we constructed earlier (cf. [AG04, AG06]). We revise its encryption algorithm to avoid known attacks. Further, we show that the key size of our cryptosystem is one of the shortest among those of post-quantum public-key cryptosystems known at present.
The original version of this chapter was revised: The copyright line was incorrect. This has been corrected. The Erratum to this chapter is available at DOI: 10.1007/978-3-642-00468-1_29
Chapter PDF
Similar content being viewed by others
References
Akiyama, K., Goto, Y.: An Algebraic Surface Public-key Cryptosystem. IEICE Tech. Report, vol. 104(421), pp. 13–20 (2004)
Akiyama, K., Goto, Y.: A Public-key Cryptosystem using Algebraic Surfaces. In: Proc. of PQCrypto 2006, pp. 119–138 (2006)
Akiyama, K., Goto, Y.: An improvement of the algebraic surface public-key cryptosystem. In: Proc. of SCIS 2008, CD-ROM 1F1-2 (2008)
Faugère, J.-C., Joux, A.: Algebraic cryptanalysis of hidden field equation (HFE) cryptosystems using gröbner bases. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 44–60. Springer, Heidelberg (2003)
Iwami, M.: A Reduction Attack on Algebraic Surface Public-Key Cryptosystems. In: Kapur, D. (ed.) ASCM 2007. LNCS, vol. 5081, pp. 323–332. Springer, Heidelberg (2008)
Koblitz, N.: Algebraic Aspects of Cryptography. Springer, Heidelberg (1998)
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)
Uchiyama, S., Tokunaga, H.: On the Security of the Algebraic Surface Public-key Cryptosystems (in Japanese). In: Proc. of SCIS 2007, CD-ROM 2C1-2,(2007)
Voloch, F.: Breaking the Akiyama-Goto algebraic surface cryptosystem. Arithmetic, Geometry, Cryptography and Coding Theory, CIRM meeting (2007)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, New York (1979)
Szpiro, L.: Seminaire sur les pinceaux de courbes de genre au moins deux. Asterisque 86(3), 44–78 (1981)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Akiyama, K., Goto, Y., Miyake, H. (2009). An Algebraic Surface Cryptosystem. In: Jarecki, S., Tsudik, G. (eds) Public Key Cryptography – PKC 2009. PKC 2009. Lecture Notes in Computer Science, vol 5443. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-00468-1_24
Download citation
DOI: https://doi.org/10.1007/978-3-642-00468-1_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-00467-4
Online ISBN: 978-3-642-00468-1
eBook Packages: Computer ScienceComputer Science (R0)