“Parallelism strategies for the tuneable golden claw-finding problem.
Azarderakhsh, R., Biasse, J.F., El Khatib, R., Langenberg, B., Pring, B.
International Journal of Computer Mathematics (accepted subject to revisions 2020)
We examine the impact of the "Tiny Claw" algorithm proposed in BP2020 on the cost of attacking the SIKE public-key cryptosystem, under realistic assumptions concerning hardware layout, classical memory-access costs and the cost of the neccessary quantum circuit that computes arbitrary degree isogeny paths. We observe that whilst the original Tiny Claw algorithm does not reach its full potential under these assumptions, our adaptations and new options for parallelism mean that even in a pessimistic cost model for classical memory-access costs, the Tiny Claw algorithm may offer competitive or superior performance compared to other quantum algorithms, under the assumption that qubits require computational effort to maintain.
There is no talk associated with this journal paper. The scripts used can be found here.
“Improvements to quantum search techniques for block-ciphers, with applications to AES”.
Davenport, J.H., Pring, B.
Selected Areas in Cryptography 2020.
In this paper we demonstrate a purely advantageous trade-off for attacking block-ciphers with quantum search techniques. This allows us to reduce the number of qubits and quantum gates required to attack AES-128/192 by a factor of just over two and for AES-256 by a factor of just over 3. This technique gives the greatest advantage when we are executing a quantum search on a single quantum computer, but also approximately halves the costs for attacking AES-128/192/256 when we are constrained by a maximum quantum circuit-depth of \(2^{96}\), as required in the NIST post-quantum standardisation specifications.
The slides I used to present this talk at SAC2020 can be found here. The associated code in the form of SageMath scripts and Microsoft Q# code is available here.
“A framework for reducing the overhead of the quantum oracle for use with Grover’s algorithm with applications to cryptanalysis of SIKE”
Biasse, J.F., Pring, B.
Journal of Mathematical Cryptology (2020)
A basic quantum search algorithms makes a number of queries to a quantum oracle. In this paper we examine how preprocessing can be used to reduce the cost of quantum search algorithms by modifying them to create more expensive quantum oracles, that must be executed fewer times. This has the effect (for certain problems) of reducing the total cost of the quantum search algorithm.
We demonstrated that this methodology could be applied to asymptotically reduce the cost of attacking the SIKE cryptosystem from \(O\big(p^{1/4} \cdot C\big)\) to \(O\big(p^{1/4} \cdot \sqrt{C \cdot \log_2 p}\big)\), where \(p\) is the prime number that defines the security of SIKE and \(C\) is the cost of a necessary quantum circuit that computes an isogeny-path.
This work refines the work in PRING2018 below and offers asymptotic results. This approach to reducing the cost to attack SIKE is later called the "Tiny Claw" algorithm and further studied in ABELP2020 above.
The slides I used to present this talk at MathCrypt 2019 can be found here.
“A trade-off between classical and quantum circuit size of the attack against CSIDH”
Biasse, J.F., Bonnetain, X., Pring, B., Schrottenloher, A., Youmans W.
Journal of Mathematical Cryptology (2020)
In this paper we demonstrate an adaptation to Kuperberg's algorithm, whereby the quantum cost of attacking the CSIDH cryptosystem is reduced by increasing the time spent in the classical search phase.
The slides I used to present this talk at MathCrypt 2019 can be found here.
“Exploiting preprocessing for quantum search to break parameters for MQ cryptosystems”
Pring, B.
International Workshop on the Arithmetic of Finite Fields 2018
My first quantum paper - I proposed that preprocessing could be combined with Grover's algorithm to lower the concrete cost of attacking the Multivariate Quadratic problem, the underlying hard problem behind the Gui cryptosystem. This paper deals only with the methodology and produces concrete figures --- the asymptotic case is dealt with above in BP2020.
The slides I used to present this talk at WAIFI 2018 can be found here.
“A Generalised Successive Resultants Algorithm”
Davenport, J.H., Petit, C., Pring, B.
International Workshop on the Arithmetic of Finite Fields 2016.
In this paper we develop a framework that captures the original "Successive Resultants Algorithm" by Petit that can be used for root-finding over finite fields. We prove its correctness in the general case and demonstrate the utility of this framework by showing that the core component --- a sequence of linearised polynomials --- can be replaced by maps derived from order of the finite field.
The slides I used to present this talk at WAIFI 2016 can be found here and the code for this paper may be found here.