University of Calgary

UofC Navigation

**Post-quantum cryptography***Daniel J. Bernstein*

Large quantum computers will break RSA, DSA, ECC, and HECC, but cryptographers will still have many attractive choices of post-quantum public-key systems. This talk will survey the post-quantum landscape, and as an illustrative example will discuss McEliece's 1978 hidden-Goppa-code public-key encryption system.

**Security of compositions with implicit certificate schemes***Matthew Campagna*

We detail an attack originally described by Qu on the composition of an implicit certificate scheme known as optimal mail certificates (OMC) and ECDSA. This attack is an undetectable forgery by a passive adversary that requires no interaction with a signer or the certificate authority. We highlight where the attack fails when the OMC-scheme is replaced by the elliptic curve Qu-Vanstone (ECQV) certificate scheme. Finally, we indicate a proof of security against a passive adversary of ECQV combined with ECDSA under the generic group and random oracle model.

**NICE Cryptanalyses**

In this talk, I will present two cryptanalyses of cryptosystems based on the arithmetic of class groups of quadratic fields.

The first cryptanalysis is a joint work with Fabien Laguillaumie. This work is a polynomial time chosen-plaintext total break of the NICE family of cryptosystems based on ideal arithmetic in imaginary quadratic orders, introduced in the late 90's by Hartmann, Paulus and Takagi. The singular interest of these encryption schemes is their quadratic decryption time procedure. The security against a total break attack was believed to rely on the difficulty of factoring the public discriminant $\Delta_q=-pq^2$. We show how to factor $\Delta_q$ in cubic time in the security parameter, thanks to an element of the public key which is crucial to reach the quadratic decryption complexity.

The second cryptanalysis is a joint work with Antoine Joux, Fabien Laguillaumie and Phong Q. Nguyen. This work is the development of a new algorithm based on binary quadratic forms to factor integers of the form $N=pq^2$. This algorithm uses a new provable variant of Coppersmith's lattice-based root finding algorithm for homogeneous polynomials. Its running time is exponential in the general case, but becomes polynomial when special (arithmetic) hints are available. One hint is the element of the public key of NICE used in the previous cryptanalysis. The second is the knowledge that the regulator of the quadratic field $\mathbb{Q}(\sqrt{p})$ is unusually small. This is precisely the case for the public key of REAL-NICE, proposed by Jacobson, Scheidler and Weimer last year, an adaptation of NICE with real quadratic fields which also offers fast decryption. This gives a heuristic polynomial-time total break of REAL-NICE.

**Computing Scalar Multiplication with Many Cores***Chen-Mou Cheng*

After decades of remarkable growth, the performance of single-thread processors has slowed down, hitting both the power and ILP walls. To respond, the entire industry is now moving to the multi-core/many-core paradigm to exploit the increasing transistor budget offered by the Moore's law in semiconductor fabrication technologies. Graphics processing units (GPUs) are an example of computing devices with many simple cores, which we have demonstrated to be useful and cost-effective for computing stage-1 ECM in a recent paper "ECM on Graphics Cards."

In this sequel talk, we will provide an update and in-depth introduction on using many-cores to compute elliptic curve scalar multiplication, the core computation of ECM as well as ECC. We will report and compare state-of-the-art performance of scalar multiplication using various computing devices including GPU (NVIDIA CUDA), Cell (both Playstation 3 and the newer QS 22), and the latest 64-bit x86 processors (Intel Core 2 and AMD Phenom II). We will also explain how to achieve high computational throughput with these devices, e.g., by carefully managing the scarce on-die memories while having enough threads of computation for latency hiding.

**Isogeny computation in small characteristic***Luca De Feo*

Isogenies are an important tool in the study of elliptic curves. As such their applications in Elliptic Curve Cryptography are numerous, ranging from point counting to new cryptographic schemes.

The problem of finding explicit formulae expressing an isogeny between two elliptic curves has been studied by many. V?lu gave formulae for the case where the curves are defined over C; these formulae have been extended in works by Morain, Atkin and Charlap, Coley & Robbins to compute isogenies in the case where the characteristic of the field is larger than the degree of the isogeny.

The small characteristic case requires another treatment. Algorithms by Couveignes, Lercier, Joux & Lercier, Lercier & Sirvent give solutions to different instances of the problem. We review these strategies, then we present an improved algorithm based over Couveignes' ideas and we compare its performance to the other ones.

**Loading the bases - some open problems associated with the use of multiple-base number systems in ECC***Vassil Dimitrov*

Since the introduction of the double-base number system to the field of elliptic curve cryptography in 2005, the interest in using double ans multiple-base representations continues to grow. The study of these number representations leads to some very interesting number theoretic problems, associated with the theory of exponential Diophantine equations and Diophantine approximations. There are also some important applications of the double-base representations for efficient implementation of graph-theoretic and matrix inversion algorithms, that seems to be less known to the ECC community. The analysis of these algorithms leads to very intiguing and non-trivial problems that will be discussed at this talk.

**Cryptographic Aspects of Real Hyperelliptic Curves***Michael John Jacobson, Jr.*

The majority of work on hyperelliptic curve cryptography makes use of the so-called imaginary model of a hyperelliptic curve, in which the Jacobian, a finite abelian group, is used in a variety of protocols. The Mumford representation of divisors leads to a convenient representation of group elements with efficient arithmetic. The real model is in some sense more general than the imaginary model, as every imaginary hyperelliptic curve defined over a finite field with more than five elements is birationally equivalent to a real one over the same base field, whereas the converse is not true in general without extending the base field. However, the real model has not been as well-studied for cryptographic applications, because arithmetic in the Jacobian is thought to be more cumbersome and less efficient.

In this talk, I will give an overview of cryptographic applications using real hyperelliptic curves. The main theme behind this area is exploiting the so-called baby step operation in the infrastructure, which is faster than other general divisor operations. I will touch on the cryptographic protocols that have been proposed, recent improvements to arithmetic including explicit formulas for divisor arithmetic in genus 2, and advances in solving the infrastructure discrete logarithm problem, whose presumed intractability is the basis of security for the related cryptographic protocols.

**Boneh-Boyen signatures and the Strong Diffie-Hellman problem***David Jao*

The Boneh-Boyen digital signature scheme is a pairing based short signature scheme which is provably secure in the standard model under the $q$-Strong Diffie-Hellman assumption. In this work we show that, with very few exceptions, the private key in the scheme can be recovered in $O(p^{\frac{2}{5}+\varepsilon})$ time instead of the usual $O(\sqrt{p})$ time required for a discrete log, given access to a signature oracle. This improvement is achieved by proving that the security of the Boneh-Boyen scheme is equivalent to the intractability of the $q$-Strong Diffie-Hellman problem. We present implementation results comparing the performance of our recovery algorithm to generic discrete logarithm algorithms such as Pollard's lambda algorithm and Pollard's rho algorithm. We also discuss some possible countermeasures and strategies for mitigating the impact of these findings.

Joint work with Kayo Yoshida.

**Encryption from the Diffie-Hellman assumption***Eike Kiltz*

The most common public-key encryption scheme for elliptic-curve cryptography is the Diffie-Hellman integrated encryption standard (DHIES). (A hybrid variant of the ElGamal scheme.) Its security relies on the hardness of an *interactive* version of the Diffie-Hellman problem that is not very well studied. In this talk we discuss the "Twin ElGamal" encryption scheme, an alternative to DHIES with roughly the same efficiency but with provable security under the standard (non-interactive) Diffie-Hellman assumption.

**Fast Implementation of Elliptic Curve Cryptography and Pairing Computation for Sensor Networks***Julio Lopez*

The software implementation of public-key cryptography in wireless sensor networks (WSNs) is challenging due to the limited capabilities of the sensor nodes (low-power CPU, battery life, bandwidth and memory).In this talk, we present the results of our software implementation of elliptic curve cryptography (ECC) and pairing based cryptography (PBC) on two popular platforms, the ATmega128 (8-bit micro-processor) and the MSP430 (16-bit micro-processor). We will also describe fast algorithms for performing binary field arithmetic and their applications to point multiplication and eta-pairing computation.

**Asymmetric Pairings***Alfred Menezes*

Asymmetric pairings $e : G_1 \times G_2 \rightarrow G_T$ for which an efficiently-computable isomorphism $\psi : G_2 \rightarrow G_1$ is known are called Type~2 pairings; if such an isomorphism $\psi$ is not known, then $e$ is called a Type~3 pairing. (Type~1 pairings are the symmetric pairings derived from supersingular elliptic curves.) Research papers that present protocols using asymmetric pairings generally use Type~2 pairings instead of Type~3 pairings. We argue that Type~2 pairings are merely inefficient implementations of Type~3 pairings, and offer no benefit for protocols based on asymmetric pairings from the point of view of functionality, security, and performance.

**On Bounded Distance Decoding, Unique Shortest Vectors, and the Minimum Distance Problem***Daniele Micciancio (with Vadim Lyubashevsky)*

We prove the equivalence, up to a small polynomial approximation factor $\sqrt{n/\log n}$, of the lattice problems $\uSVP$ (unique Shortest Vector Problem), $\BDD$ (Bounded Distance Decoding) and $\GapSVP$ (the decision version of the Shortest Vector Problem). This resolves a long-standing open problem about the relationship between uSVP and the more standard $\GapSVP$, as well the $\BDD$ problem commonly used in coding theory. The main cryptographic application of our work is the proof that the Ajtai-Dwork and the Regev cryptosystems, which were previously only known to be based on the hardness of $\uSVP$, can be equivalently based on the hardness of worst-case GapSVP$_{O(n^{2.5})}$ and GapSVP$_{O(n^{2})}$, respectively. Also, in the case of $\uSVP$ and $\BDD$, our connection is very tight, establishing the equivalence (within a small constant approximation factor) between the two most central problems used in lattice based public key cryptography and coding theory.

**Generating Genus two Hyperelliptic Curves over Large Characteristic Finite Fields***Takakazu Satoh*

We describe an algorithm to generate genus two hyperelliptic curves verifiably at random in a certain family of curves which is suitable for hyperelliptic curve cryptography. The curves are simple but not absolutely simple. The non absolutely simpleness also enables us to compare the difficulty of the DLP on our curves to certain ECDLP's.

**Computing modular polynomials with the Chinese Remainder Theorem***Andrew Sutherland*

The classical modular polynomial &Phi_{n}(*X*,*Y*) parameterizes pairs of *n*-isogenous elliptic curves. These polynomials play a key role in many algorithms related to elliptic curves, but their large size, up to *O*(*n*^{3}log*n*) bits, makes computing them a challenge. We have a new algorithm to compute &Phi_{n}, for prime *n*, based on the CRT method. By selecting CRT moduli with special properties, we are able to exploit the structure of certain isogeny volcanoes to obtain a very efficient algorithm. Under the GRH its expected running time is *O*(*n*^{3}(log *n*)^{3}loglog *n*). It can be also used to compute &Phi_{n} mod *m* using just *O*(*n*^{2} log *mn*) space. The algorithm may be adapted to treat some other modular functions, including the Weber f-function, which can improve performance by a constant factor as large as 1728.

I will present details of the new algorithm, including computational results. For the classical modular polynomial we can readily handle *n* up to 5003, and we have computed modular polynomials for the Weber f-function with *n* as large as 50021. I will also discuss some constructive and destructive applications of these results to elliptic curve cryptography.

This is joint work with Reinier Bröker and Kristin Lauter.

**Special Guest Lecture:
Number Theory or Numerology?**