Quantum Circuits for the CSIDH: Optimizing Quantum Evaluation of Isogenies

被引：39

作者：

Bernstein, Daniel J. ^{[1
]}

Lange, Tanja ^{[2
]}

Martindale, Chloe ^{[2
]}

Panny, Lorenz ^{[2
]}

机构：

[1] Univ Illinois, Dept Comp Sci, Chicago, IL 60607 USA

[2] Tech Univ Eindhoven, Dept Math & Comp Sci, POB 513, NL-5600 MB Eindhoven, Netherlands

来源：

ADVANCES IN CRYPTOLOGY - EUROCRYPT 2019, PT II | 2019年 / 11477卷

基金：

欧盟地平线“2020”; 美国国家科学基金会;

关键词：

Elliptic curves; Isogenies; Circuits; Constant-time computation; Reversible computation; Quantum computation; Cryptanalysis;

D O I：

10.1007/978-3-030-17656-3_15

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

Choosing safe post-quantum parameters for the new CSIDH isogeny-based key-exchange system requires concrete analysis of the cost of quantum attacks. The two main contributions to attack cost are the number of queries in hidden-shift algorithms and the cost of each query. This paper analyzes algorithms for each query, introducing several new speedups while showing that some previous claims were too optimistic for the attacker. This paper includes a full computer-verified simulation of its main algorithm down to the bit-operation level.

引用

页码：409 / 441

页数：33

共 39 条

[1]

[Anonymous], 2018537 IACR CRYPT E

[2]

[Anonymous], 2018782 IACR CRYPT E

[3]

[Anonymous], 2018, J MATH CRYPTOL

[4]

[Anonymous], 2017, Topics in Computational Number Theory inspired by Peter L. Montgomery

[5]

[Anonymous], 2010, THESIS

[6]

[Anonymous], THESIS

[7]

[Anonymous], 1996, THESIS

[8]

Azarderakhsh Reza., 2016, Proceedings of the 3rd ACM International Workshop on ASIA Public-Key Cryptography, AsiaPKC'16, page, P1

[9]

Bernstein D. J., 2013, P 2013 ACM SIGSAC C, P967

[10]

Bernstein D. J., 2008, FINITE FIELDS APPL 2, P1

← 1 2 3 4 →