Quantum Circuits for Cryptanalysis

Date Issued:: 2016
Summary:: Finite elds of the form F2m play an important role in coding theory and cryptography. We show that the choice of how to represent the elements of these elds can have a signi cant impact on the resource requirements for quantum arithmetic. In particular, we show how the Gaussian normal basis representations and \ghost-bit basis" representations can be used to implement inverters with a quantum circuit of depth O(mlog(m)). To the best of our knowledge, this is the rst construction with subquadratic depth reported in the literature. Our quantum circuit for the computation of multiplicative inverses is based on the Itoh-Tsujii algorithm which exploits the property that, in a normal basis representation, squaring corresponds to a permutation of the coe cients. We give resource estimates for the resulting quantum circuit for inversion over binary elds F2m based on an elementary gate set that is useful for fault-tolerant implementation. Elliptic curves over nite elds F2m play a prominent role in modern cryptography. Published quantum algorithms dealing with such curves build on a short Weierstrass form in combination with a ne or projective coordinates. In this thesis we show that changing the curve representation allows a substantial reduction in the number of T-gates needed to implement the curve arithmetic. As a tool, we present a quantum circuit for computing multiplicative inverses in F2m in depth O(mlogm) using a polynomial basis representation, which may be of independent interest. Finally, we change our focus from the design of circuits which aim at attacking computational assumptions on asymmetric cryptographic algorithms to the design of a circuit attacking a symmetric cryptographic algorithm. We consider a block cipher, SERPENT, and our design of a quantum circuit implementing this cipher to be used for a key attack using Grover's algorithm as in [18]. This quantum circuit is essential for understanding the complexity of Grover's algorithm.

Title:	Quantum Circuits for Cryptanalysis.	220 views 58 downloads
Name(s):	Amento, Brittanney Jaclyn, author Steinwandt, Rainer, Thesis advisor Florida Atlantic University, Degree grantor Charles E. Schmidt College of Science Department of Mathematical Sciences
Type of Resource:	text
Genre:	Electronic Thesis Or Dissertation
Date Created:	2016
Date Issued:	2016
Publisher:	Florida Atlantic University
Place of Publication:	Boca Raton, Fla.
Physical Form:	application/pdf
Extent:	82 p.
Language(s):	English
Summary:	Finite elds of the form F2m play an important role in coding theory and cryptography. We show that the choice of how to represent the elements of these elds can have a signi cant impact on the resource requirements for quantum arithmetic. In particular, we show how the Gaussian normal basis representations and \ghost-bit basis" representations can be used to implement inverters with a quantum circuit of depth O(mlog(m)). To the best of our knowledge, this is the rst construction with subquadratic depth reported in the literature. Our quantum circuit for the computation of multiplicative inverses is based on the Itoh-Tsujii algorithm which exploits the property that, in a normal basis representation, squaring corresponds to a permutation of the coe cients. We give resource estimates for the resulting quantum circuit for inversion over binary elds F2m based on an elementary gate set that is useful for fault-tolerant implementation. Elliptic curves over nite elds F2m play a prominent role in modern cryptography. Published quantum algorithms dealing with such curves build on a short Weierstrass form in combination with a ne or projective coordinates. In this thesis we show that changing the curve representation allows a substantial reduction in the number of T-gates needed to implement the curve arithmetic. As a tool, we present a quantum circuit for computing multiplicative inverses in F2m in depth O(mlogm) using a polynomial basis representation, which may be of independent interest. Finally, we change our focus from the design of circuits which aim at attacking computational assumptions on asymmetric cryptographic algorithms to the design of a circuit attacking a symmetric cryptographic algorithm. We consider a block cipher, SERPENT, and our design of a quantum circuit implementing this cipher to be used for a key attack using Grover's algorithm as in [18]. This quantum circuit is essential for understanding the complexity of Grover's algorithm.
Identifier:	FA00004662 (IID)
Degree granted:	Dissertation (Ph.D.)--Florida Atlantic University, 2016.
Collection:	FAU Electronic Theses and Dissertations Collection
Note(s):	Includes bibliography.
Subject(s):	Artificial intelligence Computer networks Cryptography Data encryption (Computer science) Finite fields (Algebra) Quantum theory
Held by:	Florida Atlantic University Libraries
Sublocation:	Digital Library
Links:	http://purl.flvc.org/fau/fd/FA00004662
Persistent Link to This Record:	http://purl.flvc.org/fau/fd/FA00004662
Use and Reproduction:	Copyright © is held by the author, with permission granted to Florida Atlantic University to digitize, archive and distribute this item for non-profit research and educational purposes. Any reuse of this item in excess of fair use or other copyright exemptions requires permission of the copyright holder.
Use and Reproduction:	http://rightsstatements.org/vocab/InC/1.0/
Host Institution:	FAU
Is Part of Series:	Florida Atlantic University Digital Library Collections.

In Collections

FAU Theses and Dissertations

Search In

You are here

In Collections