Small Public Keys and Fast Verification for M\mathcal{M}ultivariate Q\mathcal{Q}uad

详细信息    查看全文

• 作者：Albrecht Petzoldt (1) apetzoldt@cdc.informatik.tu-darmstadt.de
  Enrico Thomae (2) Enrico.Thomae@rub.de
  Stanislav Bulygin (1) Stanislav.Bulygin@cased.de
  Christopher Wolf (2) Christopher.Wolf@rub.de
• 关键词：Multivariate Quadratic Cryptography – ; Post ; Quantum Cryptography – ; Implementation – ; Unbalanced Oil and Vinegar Signature Scheme
• 刊名：Lecture Notes in Computer Science
• 出版年：2011
• 出版时间：2011
• 年：2011
• 卷：6917
• 期：1
• 页码：475-490
• 全文大小：278.4 KB
• 参考文献：1. Bernstein, D.J., Buchmann, J., Dahmen, E. (eds.): Post-Quantum Cryptography. Springer, Heidelberg (2009)
  2. Bettale, L., Faug茅re, J.-C., Perret, L.: Hybrid approach for solving multivariate systems over finite fields. Journal of Mathematical Cryptology 3, 177–197 (2009)
  3. Bogdanov, A., Eisenbarth, T., Rupp, A., Wolf, C.: Time-area optimized public-key engines: -cryptosystems as replacement for elliptic curves? In: Oswald, E., Rohatgi, P. (eds.) CHES 2008. LNCS, vol. 5154, pp. 45–61. Springer, Heidelberg (2008)
  4. Chen, A.I.-T., Chen, C.-H.O., Chen, M.-S., Cheng, C.-M., Yang, B.-Y.: Practical-sized instances of multivariate pKCs: Rainbow, TTS, and ℓIC-derivatives. In: Buchmann, J., Ding, J. (eds.) PQCrypto 2008. LNCS, vol. 5299, pp. 95–108. Springer, Heidelberg (2008)
  5. 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)
  6. Ding, J., Gower, J.E., Schmidt, D.: Multivariate Public Key Cryptography. Cambridge University Press, Cambridge (2006)
  7. Faug茅re, J.-C.: A new efficient algorithm for computing Gr枚bner bases without reduction to zero (F5). In: ISSAC 2002, pp. 75–83. ACM Press, New York (2002)
  8. 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)
  9. Hu, Y., Wang, L., Chou, C., Lai, F.: Similar keys of multivariate quadratic public key cryptosystems. In: Desmedt, Y.G., Wang, H., Mu, Y., Li, Y. (eds.) CANS 2005. LNCS, vol. 3810, pp. 211–222. Springer, Heidelberg (2005)
  10. 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)
  11. Kipnis, A., Shamir, A.: Cryptanalysis of the oil & vinegar signature scheme. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 257–266. Springer, Heidelberg (1998)
  12. Patarin, J.: The oil and vinegar signature scheme. Presented at the Dagstuhl Workshop on Cryptography, transparencies (September 1997)
  13. Petzoldt, A., Bulygin, S., Buchmann, J.: A multivariate signature scheme with a partially cyclic public key. In: SCC 2010, pp. 229–235 (2010)
  14. Petzoldt, A., Bulygin, S., Buchmann, J.: Linear recurring sequences for the UOV key generation. In: Catalano, D., Fazio, N., Gennaro, R., Nicolosi, A. (eds.) PKC 2011. LNCS, vol. 6571, pp. 335–350. Springer, Heidelberg (2011)
  15. Petzoldt, A., Thomae, E., Bulygin, S., Wolf, C.: Small Public Keys and Fast Verification for Multivariate Quadratic Public Key Systems (full version), http://eprint.iacr.org/2011/294
  16. Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing 26(5), 1484–1509 (1997)
  17. Tur谩n, P.: On an extremal problem in Graph Theory. Matematiko Fizicki Lapok 48, 436–452 (1941)
  18. Wolf, C., Preneel, B.: Taxonomy of public key schemes based on the problem of multivariate quadratic equations, http://eprint.iacr.org/2005/077
  19. Wolf, C., Preneel, B.: Superfluous keys in Multivariate Quadratic asymmetric systems. In: Vaudenay, S. (ed.) PKC 2005. LNCS, vol. 3386, pp. 275–287. Springer, Heidelberg (2005)
  20. Wolf, C., Preneel, B.: Equivalent keys in multivariate quadratic public key systems. Journal of Mathematical Cryptology (to appear, 2011)
  21. 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)
• 作者单位：1. Technische Universit盲t Darmstadt and, Center for Advanced Security Research Darmstadt (CASED), Germany2. Horst G枚rtz Institute for IT-security, Faculty of Mathematics, Ruhr-University of Bochum, 44780 Bochum, Germany
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

Security of public key schemes in a post-quantum world is a challenging task—as both RSA and ECC will be broken then. In this paper, we show how post-quantum signature systems based on M\mathcal{M}ultivariate Q\mathcal{Q}uadratic (MQ\mathcal{MQ}) polynomials can be improved up by about 9/10, and 3/5, respectively, in terms of public key size and verification time. The exact figures are 88% and 59%. This is particularly important for small-scale devices with restricted energy, memory, or computational power. In addition, we provide evidence that this reduction does not affect security and that it is also optimal in terms of possible attacks. We do so by combining the previously unrelated concepts of reduced and equivalent keys. Our new scheme is based on the so-called Unbalanced Oil and Vinegar class of MQ\mathcal{MQ}-schemes. We have derived our results mathematically and verified the speed-ups through a C++ implementation.