Abstract
The problem of solving a system of quadratic equations in multiple variables—known as multivariate-quadratic or \(\mathcal {MQ}\) problem—is the underlying hard problem of various cryptosystems. For efficiency reasons, a common instantiation is to consider quadratic equations over \(\mathbb {F}_2\). The current state of the art in solving the \(\mathcal {MQ}\) problem over \(\mathbb {F}_2\) for sizes commonly used in cryptosystems is enumeration, which runs in time \(\varTheta (2^n)\) for a system of n variables. Grover’s algorithm running on a large quantum computer is expected to reduce the time to \(\varTheta (2^{n/2})\). As a building block, Grover’s algorithm requires an “oracle”, which is used to evaluate the quadratic equations at a superposition of all possible inputs. In this paper, we describe two different quantum circuits that provide this oracle functionality. As a corollary, we show that even a relatively small quantum computer with as little as 92 logical qubits is sufficient to break \(\mathcal {MQ}\) instances that have been proposed for 80-bit pre-quantum security.
This work has been supported by the European Commission through the ICT program under contract ICT-645622 (PQCRYPTO); by the European Research Council under grant 320571 (QCLS) and by the Netherlands Organisation for Scientific Research (NWO) through Veni 2013 project 13114. Permanent ID of this document: 40eb0e1841618b99ae343ffa073d6c1e. Date: 2016-09-01.
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.
The problem of factoring a number N is reduced to finding the order of an element x modulo N, which requires a bit more than \(2 \log _2 N\) qubits [NC10, §5.3.1].
- 2.
Note that a SWAP gate can be written with CNOTs:
- 3.
References
Amy, M., Di Matteo, O., Gheorghiu, V., Mosca, M., Parent, A., Schanck, J.: Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3. Preprint 2016. https://arxiv.org/abs/1603.09383
Bouillaguet, C., Cheng, C.-M., Chou, T., Niederhagen, R., Yang, B.-Y.: Fast exhaustive search for quadratic systems in \(\mathbb{F}_{2}\) on FPGAs. In: Lange, T., Lauter, K., Lisoněk, P. (eds.) SAC 2013. LNCS, vol. 8282, pp. 205–222. Springer, Heidelberg (2014). doi:10.1007/978-3-662-43414-7_11
Brassard, G., HØyer, P., Tapp, A.: Quantum counting. In: Larsen, K.G., Skyum, S., Winskel, G. (eds.) ICALP 1998. LNCS, vol. 1443, pp. 820–831. Springer, Heidelberg (1998). doi:10.1007/BFb0055105
Chuang, I.: Quantum circuit viewer: qasm2circ (2005). http://www.media.mit.edu/quanta/qasm2circ/. Accessed 24 June 2016
Ding, J., Schmidt, D.: Rainbow, a new multivariable polynomial signature scheme. In: Ioannidis, J., Keromytis, A., Yung, M. (eds.) ACNS 2005. LNCS, vol. 3531, pp. 164–175. Springer, Heidelberg (2005). doi:10.1007/11496137_12
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company (1979)
Green, A.S., Lumsdaine, P.L.F., Ross, N.J., Selinger, P., Valiron, B.: An introduction to quantum programming in quipper. In: Dueck, G.W., Miller, D.M. (eds.) RC 2013. LNCS, vol. 7948, pp. 110–124. Springer, Heidelberg (2013). doi:10.1007/978-3-642-38986-3_10
Green, A.S., Lumsdaine, P.L., Ross, N.J., Selinger, P., Valiron, B.: Quipper: a scalable quantum programming language. 48(6), 333–342 (2013). https://arxiv.org/pdf/1304.3390
Grassl, M., Langenberg, B., Roetteler, M., Steinwandt, R.: Applying grover’s algorithm to AES: quantum resource estimates. In: Takagi, T. (ed.) PQCrypto 2016. LNCS, vol. 9606, pp. 29–43. Springer, Heidelberg (2016). doi:10.1007/978-3-319-29360-8_3
Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, pp. 212–219. ACM (1996)
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). doi:10.1007/3-540-48910-X_15
Maslov, D., Dueck, G.W.: Improved quantum cost for n-bit Toffoli gates. Electron. Lett. 39(25), 1790–1791 (2003)
Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2010)
Patarin, J., Courtois, N., Goubin, L.: QUARTZ, 128-bit long digital signatures. In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol. 2020, pp. 282–297. Springer, Heidelberg (2001). doi:10.1007/3-540-45353-9_21
Petzoldt, A., Chen, M.-S., Yang, B.-Y., Tao, C., Ding, J.: Design principles for HFEv- based multivariate signature schemes. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015. LNCS, vol. 9452, pp. 311–334. Springer, Heidelberg (2015). doi:10.1007/978-3-662-48797-6_14
Selinger, P.: The quipper language. http://www.mathstat.dal.ca/~selinger/quipper/. Accessed 09 Jan 2016
Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In SFCS 1994 Proceedings of the 35th Annual Symposium on Foundations of Computer Science, pp. 124–134. IEEE (1994). http://www-math.mit.edu/~shor/papers/algsfqc-dlf.pdf
Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26, 1484–1509 (1997). http://arxiv.org/abs/quant-ph/9508027
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). doi:10.1007/978-3-642-22792-9_40
Toffoli, T.: Reversible Computing. Springer, Heidelberg (1980)
Watson, E.J.: Primitive polynomials (mod 2). Math. Comput. 16(79), 368–369 (1962)
Yang, B.-Y., Chen, J.-M., Courtois, N.T.: On asymptotic security estimates in XL and Gröbner bases-related algebraic cryptanalysis. In: Lopez, J., Qing, S., Okamoto, E. (eds.) ICICS 2004. LNCS, vol. 3269, pp. 401–413. Springer, Heidelberg (2004). doi:10.1007/978-3-540-30191-2_31
Acknowledgments
The authors are grateful to Gauillaume Allais and Peter Selinger for their helpful suggestions. In particular, it was Peter Selinger’s suggestion to construct a counter from a primitive polynomial.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
A Example code
A Example code
The following is Python code that generates the first oracle circuit, which we described informally in Sect. 4.
To turn this into a useful commandline util that converts a system of quadratic equations into a quantum circuit in Nielsen and Chuang’s QASM [Chu05] format, we need a few more lines of code.Footnote 3 One invokes the completed script as follows.
The second oracle is more complex and easier to synthesize in a special purpose language. The following is an implementation of the first and second oracle in the quipper programming language [GLR+13b, GLR+13a, Sel], which is based on Haskell.
The gate counts mentioned in the conclusion were generated by the build-in GateCount functionality of Quipper, which was invoked (for the first oracle) with the following code.
The variable sqe is set to the system of 85 equations in 81 variables where every coefficient is 1 as it requires most gates executed in our construction. We use the following implementation of Grover’s algorithm.
Rights and permissions
Copyright information
© 2016 Springer International Publishing AG
About this paper
Cite this paper
Schwabe, P., Westerbaan, B. (2016). Solving Binary \(\mathcal {MQ}\) with Grover’s Algorithm. In: Carlet, C., Hasan, M., Saraswat, V. (eds) Security, Privacy, and Applied Cryptography Engineering. SPACE 2016. Lecture Notes in Computer Science(), vol 10076. Springer, Cham. https://doi.org/10.1007/978-3-319-49445-6_17
Download citation
DOI: https://doi.org/10.1007/978-3-319-49445-6_17
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-49444-9
Online ISBN: 978-3-319-49445-6
eBook Packages: Computer ScienceComputer Science (R0)