Welcome to the resource topic for 2022/501
Title:
Another Concrete Quantum Cryptanalysis of Binary Elliptic Curves
Authors: Dedy Septono Catur Putranto, Rini Wisnu Wardhani, Harashta Tatimma Larasati, Howon Kim
Abstract:This paper presents concrete quantum cryptanalysis for binary elliptic curves for a time-efficient implementation perspective (i.e., reducing the circuit depth), complementing the previous research by Banegas et al., that focuses on the space-efficiency perspective (i.e., reducing the circuit width). To achieve the depth optimization, we propose an improvement to the existing circuit implementation of the Karatsuba multiplier and FLT-based inversion, then construct and analyze the resource in Qiskit quantum computer simulator. The proposed multiplier architecture, improving the quantum Karatsuba multiplier by Van Hoof et al., reduces the depth and yields lower number of CNOT gates that bounds to O(nlog2(3)) while maintaining a similar number of Toffoli gates and qubits. Furthermore, our improved FLT-based inversion reduces CNOT count and overall depth, with a tradeoff of higher qubit size. Finally, we employ the proposed multiplier and FLT-based inversion for performing quantum cryptanalysis of binary point addition as well as the complete Shor’s algorithm for elliptic curve discrete logarithm problem (ECDLP). As a result, apart from depth reduction, we are also able to reduce up to 90% of the Toffoli gates required in a single-step point addition compared to prior work, leading to significant improvements and give a new insights on quantum cryptanalysis for a depth-optimized implementation.
ePrint: https://eprint.iacr.org/2022/501
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .