Parallelism strategies for the tuneable golden-claw finding problem

References

• G. Adj, D. Cervantes-Vázquez, J.J. Chi-Domínguez, A. Menezes, and F. Rodríguez-Henríquez, On the Cost of Computing Isogenies between Supersingular Elliptic Curves, International Conference on Selected Areas in Cryptography, Springer, 2018, pp. 322–343.
   Google Scholar
• R. Azarderakhsh, M. Campagna, C. Costello, L. Feo, B. Hess, A. Jalali, D. Jao, B. Koziel, B. LaMacchia, P. Longa, M. Naehrig, G. Pereira, J. Renes, V. Soukharev, and D. Urbanik, Supersingular isogeny key encapsulation, Submission to the NIST Post-Quantum Standardization project, 2017.
   Google Scholar
• M. Bardet, J.C. Faugére, B. Salvy, and P.J. Spaenlehauer, On the complexity of solving quadratic Boolean systems, J. Complex. 29(1) (2013), pp. 53–75.
   Web of Science ®Google Scholar
• R. Beals, S. Brierley, O. Gray, A.W. Harrow, S. Kutin, N. Linden, D. Shepherd, and M. Stather, Efficient distributed quantum computing, Proc. R. Soc. A: Math. Phys. Eng. Sci. 469(2153) (2013), p. 20120686.
   Google Scholar
• C.H. Bennett, Time/space trade-offs for reversible computation, SIAM J. Comput. 18(4) (1989), pp. 766–776.
   Web of Science ®Google Scholar
• D.J. Bernstein, Cost analysis of hash collisions: Will quantum computers make SHARCS obsolete, SHARCS 9 (2009), p. 105.
   Google Scholar
• D.J. Bernstein, The cr.yp.to blog, October 2017. Available at https://blog.cr.yp.to/20171017-collisions.html.
   Google Scholar
• J.F. Biasse and B. Pring, A framework for reducing the overhead of the quantum oracle for use with Grover's algorithm with applications to cryptanalysis of SIKE, J. Math. Cryptol. 15 (2019), pp. 143–156.
   Web of Science ®Google Scholar
• C. Bouillaguet, H.C. Chen, C.M. Cheng, T. Chou, R. Niederhagen, A. Shamir, and B.Y. Yang, Fast Exhaustive Search for Polynomial Systems in F2, International Workshop on Cryptographic Hardware and Embedded Systems, Springer, 2010, pp. 203–218.
   Google Scholar
• C. Bouillaguet, C.M. Cheng, T. Chou, R. Niederhagen, and B.Y. Yang, Fast Exhaustive Search for Quadratic systems in F2 on FPGAs, International Conference on Selected Areas in Cryptography, Springer, 2013, pp. 205–222.
   Google Scholar
• G. Brassard, P. Høyer, and A. Tapp, Quantum Cryptanalysis of Hash and Claw-free Functions, Latin American Symposium on Theoretical Informatics, Springer, 1998, pp. 163–169.
   Google Scholar
• G. Brassard, P. Hoyer, M. Mosca, and A. Tapp, Quantum amplitude amplification and estimation, Contemp. Math. 305 (2002), pp. 53–74.
   Google Scholar
• A. Chailloux, M. Naya-Plasencia, and A. Schrottenloher, An Efficient Quantum Collision Search Algorithm and Implications on Symmetric Cryptography, International Conference on the Theory and Application of Cryptology and Information Security, Springer, 2017, pp. 211–240.
   Google Scholar
• D.X. Charles, K.E. Lauter, and E.Z. Goren, Cryptographic hash functions from expander graphs, J. Cryptol. 22(1) (2009), pp. 93–113. doi:https://doi.org/10.1007/s00145-007-9002-x
   Web of Science ®Google Scholar
• A. Costache, B. Feigon, K.E. Lauter, M. Massierer, and A. Puskás, Ramanujan graphs in cryptography, CoRR (2018). Available at http://arxiv.org/abs/1806.05709.
   Google Scholar
• C. Costello, P. Longa, M. Naehrig, J. Renes, and F. Virdia, Improved classical cryptanalysis of the computational supersingular isogeny problem, IACR Cryptol. ePrint Arch. 2019 (2019), p. 298.
   Google Scholar
• T. Decru, Grover's tiny claw algorithm, 2019. Available at https://www.esat.kuleuven.be/cosic/blog/grovers-tiny-claw-algorithm/, cOSIC Cryptography blog.
   Google Scholar
• L. De Feo, D. Jao, and J. Plût, Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies, J. Math. Cryptol. 8 (2014), pp. 209–247.
   Google Scholar
• R. Elkhatib, R. Azarderakhsh, and M. Mozaffari-Kermani, Efficient and fast hardware architectures for SIKE round 2 on FPGA, Tech. Rep., Cryptology ePrint Archive: 2020/611, 2020.
   Google Scholar
• C. Gidney, Halving the cost of quantum addition, Quantum J. 2 (2018), p. 74.
   Web of Science ®Google Scholar
• L.K. Grover, A Fast Quantum Mechanical Algorithm for Database Search, Proceedings of the 28th Annual ACM Symposium on Theory of Computing, ACM, 1996, pp. 212–219.
   Google Scholar
• L. Grover and T. Rudolph, How significant are the known collision and element distinctness quantum algorithms? Preprint (2003). Available at arXiv:quant-ph/0309123.
   Google Scholar
• T. Häner, S. Jaques, M. Naehrig, M. Roetteler, and M. Soeken, Improved Quantum Circuits for Elliptic Curve Discrete Logarithms, International Conference on Post-Quantum Cryptography, Springer, 2020, pp. 425–444.
   Google Scholar
• S. Jaques, Quantum cost models for cryptanalysis of isogenies, Master's thesis, University of Waterloo, 2019.
   Google Scholar
• S. Jaques and J.M. Schanck, Quantum cryptanalysis in the ram model: Claw-finding attacks on SIKE, in Advances in Cryptology – CRYPTO 2019, A. Boldyreva and D. Micciancio, eds., Springer International Publishing, Cham, 2019, pp. 32–61.
   Google Scholar
• S. Jaques and J.M. Schanck, Quantum cryptanalysis in the ram model: Claw-finding attacks on SIKE, Tech. rep., Cryptology ePrint Archive: Report 2019/103, 2019. Available at https://eprint.iacr.org.
   Google Scholar
• S. Jaques and A. Schrottenloher, Low-gate quantum golden collision finding, IACR Cryptol. ePrint Arch. 2020 (2020), p. 424. Available at https://eprint.iacr.org/2020/424.pdf.
   Google Scholar
• S. Jaques, M. Naehrig, M. Roetteler, and F. Virdia, Implementing Grover oracles for quantum key search on AES and LowMC, Preprint (2019). Available at arXiv:1910.01700.
   Google Scholar
• S. Kimmel, C. Yen-Yu Lin, and L. Han-Hsuan, Oracles With Costs, 10th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2015, 20–22 May 2015, Brussels, Belgium, 2015, p. 44.
   Google Scholar
• National Institute of Standards Technology, Submission requirements and evaluation criteria for the Post-Quantum Cryptography standardization process, 2016. Available at http://csrc.nist.gov/groups/ST/post-quantum-crypto/documents/call-for-proposals-final-dec-2016.pdf. Accessed: 2020.
   Google Scholar
• M.A. Nielsen, I.L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, Cambridge, UK, 2010.
   Google Scholar
• A. Pietracaprina and G. Pucci, Optimal Many-to-One Routing on the Mesh with Constant Queues, European Conference on Parallel Processing, Springer, 2001, pp. 645–650.
   Google Scholar
• S. Tani, An Improved Claw Finding Algorithm using Quantum Walk, International Symposium on Mathematical Foundations of Computer Science, Springer, 2007, pp. 536–547.
   Google Scholar
• P.C. Van Oorschot and M.J. Wiener, Parallel Collision Search with Application to Hash Functions and Discrete Logarithms, Proceedings of the 2nd ACM Conference on Computer and Communications Security, ACM, 1994, pp. 210–218.
   Google Scholar
• C. Zalka, Grover's quantum searching algorithm is optimal, Phys. Rev. A 60(4) (1999), p. 2746.
   Web of Science ®Google Scholar