A Survey of Public-Key Cryptosystems
---
paper_title: A high security log-in procedure

paper_content:

The protection of time sharing systems from unauthorized users is often achieved by the use of passwords. By using one-way ciphers to code the passwords, the risks involved with storing the passwords in the computer can be avoided. We discuss the selection of a suitable one-way cipher and suggest that for this purpose polynomials over a prime modulus are superior to one-way ciphers derived from Shannon codes.
---
paper_title: A subexponential algorithm for discrete logarithms over the rational subgroup of the jacobians of large genus hyperelliptic curves over finite fields

paper_content:

There are well known subexponential algorithms for finding discrete logarithms over finite fields. However, the methods which underlie these algorithms do not appear to be easily adaptable for finding discrete logarithms in the groups associated with elliptic curves and the Jacobians of hyperelliptic curves. This has led to the development of cryptographic systems based on the discrete logarithm problem for such groups [12, 7, 8]. In this paper a Subexponential algorithm is presented for finding discrete logarithms in the group of rational points on the Jacobians of large genus hyperelliptic curves over finite fields. We give a heuristic argument that under certain assumptions, there exists a c e ℜ>0 such that for all sufficiently large g e Z>0, for all odd primes p with log p ≤ (2g + 1).98, the algorithm computes discrete logarithms in the group of rational points on the Jacobian of a genus g hyperelliptic curve over GF(p) within expected time: Lp2g+1[1/2, c] where c ≤ 2.181.
---
paper_title: New Directions in Cryptography

paper_content:

Two kinds of contemporary developments in cryptography are examined. Widening applications of teleprocessing have given rise to a need for new types of cryptographic systems, which minimize the need for secure key distribution channels and supply the equivalent of a written signature. This paper suggests ways to solve these currently open problems. It also discusses how the theories of communication and computation are beginning to provide the tools to solve cryptographic problems of long standing.
---
paper_title: A method for obtaining digital signatures and public-key cryptosystems

paper_content:

An encryption method is presented with the novel property that publicly revealing an encryption key does not thereby reveal the corresponding decryption key. This has two important consequences: (1) Couriers or other secure means are not needed to transmit keys, since a message can be enciphered using an encryption key publicly revealed by the intented recipient. Only he can decipher the message, since only he knows the corresponding decryption key. (2) A message can be “signed” using a privately held decryption key. Anyone can verify this signature using the corresponding publicly revealed encryption key. Signatures cannot be forged, and a signer cannot later deny the validity of his signature. This has obvious applications in “electronic mail” and “electronic funds transfer” systems. A message is encrypted by representing it as a number M, raising M to a publicly specified power e, and then taking the remainder when the result is divided by the publicly specified product, n , of two large secret primer numbers p and q. Decryption is similar; only a different, secret, power d is used, where e * d ≡ 1(mod (p - 1) * (q - 1)). The security of the system rests in part on the difficulty of factoring the published divisor, n .
---
paper_title: Another Look at "Provable Security"

paper_content:

We give an informal analysis and critique of several typical "provable security" results. In some cases there are intuitive but convincing arguments for rejecting the conclusions suggested by the formal terminology and "proofs," whereas in other cases the formalism seems to be consistent with common sense. We discuss the reasons why the search for mathematically convincing theoretical evidence to support the security of public-key systems has been an important theme of researchers. However, we argue that the theorem-proof paradigm of theoretical mathematics is often of limited relevance here and frequently leads to papers that are confusing and misleading. Because our paper is aimed at the general mathematical public, it is self-contained and as jargon-free as possible.
---
paper_title: Relations among notions of security for public-key encryption schemes

paper_content:

We compare the relative strengths of popular notions of security for public key encryption schemes. We consider the goals of privacy and non-malleability, each under chosen plaintext attack and two kinds of chosen ciphertext attack. For each of the resulting pairs of definitions we prove either an implication (every scheme meeting one notion must meet the other) or a separation (there is a scheme meeting one notion but not the other, assuming the first notion can be met at all). We similarly treat plaintext awareness, a notion of security in the random oracle model. An additional contribution of this paper is a new definition of non-malleability which we believe is simpler than the previous one.
---
paper_title: On the Importance of Checking Cryptographic Protocols for Faults

paper_content:

We present a theoretical model for breaking various cryptographic schemes by taking advantage of random hardware faults. We show how to attack certain implementations of RSA and Rabin signatures. We also show how various authentication protocols, such as Fiat-Shamir and Schnorr, can be broken using hardware faults.
---
paper_title: Chosen ciphertext attacks against protocols based on the RSA encryption standard

paper_content:

This paper introduces a new adaptive chosen ciphertext attack against certain protocols based on RSA. We show that an RSA private-key operation can be performed if the attacker has access to an oracle that, for any chosen ciphertext, returns only one bit telling whether the ciphertext corresponds to some unknown block of data encrypted using PKCS #1. An example of a protocol susceptible to our attack is SSL V.3.0.
---
paper_title: Differential power analysis

paper_content:

Cryptosystem designers frequently assume that secrets will be manipulated in closed, reliable computing environments. Unfortunately, actual computers and microchips leak information about the operations they process. This paper examines specific methods for analyzing power consumption measurements to find secret keys from tamper resistant devices. We also discuss approaches for building cryptosystems that can operate securely in existing hardware that leaks information.
---
paper_title: Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems

paper_content:

By carefully measuring the amount of time required tm perform private key operalions, attackers may be able to find fixed Diffie-Hellman exponents, factor RSA keys, and break other cryptosystems. Against, a valnerable system, the attack is computationally inexpensive and often requires only known ciphertext. Actual systems are potentially at risk, including cryptographic tokens, network-based cryptosystems, and other applications where attackers can make reasonably accurate timing measurements. Techniques for preventing the attack for RSA and Diffie-Hellman are presented. Some cryptosystems will need to be revised to protect against the attack, and new protocols and algorithms may need to incorporate measures to prevenl timing attacks.
---
paper_title: A method for obtaining digital signatures and public-key cryptosystems

paper_content:

An encryption method is presented with the novel property that publicly revealing an encryption key does not thereby reveal the corresponding decryption key. This has two important consequences: (1) Couriers or other secure means are not needed to transmit keys, since a message can be enciphered using an encryption key publicly revealed by the intented recipient. Only he can decipher the message, since only he knows the corresponding decryption key. (2) A message can be “signed” using a privately held decryption key. Anyone can verify this signature using the corresponding publicly revealed encryption key. Signatures cannot be forged, and a signer cannot later deny the validity of his signature. This has obvious applications in “electronic mail” and “electronic funds transfer” systems. A message is encrypted by representing it as a number M, raising M to a publicly specified power e, and then taking the remainder when the result is divided by the publicly specified product, n , of two large secret primer numbers p and q. Decryption is similar; only a different, secret, power d is used, where e * d ≡ 1(mod (p - 1) * (q - 1)). The security of the system rests in part on the difficulty of factoring the published divisor, n .
---
paper_title: Breaking RSA may not be equivalent to factoring

paper_content:

We provide evidence that breaking low-exponent RSA cannot be equivalent to factoring integers. We show that an algebraic reduction from factoring to breaking low-exponent RSA can be converted into an efficient factoring algorithm. Thus, in effect an oracle for breaking RSA does not help in factoring integers. Our result suggests an explanation for the lack of progress in proving that breaking rsa is equivalent to factoring. We emphasize that our results do not expose any specific weakness in the rsa system.
---
paper_title: Factoring Large Numbers with the TWIRL Device

paper_content:

The security of the RSA cryptosystem depends on the difficulty of factoring large integers. The best current factoring algorithm is the Number Field Sieve (NFS), and its most difficult part is the sieving step. In 1999 a large distributed computation involving hundreds of workstations working for many months managed to factor a 512-bit RSA key, but 1024-bit keys were believed to be safe for the next 15-20 years. In this paper we describe a new hardware implementation of the NFS sieving step (based on standard 0.13μm, 1GHz silicon VLSI technology) which is 3-4 orders of magnitude more cost effective than the best previously published designs (such as the optoelectronic TWINKLE and the mesh-based sieving). Based on a detailed analysis of all the critical components (but without an actual implementation), we believe that the NFS sieving step for 512-bit RSA keys can be completed in less than ten minutes by a $10K device. For 1024-bit RSA keys, analysis of the NFS parameters (backed by experimental data where possible) suggests that sieving step can be completed in less than a year by a $10 M device. Coupled with recent results about the cost of the NFS matrix step, this raises some concerns about the security of this key size.
---
paper_title: Solving simultaneous modular equations of low degree

paper_content:

We consider the problem of solving systems of equations $P_i (x) \equiv 0(\bmod n_i )i = 1 \cdots k$ where $P_i $ are polynomials of degree d and the $n_i $ are distinct relatively prime numbers and $x {{d(d + 1)} / 2}$ we can recover x in polynomial time provided $\min (n_i ) > 2^{d^2 } $. As a consequence the RSA cryptosystem used with a small exponent is not a good choice to use as a public-key cryptosystem in a large network. We also show that a protocol by Broder and Dolev [Proceedings on the 25th Annual IEEE Symposium on the Foundations of Computer Science, 1984] is insecure if RSA with a small exponent is used.
---
paper_title: Breaking iterated knapsacks

paper_content:

This paper presents an outline of an attack that we have used successfully to break iterated knapsacks. Although we do not provide a proof that the attack almost always works, we do provide some heuristic arguments. We also give a detailed description of the examples we have broken.
---
paper_title: A knapsack-type public key cryptosystem based on arithmetic in finite fields

paper_content:

We introduce a new knapsack type public key cryptosystem. The system is based on a novel application of arithmetic in finite fields, following a construction by Bose and Chowla. Appropriately choosing the parameters, we can control the density of the resulting knapsack. In particular, the density can be made high enough to foil “low density” attacks against our system. At the moment, we do not know of any attacks capable of “breaking” this system in a reasonable amount of time.
---
paper_title: A polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystem

paper_content:

The cryptographic security of the Merkle-Hellman cryptosystem has been a major open problem since 1976. In this paper we show that the basic variant of this cryptosystem, in which the elements of the public key are modular multiples of a superincreasing sequence, is breakable in polynomial time.
---
paper_title: Cryptanalysis of the Chor—Rivest Cryptosystem

paper_content:

Knapsack-based cryptosystems used to be popular in the beginning of public key cryptography before being all broken, all but the Chor-Rivest cryptosystem. In this paper, we show how to break this one with its suggested parameters: GF(p 24 ) and GF(256 25 ). We also give direction on possible extensions of our attack.
---
paper_title: Aspects of Hyperelliptic Curves over Large Prime Fields in Software Implementations

paper_content:

We present an implementation of elliptic curves and of hyperelliptic curves of genus 2 and 3 over prime fields. To achieve a fair comparison between the different types of groups, we developed an ad-hoc arithmetic library, designed to remove most of the overheads that penalize implementations of curve-based cryptography over prime fields. These overheads get worse for smaller fields, and thus for larger genera for a fixed group size. We also use techniques for delaying modular reductions to reduce the amount of modular reductions in the formulae for the group operations.
---
paper_title: Cryptanalysis: a survey of recent results

paper_content:

Cryptosystems are tested by subjecting them to cryptanalytic attacks by experts. Most of the cryptosystems that have been publicly proposed in the last decade have been broken. Some of the attacks that have been used are outlined, and some of the basic tools available to the cryptanalyst are explained. Attacks on the knapsack cryptosystems, congruential generators, and a variety of two key secrecy and signature schemes are discussed. There is also a brief discussion of the status of the security of cryptosystems for which there is no known feasible attack, such as the RSA, discrete exponentiation, and DES cryptosystems. >
---
paper_title: Hiding information and signatures in trapdoor knapsacks

paper_content:

The knapsack problem is an NP-complete combinatorial problem that is strongly believed to be computationally difficult to solve in general. Specific instances of this problem that appear very difficult to solve unless one possesses "trapdoor information" used in the design of the problem are demonstrated. Because only the designer can easily solve problems, others can send him information hidden in the solution to the problems without fear that an eavesdropper will be able to extract the information. This approach differs from usual cryptographic systems in that a secret key is not needed. Conversely, only the designer can generate signatures for messages, but anyone can easily check their authenticity.
---
paper_title: An improved algorithm for computing logarithms over GF(p) and its cryptographic significance (Corresp.)

paper_content:

A cryptographic system is described which is secure if and only if computing logarithms over GF(p) is infeasible. Previously published algorithms for computing this function require O(p^{1/2}) complexity in both time and space. An improved algorithm is derived which requires O =(\log^{2} p) complexity if p - 1 has only small prime factors. Such values of p must be avoided in the cryptosystem. Constructive uses for the new algorithm are also described.
---
paper_title: New Directions in Cryptography

paper_content:

Two kinds of contemporary developments in cryptography are examined. Widening applications of teleprocessing have given rise to a need for new types of cryptographic systems, which minimize the need for secure key distribution channels and supply the equivalent of a written signature. This paper suggests ways to solve these currently open problems. It also discusses how the theories of communication and computation are beginning to provide the tools to solve cryptographic problems of long standing.
---
paper_title: The Relationship Between Breaking the Diffie-Hellman Protocol and Computing Discrete Logarithms

paper_content:

Both uniform and nonuniform results concerning the security of the Diffie--Hellman key-exchange protocol are proved. First, it is shown that in a cyclic group G of order |G|=\prod{p_i^{e_i}}$, where all the multiple prime factors of |G| are polynomial in log|G|, there exists an algorithm that reduces the computation of discrete logarithms in G to breaking the Diffie--Hellman protocol in G and has complexity $\sqrt{\max\{\nu(p_i)\}}\cdot(\log|G|)^{O(1)}$, where $\nu(p)$ stands for the minimum of the set of largest prime factors of all the numbers d in the interval $[p-2\sqrt{p}+1,p+2\sqrt{p}+1]$. Under the unproven but plausible assumption that $\nu(p)$ is polynomial in log p, this reduction implies that the Diffie--Hellman problem and the discrete logarithm problem are polynomial-time equivalent in G. Second, it is proved that the Diffie--Hellman problem and the discrete logarithm problem are equivalent in a uniform sense for groups whose orders belong to certain classes: there exists a polynomial-time reduction algorithm that works for all those groups. Moreover, it is shown that breaking the Diffie--Hellman protocol for a small but nonnegligible fraction of the instances is equally difficult as breaking it for all instances. Finally, efficient constructions of groups are described for which the algorithm reducing the discrete logarithm problem to the Diffie--Hellman problem is efficiently constructible.
---
paper_title: Discrete logarithms in gf(p) using the number field sieve

paper_content:

Recently, several algorithms using number field sieves have been given to factor a number n in heuristic expected time $L_n [1/3; c]$, where \[ L_n [ v ;c ] = \exp \left\{ ( c + o ( 1 ) ) ( \log n )^v ( \log \log n )^{1 - v } \right\} \] for $n \to \infty $.This paper presents an algorithm to solve the discrete logarithm problem for $GF ( p )$ with heuristic expected running time $L_p [ 1/3; 3^{2/3}]$. For umbers of a special form, there is an asymptotically slower but more practical version of the algorithm.
---
paper_title: Elliptic Curve Cryptosystems

paper_content:

We discuss analogs based on elliptic curves over finite fields of public key cryptosystems which use the multiplicative group of a finite field. These elliptic curve cryptosystems may be more secure, because the analog of the discrete logarithm problem on elliptic curves is likely to be harder than the classical discrete logarithm problem, especially over GF(2'). We discuss the question of primitive points on an elliptic curve modulo p, and give a theorem on nonsmoothness of the order of the cyclic subgroup generated by a global point.
---
paper_title: A subexponential algorithm for discrete logarithms over the rational subgroup of the jacobians of large genus hyperelliptic curves over finite fields

paper_content:

There are well known subexponential algorithms for finding discrete logarithms over finite fields. However, the methods which underlie these algorithms do not appear to be easily adaptable for finding discrete logarithms in the groups associated with elliptic curves and the Jacobians of hyperelliptic curves. This has led to the development of cryptographic systems based on the discrete logarithm problem for such groups [12, 7, 8]. In this paper a Subexponential algorithm is presented for finding discrete logarithms in the group of rational points on the Jacobians of large genus hyperelliptic curves over finite fields. We give a heuristic argument that under certain assumptions, there exists a c e ℜ>0 such that for all sufficiently large g e Z>0, for all odd primes p with log p ≤ (2g + 1).98, the algorithm computes discrete logarithms in the group of rational points on the Jacobian of a genus g hyperelliptic curve over GF(p) within expected time: Lp2g+1[1/2, c] where c ≤ 2.181.
---
paper_title: The Arithmetic of Elliptic Curves

paper_content:

Algebraic Varieties.- Algebraic Curves.- The Geometry of Elliptic Curves.- The Formal Group of Elliptic Curves.- Elliptic Curves over Finite Fields.- Elliptic Curves over C.- Elliptic Curves over Local Fields.- Elliptic Curves over Global Fields.- Integral Points on Elliptic Curves.-Computing the Mordell Weil Group.- Appendix A: Elliptic Curves in Characteristics.-Appendix B: Group Cohomology (H0 and H1).
---
paper_title: The Improbability That an Elliptic Curve Has Subexponential Discrete Log Problem under the Menezes—Okamoto—Vanstone Algorithm

paper_content:

The security of elliptic curve cryptosystems is based on the presumed intractability of the discrete logarithm problem on the curve. Other than algorithms that work in an arbitrary group and are exponential in the general case, the only general-purpose algorithm that has ever been proposed for the elliptic curve discrete logarithm is that of Menezes--Okamoto--Vanstone (MOV). The MOV algorithm, which embeds an elliptic curve group of prime order l in the multiplicative group of a field F qk, is subexponential only under special circumstances, however. In this paper we first prove that, under a mild condition that always holds in practical applications, the condition that l|(q k -1) , which is obviously necessary for realizing the MOV algorithm, is also sufficient. We next give an improved upper bound for the frequency of occurrence of pairs of primes l, p such that l|(p k -1) for k small, where l is in the Hasse interval $[p+1-2\sqrt{p},p+1+2\sqrt{p}]$ .
---
paper_title: Fast evaluation of logarithms in fields of characteristic two

paper_content:

A method for determining logarithms in GF (2^{n}) is presented. Its asymptotic running time is O(\exp (cn^{1/3} \log^{2/3} n)) for a small constant c , while, by comparison, Adleman's scheme runs in time O(\exp (c^{'}n^{1/2} \log^{1/2} n )) . The ideas give a dramatic improvement even for moderate-sized fields such as GF (2^{127}) , and make (barely) possible computations in fields of size around 2^{400} . The method is not applicable to GF (q) for a large prime q .
---
paper_title: Constructive and destructive facets of Weil descent on elliptic curves

paper_content:

In this paper we look in detail at the curves which arise in the method of Galbraith and Smart for producing curves in the Weil restriction of an elliptic curve over a finite field of characteristic 2 of composite degree. We explain how this method can be used to construct hyperelliptic cryptosystems which could be as secure as cryptosystems based on the original elliptic curve. On the other hand, we show that the same technique may provide a way of attacking the original elliptic curve cryptosystem using recent advances in the study of the discrete logarithm problem on hyperelliptic curves. ::: ::: We examine the resulting higher genus curves in some detail and propose an additional check on elliptic curve systems defined over fields of characteristic 2 so as to make them immune from the methods in this paper.
---
paper_title: A Remark Concerning m-Divisibility and the Discrete Logarithm in the Divisor Class Group of Curves

paper_content:

The aim of this paper is to show that the computation of the discrete logarithm in the m-torsion part of the divisor class group of a curve X over a finite field ko (with char(ko) prime to m), or over a local field k with residue field ko, can be reduced to the computation of the discrete logarithm in k0(4m)* . For this purpose we use a variant of the (tame) Tate pairing for Abelian varieties over local fields. In the same way the problem to determine all linear combinations of a finite set of elements in the divisor class group of a curve over k or ko which are divisible by m is reduced to the computation of the discrete logarithm in ko(Cm)* -
---
paper_title: Index calculus for abelian varieties and the elliptic curve discrete logarithm problem

paper_content:

We propose an index calculus algorithm for the discrete logarithm problem on gen- eral abelian varieties. The main difference with the previous approaches is that we do not make use of any embedding into the Jacobian of a well-suited curve. We apply this algorithm to the Weil restriction of elliptic curves and hyperelliptic curves over small degree extension fields. In particular, our attack can solve all elliptic curve discrete logarithm problems defined over Fq3 in time O(q 4/3 ), with a reasonably small constant; and an elliptic problem over Fq4 or a genus 2 problem over Fq2 in time O(q 3/2 ) with a larger constant.
---
paper_title: The GHS attack revisited

paper_content:

We generalize the Weil descent construction of the GHS attack to arbitrary Artin-Schreier extensions. We give a formula for the characteristic polynomial of Frobenius of the obtained curves and prove that the large cyclic factor of the input elliptic curve is not contained in the kernel of the composition of the conorm and norm maps. As an application we almost square the number of elliptic curves which succumb to the basic GHS attack, thereby weakening curves over F 2 155 further. We also discuss other possible extensions or variations of the GHS attack and conclude that they are not likely to yield further improvements.
---
paper_title: Speeding up Pollard's Rho Method for Computing Discrete Logarithms

paper_content:

In Pollard's rho method, an iterating function f is used to define a sequence (y i) by y i+1=f(y i) for i=0,1, 2,..., with some starting value y0. In this paper, we define and discuss new iterating functions for computing discrete logarithms with the rho method. We compare their performances in experiments with elliptic curve groups. Our experiments show that one of our newly defined functions is expected to reduce the number of steps by a factor of approximately 0.8, in comparison with Pollard's originally used function, and we show that this holds independently of the size of the group order. For group orders large enough such that the run time for precomputation can be neglected, this means a real-time speed-up of more than 1.2.
---
paper_title: Elliptic curve implementation of zero-knowledge blobs

paper_content:

In [2] the authors show how to construct the building blocks for perfect zero-knowledge proofs called "blobs" using the discrete log problem. Contrary to what they remark on p. 73 of [2], we argue that the Mordell group of an elliptic curve is more suitable than the multiplicative group of a finite field for the construction of a hard cryptographic suite of problems.
---
paper_title: The Discrete Logarithm Problem on Elliptic Curves of Trace One

paper_content:

In this short note we describe an elementary technique which leads to a linear algorithm for solving the discrete logarithm problem on elliptic curves of trace one. In practice the method described means that when choosing elliptic curves to use in cryptography one has to eliminate all curves whose group orders are equal to the order of the finite field.
---
paper_title: Analysis of the GHS Weil Descent Attack on the ECDLP over Characteristic Two Finite Fields of Composite Degree

paper_content:

In this paper, the authors analyze the Gaudry-Hess-Smart (GHS) Weil descent attack on the elliptic curve discrete logarithm problem (ECDLP) for elliptic curves defined over characteristic two finite fields of composite extension degree. For each such field F2N, where N is in [100,600], elliptic curve parameters are identified such that: (i) there should exist a cryptographically interesting elliptic curve E over F2N with these parameters; and (ii) the GHS attack is more efficient for solving the ECDLP in E(F2N) than for solving the ECDLP on any other cryptographically interesting elliptic curve over F2N. The feasibility of the GHS attack on the specific elliptic curves is examined over F2176, F2208, F2272, F2304 and F2368, which are provided as examples in the ANSI X9.62 standard for the elliptic curve signature scheme ECDSA. Finally, several concrete instances are provided of the ECDLP over F2N, N composite, of increasing difficulty; these resist all previously known attacks, but are within reach of the GHS attack.
---
paper_title: An improved algorithm for computing logarithms over GF(p) and its cryptographic significance (Corresp.)

paper_content:

A cryptographic system is described which is secure if and only if computing logarithms over GF(p) is infeasible. Previously published algorithms for computing this function require O(p^{1/2}) complexity in both time and space. An improved algorithm is derived which requires O =(\log^{2} p) complexity if p - 1 has only small prime factors. Such values of p must be avoided in the cryptosystem. Constructive uses for the new algorithm are also described.
---
paper_title: Reducing elliptic curve logarithms to logarithms in a finite field

paper_content:

Abstruct- Elliptic cuwe cryptosystems have the potential to provide relatively small block size, high-security public key schemes that can be efficiently implemented. As with other known public key schemes, such as RSA and discrete exponentiation in a finite field, some care must be exercised when selecting the parameters involved, in this case the elliptic curve and the underlying field. Specific classes of cuwes that give little or no advantage over previously known schemes are discussed. The main result of the paper is to demonstrate the reduction of the elliptic curve logarithm problem to the logarithm problem in the multiplicative group of an extension of the underlying finite field. For the class of supersingular elliptic curves, the reduction takes probabilistic polynomial time, thus providing a probabilistic subexponential time algorithm for the former problem. Index Tem- Discrete logarithms, elliptic curves, public key CryPtOSraPhY.
---
paper_title: Elliptic Curve Discrete Logarithms and the Index Calculus

paper_content:

The discrete logarithm problem forms the basis of numerous cryptographic systems. The most effective attack on the discrete logarithm problem in the multiplicative group of a finite field is via the index calculus, but no such method is known for elliptic curve discrete logarithms. Indeed, Miller [23] has given a brief heuristic argument as to why no such method can exist. IN this note we give a detailed analysis of the index calculus for elliptic curve discrete logarithms, amplifying and extending miller's remarks. Our conclusions fully support his contention that the natural generalization of the index calculus to the elliptic curve discrete logarithm problem yields an algorithm with is less efficient than a brute-force search algorithm.
---
paper_title: The Improbability That an Elliptic Curve Has Subexponential Discrete Log Problem under the Menezes—Okamoto—Vanstone Algorithm

paper_content:

The security of elliptic curve cryptosystems is based on the presumed intractability of the discrete logarithm problem on the curve. Other than algorithms that work in an arbitrary group and are exponential in the general case, the only general-purpose algorithm that has ever been proposed for the elliptic curve discrete logarithm is that of Menezes--Okamoto--Vanstone (MOV). The MOV algorithm, which embeds an elliptic curve group of prime order l in the multiplicative group of a field F qk, is subexponential only under special circumstances, however. In this paper we first prove that, under a mild condition that always holds in practical applications, the condition that l|(q k -1) , which is obviously necessary for realizing the MOV algorithm, is also sufficient. We next give an improved upper bound for the frequency of occurrence of pairs of primes l, p such that l|(p k -1) for k small, where l is in the Hasse interval $[p+1-2\sqrt{p},p+1+2\sqrt{p}]$ .
---
paper_title: Discrete logarithms and local units

paper_content:

Let K be a number field and $\scr{O}\_{K}$ its ring of integers. Let l be a prime number and e a positive integer. We give a method to construct l$^{e}$th powers in $\scr{O}\_{K}$ using smooth algebraic integers. This method makes use of approximations of the l-adic logarithm to identify l$^{e}$th powers. One version we give is successful if the class number of K is not divisible by l and if the units in $\scr{O}\_{K}$ which are congruent to 1 modulo l$^{e+1}$ are l$^{e}$th powers. A second version only depends on Leopoldt's conjecture. We use the technique of constructing l$^{e}$th powers to find discrete logarithms in a finite field of prime order. Our method for computing discrete logarithms is closely modelled after Gordon's adaptation of the number field sieve to this problem. We conjecture that the expected running time of our algorithm is L$\_{p}$[1/3; (64/9)$^{1/3}$ + o(1)] for p $\rightarrow \infty $, where L$_{p}$[s;c] = exp (c (log q)$^{s}$ (log log q)$^{1-s}$). This is the same running time as is conjectured for the number field sieve factoring algorithm.
---
paper_title: Evaluation of discrete logarithms in a group of p-torsion points of an elliptic curve in characteristic p

paper_content:

We show that to solve the discrete log problem in a subgroup of order p of an elliptic curve over the finite field of characteristic p one needs O(ln p) operations in this field.
---
paper_title: Discrete logarithms in gf(p) using the number field sieve

paper_content:

Recently, several algorithms using number field sieves have been given to factor a number n in heuristic expected time $L_n [1/3; c]$, where \[ L_n [ v ;c ] = \exp \left\{ ( c + o ( 1 ) ) ( \log n )^v ( \log \log n )^{1 - v } \right\} \] for $n \to \infty $.This paper presents an algorithm to solve the discrete logarithm problem for $GF ( p )$ with heuristic expected running time $L_p [ 1/3; 3^{2/3}]$. For umbers of a special form, there is an asymptotically slower but more practical version of the algorithm.
---
paper_title: Constructing elliptic curves with given group order over large finite fields

paper_content:

A procedure is developed for constructing elliptic curves with given group order over large finite fields. The generality of the construction allows an arbitrary choice of the parameters involved. For instance, it is possible to specify the finite field, the group order or the class number of the endomorphism ring of the elliptic curve. This is important for various applications in computational number theory and cryptography. Moreover, we give a method that yields all representations of a given integer as a norm in an imaginary quadratic field.
---
paper_title: Building cyclic elliptic curves modulo large primes

paper_content:

Elliptic curves play an important role in many areas of modern cryptology such as integer factorization and primality proving. Moreover, they can be used in cryptosystems based on discrete logarithms for building one-way permutations. For the latter purpose, it is required to have cyclic elliptic curves over finite fields. The aim of this note is to explain how to construct such curves over a finite field of large prime cardinality, using the ECPP primality proving test of Atkin and Morain.
---
paper_title: An extension of Satoh's algorithm and its implementation

paper_content:

We describe a fast algorithm for counting points on elliptic curves defined over finite fields of small characteristic, following Satoh. Our main contribution is an extension to characteristics two and three. We give a detailed description with the optimisations necessary for an efficient implementation. Finally we give the number of points we have computed on a ``random'' curve defined over the field Fq with q=2^8009.
---
paper_title: A comparison and a combination of SST and AGM algorithms for counting points of elliptic curves in characteristic 2

paper_content:

Since the first use of a p-adic method for counting points of elliptic curves, by Satoh in 1999, several variants of his algorithm have been proposed. In the current state, the AGM algorithm, proposed by Mestre is thought to be the fastest in practice, and the algorithm by Satoh-Skjernaa-Taguchi has the best asymptotic complexity but requires precomputations. We present an amelioration of the SST algorithm, borrowing ideas from the AGM. We make a precise comparison between this modified SST algorithm and the AGM, thus demonstrating that the former is faster by a significant factor, even for small cryptographic sizes.
---
paper_title: Constructing Elliptic Curve Cryptosystems in Characteristic 2

paper_content:

Since the group of an elliptic curve defined over a finite field Fq, was proposed for Diffie-Hellman type cryptosystems in [7] and [15], some work on implementation has been done using special types of elliptic curves for which the order of the group is trivial to compute ([2], [13]). A consideration which discourages the use of an arbitrary elliptic curve is that one needs Schoof’s algorithm [16] to count the order of the corresponding group, and this algorithm, in addition to being rather complicated, has running time O(log9 q) for an elliptic curve defined over Fq. Thus, in applications of elliptic curves where one needs extremely large q — for example, the original version of the elliptic curve primality test ([4], [11]) — this algorithm is too time-consuming.
---
paper_title: Efficient Implementation of Schoof's Algorithm

paper_content:

Schoof's algorithm is used to find a secure elliptic curve for cryptosystems, as it can compute the number of rational points on a randomly selected elliptic curve defined over a finite field. By realizing efficient combination of several improvements, such as Atkin-Elkies's method, the isogeny cycles method, and trial search by match-and-sort techniques, we can count the number of rational points on an elliptic curve over GF(p) in a reasonable time, where p is a prime whose size is around 240-bits.
---
paper_title: Factoring Integers with Elliptic Curves

paper_content:

This paper is devoted to the description and analysis of a new algorithm to factor positive integers. It depends on the use of elliptic curves. The new method is obtained from Pollard's (p - 1)-method (Proc. Cambridge Philos. Soc. 76 (1974), 521-528) by replacing the multiplicative group by the group of points on a random elliptic curve. It is conjectured that the algorithm determines a non-trivial divisor of a composite number n in expected time at most K( p)(log n)2, where p is the least prime dividing n and K is a function for which log K(x) = /(2 + o(1))log x log log x for x -x o. In the worst case, when n is the product of two primes of the same order of magnitude, this is
---
paper_title: Elliptic curves over finite fields and the computation of square roots mod $p$

paper_content:

In this paper we present a deterministic algorithm to compute the number of F^-points of an elliptic curve that is defined over a finite field Fv and which is given by a Weierstrass equation. The algorithm takes 0(log9 q) elementary operations. As an application wc give an algorithm to compute square roots mod p. For fixed .i e Z, it takes 0(log9p) elementary operations to compute fx mod p. 1. Introduction. In this paper we present an algorithm to compute the number of F(/-points of an elliptic curve defined over a finite field F , which is given by a Weierstrass equation. We restrict ourselves to the case where the characteristic of F^ is not 2 or 3. The algorithm is deterministic, does not depend on any unproved hypotheses and takes 0(log9 0. If one applies fast multiplication techniques, the algorithm will take 0((|x|1/2log p)6+f) elementary operations for any e > 0. Let £ be an elliptic curve defined over the prime field Fp and let an affine model of it be given by a Weierstrass equation Y2 = X3 + AX + B (A,BeFp). An explicit formula for the number of F^-points on £ is given by
---
paper_title: Elliptic Curves in Cryptography

paper_content:

Preface 1. Introduction 2. Finite field arithmetic 3. Arithmetic on an elliptic curve 4. Efficient implementation of elliptic curves 5. The elliptic curve discrete logarithm problem 6. Determining the group order 7. Schoof's algorithm and extensions 8. Generating curves using complex multiplication 9. Other applications of elliptic curves 10. Hyperelliptic curves Appendix A. Curve examples Bibliography Author index Subject index.
---
paper_title: Quantum cryptography: Public key distribution and coin tossing

paper_content:

When elementary quantum systems, such as polarized photons, are used to transmit digital information, the uncertainty principle gives rise to novel cryptographic phenomena unachievable with traditional transmission media, e.g. a communications channel on which it is impossible in principle to eavesdrop without a high probability of disturbing the transmission in such a way as to be detected. Such a quantum channel can be used in conjunction with ordinary insecure classical channels to distribute random key information between two users with the assurance that it remains unknown to anyone else, even when the users share no secret information initially. We also present a protocol for coin-tossing by exchange of quantum messages, which is secure against traditional kinds of cheating, even by an opponent with unlimited computing power, but ironically can be subverted by use of a still subtler quantum phenomenon, the Einstein-Podolsky-Rosen paradox.
---
paper_title: Short Signatures from the Weil Pairing

paper_content:

We introduce a short signature scheme based on the Computational Diffie–Hellman assumption on certain elliptic and hyperelliptic curves. For standard security parameters, the signature length is about half that of a DSA signature with a similar level of security. Our short signature scheme is designed for systems where signatures are typed in by a human or are sent over a low-bandwidth channel. We survey a number of properties of our signature scheme such as signature aggregation and batch verification.
---
paper_title: A One Round Protocol for Tripartite Diffie–Hellman

paper_content:

In this paper we propose a three participants variation of the Diffie--Hellman protocol. This variation is based on the Weil and Tate pairings on elliptic curves, which were first used in cryptography as cryptanalytic tools for reducing the discrete logarithm problem on some elliptic curves to the discrete logarithm problem in a finite field.
---
paper_title: Identity-based encryption from the Weil pairing

paper_content:

We propose a fully functional identity-based encryption (IBE) scheme. The scheme has chosen ciphertext security in the random oracle model assuming a variant of the computational Diffie--Hellman problem. Our system is based on bilinear maps between groups. The Weil pairing on elliptic curves is an example of such a map. We give precise definitions for secure IBE schemes and give several applications for such systems.
---
paper_title: Quantum cryptography: Public key distribution and coin tossing

paper_content:

When elementary quantum systems, such as polarized photons, are used to transmit digital information, the uncertainty principle gives rise to novel cryptographic phenomena unachievable with traditional transmission media, e.g. a communications channel on which it is impossible in principle to eavesdrop without a high probability of disturbing the transmission in such a way as to be detected. Such a quantum channel can be used in conjunction with ordinary insecure classical channels to distribute random key information between two users with the assurance that it remains unknown to anyone else, even when the users share no secret information initially. We also present a protocol for coin-tossing by exchange of quantum messages, which is secure against traditional kinds of cheating, even by an opponent with unlimited computing power, but ironically can be subverted by use of a still subtler quantum phenomenon, the Einstein-Podolsky-Rosen paradox.
---
paper_title: An algorithm for solving the discrete log problem on hyperelliptic curves

paper_content:

We present an index-calculus algorithm for the computation of discrete logarithms in the Jacobian of hyperelliptic curves defined over finite fields. The complexity predicts that it is faster than the Rho method for genus greater than 4. To demonstrate the efficiency of our approach, we describe our breaking of a cryptosystem based on a curve of genus 6 recently proposed by Koblitz.
---
paper_title: A subexponential algorithm for discrete logarithms over the rational subgroup of the jacobians of large genus hyperelliptic curves over finite fields

paper_content:

There are well known subexponential algorithms for finding discrete logarithms over finite fields. However, the methods which underlie these algorithms do not appear to be easily adaptable for finding discrete logarithms in the groups associated with elliptic curves and the Jacobians of hyperelliptic curves. This has led to the development of cryptographic systems based on the discrete logarithm problem for such groups [12, 7, 8]. In this paper a Subexponential algorithm is presented for finding discrete logarithms in the group of rational points on the Jacobians of large genus hyperelliptic curves over finite fields. We give a heuristic argument that under certain assumptions, there exists a c e ℜ>0 such that for all sufficiently large g e Z>0, for all odd primes p with log p ≤ (2g + 1).98, the algorithm computes discrete logarithms in the group of rational points on the Jacobian of a genus g hyperelliptic curve over GF(p) within expected time: Lp2g+1[1/2, c] where c ≤ 2.181.
---
paper_title: Hyperelliptic cryptosystems

paper_content:

In this paper we discuss a source of finite abelian groups suitable for cryptosystems based on the presumed intractability of the discrete logarithm problem for these groups. They are the jacobians of hyperelliptic curves defined over finite fields. Special attention is given to curves defined over the field of two elements. Explicit formulas and examples are given, and the problem of finding groups of almost prime order is discussed.
---
paper_title: A rigorous subexponential algorithm for computation of class groups

paper_content:

Let C(-d) denote the Gauss Class Group of quadratic forms of a negative discriminant -d (or equivalently, the class group of the imaginary quadratic field Q(A/=') ). We give a rigorous proof that there exists a Las Ve- gas algorithm that will compute the structure of C(-d) with an expected running time of L(d) vf2+?(1) bit operations, where L(d) = exp( Vlog d log log d) . Thus, of course, also includes the computation of the class number h(-d), the cardinality of C(-d) . IBM RESEARCH DIvISION, ALMADEN RESEARCH CENTER, K53/802, 650 HARRY ROAD, SAN JOSE, CALIFORNIA 95 120-6099 Current address (K. McCurley): Organization 1423, Sandia National Laboratories, Albuquerque, New Mexico 87185 This content downloaded from 207.46.13.180 on Thu, 08 Sep 2016 05:47:29 UTC All use subject to http://about.jstor.org/terms
---
paper_title: Aspects of Hyperelliptic Curves over Large Prime Fields in Software Implementations

paper_content:

We present an implementation of elliptic curves and of hyperelliptic curves of genus 2 and 3 over prime fields. To achieve a fair comparison between the different types of groups, we developed an ad-hoc arithmetic library, designed to remove most of the overheads that penalize implementations of curve-based cryptography over prime fields. These overheads get worse for smaller fields, and thus for larger genera for a fixed group size. We also use techniques for delaying modular reductions to reduce the amount of modular reductions in the formulae for the group operations.
---
paper_title: Hyperelliptic Curve Cryptosystems: Closing the Performance Gap to Elliptic Curves

paper_content:

For most of the time since they were proposed, it was widely believed that hyperelliptic curve cryptosystems (HECC) carry a substantial performance penalty compared to elliptic curve cryptosystems (ECC) and are, thus, not too attractive for practical applications. Only quite recently improvements have been made, mainly restricted to curves of genus 2. The work at hand advances the state-of-the-art considerably in several aspects. First, we generalize and improve the closed formulae for the group operation of genus 3 for HEC defined over fields of characteristic two. For certain curves we achieve over 50% complexity improvement compared to the best previously published results. Second, we introduce a new complexity metric for ECC and HECC defined over characteristic two fields which allow performance comparisons of practical relevance. It can be shown that the HECC performance is in the range of the performance of an ECC; for specific parameters HECC can even possess a lower complexity than an ECC at the same security level. Third, we describe the first implementation of a HEC cryptosystem on an embedded (ARM7) processor. Since HEC are particularly attractive for constrained environments, such a case study should be of relevance.
---
paper_title: Index Calculus Attack for Hyperelliptic Curves of Small Genus

paper_content:

We present a variation of the index calculus attack by Gaudry which can be used to solve the discrete logarithm problem in the Jacobian of hyperelliptic curves. The new algorithm has a running time which is better than the original index calculus attack and the Rho method (and other square-root algorithms) for curves of genus > 3. We also describe another improvement for curves of genus > 4 (slightly slower, but less dependent on memory space) initially mentioned by Harley and used in a number of papers, but never analyzed in details.
---
paper_title: A key-exchange system based on imaginary quadratic fields

paper_content:

We describe another key-exchange system which, while based on the general idea of the well-known scheme of Diffie and Hellman, seems to be more secure than that technique. The new system is based on the arithmetic of an imaginary quadratic field, and makes use, specifically, of the properties of the class group of such a field.
---
paper_title: A key-exchange protocol using real quadratic fields

paper_content:

In 1976 Diffie and Hellman first introduced their well-known key-exchange protocol which is based on exponentiation in the multiplicative group GF(p)* of integers relatively prime to a large primep (see [8]). Since then, this scheme has been extended to numerous other finite groups. Recently, Buchmann and Williams [2] introduced a version of the Diffie-Hellman protocol which uses the infrastructure of a real quadratic field. Theirs is the first such system not to require an underlying group structure, but rather a structure which is "almost" like that of a group. We give here a more detailed description of this scheme as well as state the required algorithms and considerations for their implementation.
---
paper_title: Public-key cryptosystems based on cubic finite field extensions

paper_content:

The cryptographic properties of third-order linear feedback shift-register (LFSR) sequences over GF(p) are investigated. A fast computational algorithm for evaluating the kth term of a characteristic sequence of order 3 is presented. Based on these properties, a new public-key distribution scheme and an RSA-type encryption algorithm are proposed. Their security, implementation, information rate, and computational cost for the new schemes are discussed.
---
paper_title: The XTR Public Key System

paper_content:

This paper introduces the XTR public key system. XTR is based on a new method to represent elements of a subgroup of a multiplicative group of a finite field. Application of XTR in cryptographic protocols leads to substantial savings both in communication and computational overhead without compromising security.
---
paper_title: Evidence that XTR Is More Secure than Supersingular Elliptic Curve Cryptosystems

paper_content:

We show that finding an efficiently computable injective homomorphism from the XTR subgroup into the group of points over GF(p2) of a particular type of supersingular elliptic curve is at least as hard as solving the Diffie–Hellman problem in the XTR subgroup. This provides strong evidence for a negative answer to the question posed by Vanstone and Menezes at the Crypto 2000 Rump Session on the possibility of efficiently inverting the MOV embedding into the XTR subgroup. As a side result we show that the Decision Diffie–Hellman problem in the group of points on this type of supersingular elliptic curves is efficiently computable, which provides an example of a group where the Decision Diffie–Hellman problem is simple, while the Diffie–Hellman and discrete logarithm problems are presumably not. So-called distortion maps on groups of points on elliptic curves that play an important role in our cryptanalysis also lead to cryptographic applications of independent interest. These applications are an improvement of Joux’s one round protocol for tripartite Diffie–Hellman key exchange and a non-refutable digital signature scheme that supports escrowable encryption. We also discuss the applicability of our methods to general elliptic curves defined over finite fields which includes a classification of elliptic curve groups where distortion maps exist.
---
paper_title: Reducing elliptic curve logarithms to logarithms in a finite field

paper_content:

Abstruct- Elliptic cuwe cryptosystems have the potential to provide relatively small block size, high-security public key schemes that can be efficiently implemented. As with other known public key schemes, such as RSA and discrete exponentiation in a finite field, some care must be exercised when selecting the parameters involved, in this case the elliptic curve and the underlying field. Specific classes of cuwes that give little or no advantage over previously known schemes are discussed. The main result of the paper is to demonstrate the reduction of the elliptic curve logarithm problem to the logarithm problem in the multiplicative group of an extension of the underlying finite field. For the class of supersingular elliptic curves, the reduction takes probabilistic polynomial time, thus providing a probabilistic subexponential time algorithm for the former problem. Index Tem- Discrete logarithms, elliptic curves, public key CryPtOSraPhY.
---
paper_title: NTRU: A Ring-Based Public Key Cryptosystem

paper_content:

We describe NTRU, a new public key cryptosystem. NTRU features reasonably short, easily created keys, high speed, and low memory requirements. NTRU encryption and decryption use a mixing system suggested by polynomial algebra combined with a clustering principle based on elementary probability theory. The security of the NTRU cryptosystem comes from the interaction of the polynomial mixing system with the independence of reduction modulo two relatively prime integers p and q.
---
paper_title: Lattice attacks on NTRU

paper_content:

NTRU is a new public key cryptosystem proposed at Crypto 96 by Hoffstein, Pipher and Silverman from the Mathematics department of Brown University. It attracted considerable attention, and is being advertised over the Internet by NTRU Cryptosystems. Its security is based on the difficulty of analyzing the result of polynomial arithmetic modulo two unrelated moduli, and its correctness is based on clustering properties of the sums of random variables. In this paper, we apply new lattice basis reduction techniques to cryptanalyze the scheme, to discover either the original secret key, or an alternative secret key which is equally useful in decoding the ciphertexts.
---
paper_title: W.: The impact of decryption failures on the security of ntru encryption

paper_content:

NTRUEncrypt is unusual among public-key cryptosystems in that, with standard parameters, validly generated ciphertexts can fail to decrypt. This affects the provable security properties of a cryptosystem, as it limits the ability to build a simulator in the random oracle model without knowledge of the private key. We demonstrate attacks which use decryption failures to recover the private key. Such attacks work for all standard parameter sets, and one of them applies to any padding. The appropriate countermeasure is to change the parameter sets and possibly the decryption process so that decryption failures are vanishingly unlikely, and to adopt a padding scheme that prevents an attacker from directly controlling any part of the input to the encryption primitive. We outline one such candidate padding scheme.
---
paper_title: NSS: An NTRU lattice-based signature scheme

paper_content:

A new authentication and digital signature scheme called the NTRU Signature Scheme (NSS) is introduced. NSS provides an authentication/signature method complementary to the NTRU public key cryptosystem. The hard lattice problem underlying NSS is similar to the hard problem underlying NTRU, and NSS similarly features high speed, low footprint, and easy key creation.
---
paper_title: A public key cryptosystem based on the word problem

paper_content:

The undecidable word problem for groups and semigroups is investigated as a basis for a public-key cryptosystem. A specific approach is discussed along with the results of an experimental implementation This approach does not give a provably secure or practical system, but shows the type of cryptosystem that could be constructed around the word problem. This cryptosystem is randomized, with infinitely many ciphertexts corresponding to each plaintext.
---
paper_title: Braids, Links, and Mapping Class Groups.

paper_content:

The central theme of this study is Artin's braid group and the many ways that the notion of a braid has proved to be important in low-dimensional topology. In Chapter 1 the author is concerned with the concept of a braid as a group of motions of points in a manifold. She studies structural and algebraic properties of the braid groups of two manifolds, and derives systems of defining relations for the braid groups of the plane and sphere. In Chapter 2 she focuses on the connections between the classical braid group and the classical knot problem. After reviewing basic results she proceeds to an exploration of some possible implications of the Garside and Markov theorems. Chapter 3 offers discussion of matrix representations of the free group and of subgroups of the automorphism group of the free group. These ideas come to a focus in the difficult open question of whether Burau's matrix representation of the braid group is faithful. Chapter 4 is a broad view of recent results on the connections between braid groups and mapping class groups of surfaces. Chapter 5 contains a brief discussion of the theory of "plats." Research problems are included in an appendix.
---
paper_title: Cryptanalysis of the Matsumoto and Imai Public Key Scheme of Eurocrypt’88

paper_content:

In [1] Matsumoto and Imai have developed a new public key scheme for enciphering or signing. (This scheme is completely different and should not be mistaken with another scheme of Matsumoto and Imai developed in 1983 and broken at Eurocrypt'84).No attacks have been published as yet for this scheme. However we will see in this paper that for almost all the keys almost each cleartext can be found from his ciphertext after only about m2n4 log n computations where m is the degree of the field K chosen, and where mn is the number of bits of the text.Moreover for absolutely all the keys that give a practical size for the messages it will be possible to find almost all the cleartexts from the corresponding ciphertexts after a feasible computation.So the algorithm of [1] is insecure.
---
paper_title: Cryptanalysis of Polly Cracker

paper_content:

An attack on the public key cryptosystem Polly Cracker is described, that reveals the complete secret key /spl sigma/ /spl isin/ F/sub q//sup n/ by means of n (nonadaptively) chosen "fake" ciphertexts.
---
paper_title: Asymmetric Cryptography with a Hidden Monomial

paper_content:

In [1]T. Matsumoto and H. Imai have presented a very efficient, "candidate" algorithm, called C*, for asymmetric cryptography. This algorithm was broken in [2]. Then in [3], I have suggested two algorithms, HFE and IP, to repair C*. However the secret key computations of HFE and IP are not as efficient as in the original algorithm C*. IS it possible to repair C* with the same kind of very easy secret key computations? This question is the subject of this paper. Unfortunately, we will see that for all the "easy" transformations of C* the answer is no. However one of the new ideas of this paper will enable us to suggest a candidate algorithm for assymetric signatures of length only 64 bits. An extended version of this paper can be obtained from the author.
---
paper_title: Quantum Cryptography, or Unforgeable Subway Tokens

paper_content:

The use of quantum mechanical systems, such as polarized photons, to record information gives rise to novel cryptographic phenomena, not achievable with classical recording media: 1) A Verify Only Memory (VOM) that, with high probability, cannot be read or copied by someone ignorant of its contents; 2) the multiplexing of two messages in such a way that, with high probability, either message may be recovered at the cost of irreversibly destroying the other.
---
paper_title: Quantum cryptography: Public key distribution and coin tossing

paper_content:

When elementary quantum systems, such as polarized photons, are used to transmit digital information, the uncertainty principle gives rise to novel cryptographic phenomena unachievable with traditional transmission media, e.g. a communications channel on which it is impossible in principle to eavesdrop without a high probability of disturbing the transmission in such a way as to be detected. Such a quantum channel can be used in conjunction with ordinary insecure classical channels to distribute random key information between two users with the assurance that it remains unknown to anyone else, even when the users share no secret information initially. We also present a protocol for coin-tossing by exchange of quantum messages, which is secure against traditional kinds of cheating, even by an opponent with unlimited computing power, but ironically can be subverted by use of a still subtler quantum phenomenon, the Einstein-Podolsky-Rosen paradox.
---
paper_title: Modern Cryptography : Theory and Practice

paper_content:

Many cryptographic schemes and protocols, especially those based on public-keycryptography, have basic or so-called "textbook crypto" versions, as these versionsare usually the subjects for many textbooks on cryptography. This book takes adifferent approach to introducing cryptography: it pays much more attention tofit-for-application aspects of cryptography. It explains why "textbook crypto" isonly good in an ideal world where data are random and bad guys behave nicely.It reveals the general unfitness of "textbook crypto" for the real world by demonstratingnumerous attacks on such schemes, protocols and systems under variousreal-world application scenarios. This book chooses to introduce a set of practicalcryptographic schemes, protocols and systems, many of them standards or de factoones, studies them closely, explains their working principles, discusses their practicalusages, and examines their strong (i.e., fit-for-application) security properties, oftenwith security evidence formally established. The book also includes self-containedtheoretical background material that is the foundation for modern cryptography.
---
paper_title: Prime Numbers: A Computational Perspective

paper_content:

Prime numbers beckon to the beginner, the basic notion of primality being accessible to a child. Yet, some of the simplest questions about primes have stumped humankind for millennia. In this book, the authors concentrate on the computational aspects of prime numbers, such as recognizing primes and discovering the fundamental prime factors of a given number. Over 100 explicit algorithms cast in detailed pseudocode are included in the book. Applications and theoretical digressions serve to illuminate, justify, and underscore the practical power of these algorithms. The 2nd edition adds new material on primality and algorithms and updates all the numerical records, such as the largest prime, etc. It has been revised throughout.
---
paper_title: Guide to Elliptic Curve Cryptography

paper_content:

Elliptic curves also figured prominently in the recent proof of Fermat's Last Theorem by Andrew Wiles. Originally pursued for purely aesthetic reasons, elliptic curves have recently been utilized in devising algorithms for factoring integers, primality proving, and in public-key cryptography. In this article, we aim to give the reader an introduction to elliptic curve cryptosystems, and to demonstrate why these systems provide relatively small block sizes, high-speed software and hardware implementations, and offer the highest strength-per-key-bit of any known public-key scheme.
---
paper_title: Elliptic Curves: Number Theory and Cryptography

paper_content:

INTRODUCTION THE BASIC THEORY Weierstrass Equations The Group Law Projective Space and the Point at Infinity Proof of Associativity Other Equations for Elliptic Curves Other Coordinate Systems The j-Invariant Elliptic Curves in Characteristic 2 Endomorphisms Singular Curves Elliptic Curves mod n TORSION POINTS Torsion Points Division Polynomials The Weil Pairing The Tate-Lichtenbaum Pairing Elliptic Curves over Finite Fields Examples The Frobenius Endomorphism Determining the Group Order A Family of Curves Schoof's Algorithm Supersingular Curves The Discrete Logarithm Problem The Index Calculus General Attacks on Discrete Logs Attacks with Pairings Anomalous Curves Other Attacks Elliptic Curve Cryptography The Basic Setup Diffie-Hellman Key Exchange Massey-Omura Encryption ElGamal Public Key Encryption ElGamal Digital Signatures The Digital Signature Algorithm ECIES A Public Key Scheme Based on Factoring A Cryptosystem Based on the Weil Pairing Other Applications Factoring Using Elliptic Curves Primality Testing Elliptic Curves over Q The Torsion Subgroup: The Lutz-Nagell Theorem Descent and the Weak Mordell-Weil Theorem Heights and the Mordell-Weil Theorem Examples The Height Pairing Fermat's Infinite Descent 2-Selmer Groups Shafarevich-Tate Groups A Nontrivial Shafarevich-Tate Group Galois Cohomology Elliptic Curves over C Doubly Periodic Functions Tori Are Elliptic Curves Elliptic Curves over C Computing Periods Division Polynomials The Torsion Subgroup: Doud's Method Complex Multiplication Elliptic Curves over C Elliptic Curves over Finite Fields Integrality of j-Invariants Numerical Examples Kronecker's Jugendtraum DIVISORS Definitions and Examples The Weil Pairing The Tate-Lichtenbaum Pairing Computation of the Pairings Genus One Curves and Elliptic Curves Equivalence of the Definitions of the Pairings Nondegeneracy of the Tate-Lichtenbaum Pairing ISOGENIES The Complex Theory The Algebraic Theory Velu's Formulas Point Counting Complements Hyperelliptic Curves Basic Definitions Divisors Cantor's Algorithm The Discrete Logarithm Problem Zeta Functions Elliptic Curves over Finite Fields Elliptic Curves over Q Fermat's Last Theorem Overview Galois Representations Sketch of Ribet's Proof Sketch of Wiles's Proof APPENDIX A: NUMBER THEORY APPENDIX B: GROUPS APPENDIX C: FIELDS APPENDIX D: COMPUTER packages REFERENCES INDEX Exercises appear at the end of each chapter.
---
paper_title: Handbook of Applied Cryptography

paper_content:

From the Publisher: ::: A valuable reference for the novice as well as for the expert who needs a wider scope of coverage within the area of cryptography, this book provides easy and rapid access of information and includes more than 200 algorithms and protocols; more than 200 tables and figures; more than 1,000 numbered definitions, facts, examples, notes, and remarks; and over 1,250 significant references, including brief comments on each paper.
---
paper_title: A Course in Number Theory and Cryptography

paper_content:

1: Some Topics in Elementary Number Theory. 2: Finite Fields and Quadratic Residues. 3: Cryptography. 4: Public Key. 5: Primality and Factoring. 6: Elliptic Curves.
---
paper_title: Cryptography: Theory and Practice

paper_content:

From the Publisher: ::: The object of the book is to produce a general, comprehensive textbook that treats all the essential core areas of cryptography.
---

Title: A Survey of Public-Key Cryptosystems
Section 1: Introduction
Description 1: This section introduces the concept of public-key cryptography, describes its historical context, early developments, and various applications.

Section 2: Notions of Security
Description 2: This section explores different notions and aspects of security in public-key cryptosystems, including various attack vectors and their implications.

Section 3: RSA
Description 3: This section delves into the RSA cryptosystem, explaining its key components, how it works, and examining some of the attacks and defenses associated with it.

Section 4: Factorization attack on RSA
Description 4: This section focuses on methods of attacking RSA by factorizing its modulus, including a discussion of different factorization algorithms.

Section 5: Other algorithmic attacks on RSA
Description 5: This section covers additional attacks on RSA not based on factorization, such as exploiting implementation vulnerabilities and small exponent attacks.

Section 6: Side-channel attacks
Description 6: This section examines attacks that exploit information leaked during the execution of cryptosystems, such as power consumption and execution time.

Section 7: Deployment
Description 7: This section discusses the practical deployment of public-key cryptosystems, with a focus on SSL and the authentication mechanisms in secure web transactions.

Section 8: Knapsack
Description 8: This section describes the knapsack cryptosystem, its basic construction, and the types of attacks it has faced over the years.

Section 9: Discrete Logarithm Cryptosystems
Description 9: This section introduces cryptosystems based on the discrete logarithm problem, exploring examples like Diffie-Hellman key exchange and DSA.

Section 10: Elliptic Curve Cryptography
Description 10: This section covers elliptic curve cryptography, its mathematical foundations, and its advantages over other public-key cryptosystems.

Section 11: Other Systems Based on Discrete Logarithms
Description 11: This section discusses additional cryptosystems based on the discrete logarithm problem in different groups, such as hyperelliptic curves and class groups.

Section 12: NTRU
Description 12: This section outlines the NTRU cryptosystem, its design, strengths, weaknesses, and the various attacks it has endured.

Section 13: Cryptosystems Based on Other Algebraic Structures
Description 13: This section explores cryptosystems that rely on the intractability of problems in noncommutative algebra and commutative algebra, such as braid groups and Polly Cracker.

Section 14: Quantum Cryptography and Quantum Computation
Description 14: This section discusses quantum cryptography and the potential impact of quantum computing on classical cryptographic problems.

Section 15: Further Reading
Description 15: This section provides references to additional resources for readers interested in exploring algorithmic number theory and public-key cryptography in more depth.