Abstract
Solving a system of multivariate polynomials over a finite field is a promising problem in cryptography. Recently, Sakumoto et al. proposed public-key identification schemes based on the quadratic version of the problem, which is called the MQ problem. However, it is still an open question whether or not it is able to build efficient constructions of public-key identification based on multivariate polynomials of degree greater than two. In this paper, we tackle the cubic case of this question and construct public-key identification schemes based on the cubic version of the problem, which is called the MC problem. The MQ problem is a special case of the MC problem. Our schemes consist of a protocol which is zero-knowledge argument of knowledge for the MC problem under the assumption of the existence of a non-interactive commitment scheme. For a practical parameter choice, the efficiency of our scheme is highly comparable to that of the schemes based on the MQ problem. Furthermore, the parallel version of our scheme also achieves the security under active attack with some additional cost.
Chapter PDF
Similar content being viewed by others
References
Abdalla, M., An, J.H., Bellare, M., Namprempre, C.: From Identification to Signatures via the Fiat-Shamir Transform: Minimizing Assumptions for Security and Forward-Security. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 418–433. Springer, Heidelberg (2002)
Arditti, D., Berbain, C., Billet, O., Gilbert, H.: Compact FPGA Implementations of QUAD. In: Bao, F., Miller, S. (eds.) ASIACCS, pp. 347–349. ACM (2007)
Bardet, M., Faugère, J.-C., Salvy, B.: Complexity of Gröbner Basis Computation for Semi-regular Overdetermined Sequences over F 2 with Solutions in F 2. Research Report RR-5049, INRIA (2003)
Bellare, M., Namprempre, C., Neven, G.: Security Proofs for Identity-Based Identification and Signature Schemes. J. Cryptology 22(1), 1–61 (2009)
Berbain, C., Gilbert, H., Patarin, J.: QUAD: A Practical Stream Cipher with Provable Security. In: Vaudenay (ed.) [31], pp. 109–128
Bettale, L., Faugère, J.-C., Perret, L.: Security Analysis of Multivariate Polynomials for Hashing. In: Yung, M., Liu, P., Lin, D. (eds.) Inscrypt 2008. LNCS, vol. 5487, pp. 115–124. Springer, Heidelberg (2009)
Bettale, L., Faugère, J.-C., Perret, L.: Hybrid Approach for Solving Multivariate Systems over Finite Fields. Journal of Mathematical Cryptology 3(3), 177–197 (2009)
Bouillaguet, C., Chen, H.-C., Cheng, C.-M., Chou, T., Niederhagen, R., Shamir, A., Yang, B.-Y.: Fast Exhaustive Search for Polynomial Systems in F 2. In: Mangard, S., Standaert, F.-X. (eds.) CHES 2010. LNCS, vol. 6225, pp. 203–218. Springer, Heidelberg (2010)
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)
Ding, J., Yang, B.-Y.: Multivariates Polynomials for Hashing. In: Pei, D., Yung, M., Lin, D., Wu, C. (eds.) Inscrypt 2007. LNCS, vol. 4990, pp. 358–371. Springer, Heidelberg (2008)
Faugère, J.C.: A New Efficient Algorithm for Computing Gröbner Bases without Reduction to Zero (F5). In: Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, ISSAC 2002, pp. 75–83. ACM, New York (2002)
Faugère, J.-C., Perret, L.: Cryptanalysis of 2R\(^{\mbox{-}}\) Schemes. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 357–372. Springer, Heidelberg (2006)
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)
Garey, M.R., Johnson, D.S.: Computers and Intractability; A Guide to the Theory of NP-Completeness. W.H. Freeman & Co., New York (1979)
Goldreich, O.: Foundations of Cryptography. Basic Tools, vol. I. Cambridge University Press, Cambridge (2001)
Han, Y., Okamoto, T., Qing, S. (eds.): ICICS 1997. LNCS, vol. 1334. Springer, Heidelberg (1997)
Johnson, D.S., Feige, U. (eds.): Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13. ACM (2007)
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)
Matsumoto, T., Imai, H.: Public Quadratic Polynomial-Tuples for Efficient Signature-Verification and Message-Encryption. In: Günther, C.G. (ed.) EUROCRYPT 1988. LNCS, vol. 330, pp. 419–453. Springer, Heidelberg (1988)
Pass, R., Venkitasubramaniam, M.: An Efficient Parallel Repetition Theorem for Arthur-Merlin Games. In: Johnson, Feige (eds.) [17], pp. 420–429
Patarin, J.: Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): Two New Families of Asymmetric Algorithms. In: Maurer, U. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 33–48. Springer, Heidelberg (1996)
Patarin, J., Goubin, L.: Asymmetric Cryptography with S-Boxes. In: Han, et al. (eds.) [16], pp. 369–380
Patarin, J., Goubin, L.: Trapdoor One-Way Permutations and Multi- variate Polynominals. In: Han, et al. (eds.) [16], pp. 356–368
Pointcheval, D.: A New Identification Scheme Based on the Perceptrons Problem. In: Guillou, L.C., Quisquater, J.-J. (eds.) EUROCRYPT 1995. LNCS, vol. 921, pp. 319–328. Springer, Heidelberg (1995)
Pointcheval, D., Poupard, G.: A New NP-Complete Problem and Public-key Identification. Des. Codes Cryptography 28(1), 5–31 (2003)
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)
Shamir, A.: An Efficient Identification Scheme Based on Permuted Kernels (Extended Abstract). In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 606–609. Springer, Heidelberg (1990)
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)
Stern, J.: Designing Identification Schemes with Keys of Short Size. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 164–173. Springer, Heidelberg (1994)
Stern, J.: A New Paradigm for Public Key Identification. IEEE Transactions on Information Theory, 13–21 (1996)
Vaudenay, S. (ed.): EUROCRYPT 2006. LNCS, vol. 4004. Springer, Heidelberg (2006)
Ye, D.-F., Lam, K.-Y., Dai, Z.-D.: Cryptanalysis of “2R” Schemes. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 315–325. Springer, Heidelberg (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 International Association for Cryptologic Research
About this paper
Cite this paper
Sakumoto, K. (2012). Public-Key Identification Schemes Based on Multivariate Cubic Polynomials. In: Fischlin, M., Buchmann, J., Manulis, M. (eds) Public Key Cryptography – PKC 2012. PKC 2012. Lecture Notes in Computer Science, vol 7293. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-30057-8_11
Download citation
DOI: https://doi.org/10.1007/978-3-642-30057-8_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-30056-1
Online ISBN: 978-3-642-30057-8
eBook Packages: Computer ScienceComputer Science (R0)