You are here

Elliptic curves: identity-based signing and quantum arithmetic

Download pdf | Full Screen View

Date Issued:
2014
Summary:
Pairing-friendly curves and elliptic curves with a trapdoor for the discrete logarithm problem are versatile tools in the design of cryptographic protocols. We show that curves having both properties enable a deterministic identity-based signing with “short” signatures in the random oracle model. At PKC 2003, Choon and Cheon proposed an identity-based signature scheme along with a provable security reduction. We propose a modification of their scheme with several performance benefits. In addition to faster signing, for batch signing the signature size can be reduced, and if multiple signatures for the same identity need to be verified, the verification can be accelerated. Neither the signing nor the verification algorithm rely on the availability of a (pseudo)random generator, and we give a provable security reduction in the random oracle model to the (`-)Strong Diffie-Hellman problem. Implementing the group arithmetic is a cost-critical task when designing quantum circuits for Shor’s algorithm to solve the discrete logarithm problem. We introduce a tool for the automatic generation of addition circuits for ordinary binary elliptic curves, a prominent platform group for digital signatures. Our Python software generates circuit descriptions that, without increasing the number of qubits or T-depth, involve less than 39% of the number of T-gates in the best previous construction. The software also optimizes the (CNOT) depth for F2-linear operations by means of suitable graph colorings.
Title: Elliptic curves: identity-based signing and quantum arithmetic.
257 views
136 downloads
Name(s): Budhathoki, Parshuram, author
Steinwandt, Rainer, Thesis advisor
Eisenbarth, Thomas, 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: 2014
Date Issued: 2014
Publisher: Florida Atlantic University
Place of Publication: Boca Raton, Fla.
Physical Form: application/pdf
Extent: 74 p.
Language(s): English
Summary: Pairing-friendly curves and elliptic curves with a trapdoor for the discrete logarithm problem are versatile tools in the design of cryptographic protocols. We show that curves having both properties enable a deterministic identity-based signing with “short” signatures in the random oracle model. At PKC 2003, Choon and Cheon proposed an identity-based signature scheme along with a provable security reduction. We propose a modification of their scheme with several performance benefits. In addition to faster signing, for batch signing the signature size can be reduced, and if multiple signatures for the same identity need to be verified, the verification can be accelerated. Neither the signing nor the verification algorithm rely on the availability of a (pseudo)random generator, and we give a provable security reduction in the random oracle model to the (`-)Strong Diffie-Hellman problem. Implementing the group arithmetic is a cost-critical task when designing quantum circuits for Shor’s algorithm to solve the discrete logarithm problem. We introduce a tool for the automatic generation of addition circuits for ordinary binary elliptic curves, a prominent platform group for digital signatures. Our Python software generates circuit descriptions that, without increasing the number of qubits or T-depth, involve less than 39% of the number of T-gates in the best previous construction. The software also optimizes the (CNOT) depth for F2-linear operations by means of suitable graph colorings.
Identifier: FA00004182 (IID)
Degree granted: Dissertation (Ph.D.)--Florida Atlantic University, 2014.
Collection: FAU Electronic Theses and Dissertations Collection
Note(s): Includes bibliography.
Subject(s): Coding theory
Computer network protocols
Computer networks -- Security measures
Data encryption (Computer science)
Mathematical physics
Number theory -- Data processing
Held by: Florida Atlantic University Libraries
Sublocation: Digital Library
Links: http://purl.flvc.org/fau/fd/FA00004182
Persistent Link to This Record: http://purl.flvc.org/fau/fd/FA00004182
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.