Aprimoramento de Protocolo de Identificação Baseado no Problema MQ

• Fábio S. Monteiro USP / Marinha do Brasil
• Denise Goya USP
• Routo Terada USP

DOI: https://doi.org/10.5753/sbseg.2012.20537

Resumo

O problema MQ, que consiste em resolver um sistema de equações polinomiais multivariáveis quadráticas sobre um corpo finito, tem atraído a atenção de pesquisadores para o desenvolvimento de sistemas criptográficos de chave pública por ser (1) NP-completo, (2) não ter algoritmo conhecido de tempo polinomial para sua solução nem mesmo no modelo computacional quântico e (3) viabilizar primitivas criptográficas de interesse prático. Em 2011, Sakumoto, Shirai e Hiwatari apresentaram dois novos protocolos de identificação de conhecimento-zero baseados exclusivamente no problema MQ. O protocolo em 3 passos de Sakumoto et al. apresenta probabilidade de personificação de 2/3 em uma rodada. No presente artigo é proposto um protocolo aprimorado que reduz essa probabilidade para 1/2. O resultado é um protocolo que diminui a comunicação total necessária e requer um número menor de iterações para o mesmo nível de segurança.

Referências

Abdalla, M., An, J. H., Bellare, M. e Namprempre, C. (2002). From identification to signatures via the Fiat-Shamir transform: Minimizing assumptions for security and forward-security. In Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology, EUROCRYPT ’02, pages 418–433, London, UK. Springer-Verlag.

Alaoui, S. M. E. Y., Dagdelen, O., Véron, P., Galindo, D. e Cayrel, P.-L. (2012). Extended security arguments for signature schemes. In Proceedings of the 5th international conference on Cryptology in Africa, AFRICACRYPT’12, pages 19–34, Berlin, Heidelberg. Springer-Verlag.

Bellare, M. e Rogaway, P. (1993). Random oracles are practical: a paradigm for designing efficient protocols. In Proceedings of the 1st ACM conference on Computer and communications security, CCS ’93, pages 62–73, New York, NY, USA. ACM.

Bernstein, D. J., Buchmann, J. e Dahmen, E., editors (2009). Post-Quantum Cryptography. Springer.

Bouillaguet, C., Faug`ere, J.-C., Fouque, P.-A. e Perret, L. (2011). Practical cryptanalysis of the identification scheme based on the isomorphism of polynomial with one secret problem. In Proceedings of the 14th international conference on Practice and theory in public key cryptography conference on Public key cryptography, PKC’11, pages 473–493, Berlin, Heidelberg. Springer-Verlag.

Courtois, N. T., Goubin, L. e Patarin, J. (2003). SFLASHv3, a fast asymmetric signature scheme. IACR Cryptology ePrint Archive, 2003:211.

Ding, J., Gower, J. E. e Schmidt, D. (2006). Multivariate Public Key Cryptosystems, volume 25 of Advances in Information Security. Springer.

Dubois, V., Fouque, P.-A., Shamir, A. e Stern, J. (2007). Practical cryptanalysis of SFLASH. In Proceedings of Advances in Cryptology–CRYPTO ’07. Springer-Verlag.

Fiat, A. e Shamir, A. (1987). How to prove yourself: Practical solutions to identification and signature problems. In Proceedings of Advances in Cryptology–CRYPTO ’86, pages 186–194, London, UK, UK. Springer-Verlag.

Garey, M. R. e Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman.

Halevi, S. e Micali, S. (1996). Practical and provably-secure commitment schemes from collision-free hashing. In Proceedings of the 16th Annual International Cryptology Conference on Advances in Cryptology, CRYPTO ’96, pages 201–215, London, UK, UK. Springer-Verlag.

Matsumoto, T. e Imai, H. (1988). Public quadratic polynomialtuples for efficient signature-verification and message-encryption. In Proceedings of Advances in Cryptology-EUROCRYPT ’88, pages 419–453. Springer-Verlag New York, Inc.

Patarin, J., Courtois, N. e Goubin, L. (2001). Flash, a fast multivariate signature algorithm. In Proceedings of the 2001 Conference on Topics in Cryptology: The Cryptographer’s Track at RSA, CT-RSA 2001, pages 298–307, London, UK, UK. Springer-Verlag.

Patarin, J. e Goubin, L. (1997). Trapdoor one-way permutations and multivariate polynomials. In Han, Y., Okamoto, T. e Qing, S., editors, Information and Communications Security, volume 1334 of Lecture Notes in Computer Science, pages 356–368. Springer Berlin / Heidelberg.

Petzoldt, A., Thomae, E., Bulygin, S. e Wolf, C. (2011). Small public keys and fast verification for multivariate quadratic public key systems. In Proceedings of the 13th international conference on Cryptographic hardware and embedded systems, CHES’11, pages 475–490, Berlin, Heidelberg. Springer-Verlag.

Pointcheval, D. e Stern, J. (1996). Security proofs for signature schemes. In Proceedings of the 15th annual international conference on Theory and application of cryptographic techniques, EUROCRYPT’96, pages 387–398, Berlin, Heidelberg. Springer-Verlag.

Pointcheval, D. e Stern, J. (2000). Security arguments for digital signatures and blind signatures. J. Cryptology, 13(3):361–396.

Sakumoto, K., Shirai, T. e Hiwatari, H. (2011). Public-key identification schemes based on multivariate quadratic polynomials. In Rogaway, P., editor, Advances in Cryptology CRYPTO 2011, volume 6841 of Lecture Notes in Computer Science, pages 706–723. Springer Berlin / Heidelberg.

Shor, P. W. (1997). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput., 26(5):1484–1509.

Stern, J. (2006). A new paradigm for public key identification. IEEE Transactions on Information Theory, 42(6):1757–1768.

Wolf, C. (2005). Multivariate Quadratic Polynomials in Public Key Cryptography. PhD thesis, Katholieke Universiteit Leuven.

Wolf, C. e Preneel, B. (2005). Taxonomy of public key schemes based on the problem of multivariate quadratic equations. IACR Cryptology ePrint Archive, 2005:77.