International Association
for Cryptologic Research

Straight line factoring algorithms include a variant Lenstra's elliptic curve method. This note proves lower bounds on the length of straight line factoring algorithms.

Stange, generalizing Ward's elliptic divisibility sequences, introduced elliptic nets, and showed an equivalence between elliptic nets and elliptic curves. This note relates Stange's recursion for elliptic nets and the Coxeter group F4.

Bellare and Micciancio's MuHASH applies a pre-existing hash function to map indexed message blocks into a secure group. The resulting hash is the product. Bellare and Micciancio proved, in the random oracle model, that MuHASH is collision-resistant if the group's discrete logarithm problem is infeasible. MuHASH, however, relies on a pre-existing hash being collision resistant. In this paper, we remove such a reliance by replacing the pre-existing hash with a block cipher under a fixed key. We adapt Bellare and Micciancio's collision-resistance proof to the ideal cipher model. Preimage resistance requires us to add a further modification.

A theoretical approach for integer factoring using complex analysis is to apply Newton's method on an analytic function whose zeros, within in a certain strip, correspond to factors of a given integer. A few successful toy experiments of factoring small numbers with this approach, implemented in a naive manner that amounts to complexified trial division, show that, at least for small numbers, Newton's method finds the requisite zeros, at least some of time (factors of nearby numbers were also sometimes found). Nevertheless, some heuristic arguments predict that this approach will be infeasible for factoring numbers of the size currently used in cryptography.

The one-up problem is defined for any group and a function from the group to integers. An instance of problem consists of two points in the group. A solution consists of another point satisfying an equation involving the group and the function. The one-up problem must be hard for the security of (EC)DSA. Heuristic arguments are given for the independence of the discrete log and one-up problems. DSA and ECDSA are conjectured to be secure if the discrete log and one-up problems are hard and the hash is collision resistant.

In a key retrieval scheme, a human user interacts with a client computer to retrieve a key. A scheme is user-sure if any adversary without access to the the user cannot distinguish the retrieved key from a random key. A scheme is user-safe if any adversary without access to the client's keys, or simultaneous user and client access, cannot exploit the user to distinguish the retrieved key from a random key. A multiple-round key retrieval scheme, where the user is given informative prompts to which the user responds, is proved to be user-sure and user-safe. Remote key retrieval involves a keyless client and a remote, keyed server. User-sure and user-safe are defined similarly for remote key retrieval. The scheme is user-anonymous if the server cannot identify the user. A remote version of the multiple-round key retrieval scheme is proved to be user-sure, user-safe and user-anonymous.

An elliptic curve random number generator (ECRNG) has been approved in a NIST standards and proposed for ANSI and SECG draft standards. This paper proves that, if three conjectures are true, then the ECRNG is secure. The three conjectures are hardness of the elliptic curve decisional Diffie-Hellman problem and the hardness of two newer problems, the x-logarithm problem and the truncated point problem. The x-logarithm problem is shown to be hard if the decisional Diffie-Hellman problem is hard, although the reduction is not tight. The truncated point problem is shown to be solvable when the minimum amount of bits allowed in NIST standards are truncated, thereby making it insecure for applications such as stream ciphers. Nevertheless, it is argued that for nonce and key generation this distinguishability is harmless.

For a random-self-reducible function, the evaluation problem is irreducible to the one-more evaluation problem, in the following sense. An irreduction algorithm exists that, given a reduction algorithm from the evaluation to the one-more evaluation problem, solves a separator problem: the evaluation problem itself. Another irreduction shows that if the computational Diffie-Hellman problem is reduced to the gap Diffie-Hellman problem, then the decision Diffie-Hellman problem is easy. Irreductions are primarily of theoretical interest, because they do not actually prove inequivalence between problems. What these irreductions suggest, though, is that one-more variants of the RSA and discrete logarithm problems may be easier than the standard variants, and that the gap Diffie-Hellman problem may be easier than the standard Diffie-Hellman problem.

An elliptic curve random number generator (ECRNG) has been proposed in ANSI and NIST draft standards. This paper proves that, if three conjectures are true, then the ECRNG is secure. The three conjectures are hardness of the elliptic curve decisional Diffie-Hellman problem and the hardness of two newer problems, the x-logarithm problem and the truncated point problem.

Montgomery's ladder algorithm for elliptic curve scalar multiplication uses only the x-coordinates of points. Avoiding calculation of the y-coordinates saves time for certain curves. Montgomery introduced his method to accelerate Lenstra's elliptic curve method for integer factoring. Bernstein extended Montgomery's ladder algorithm by computing integer combinations of two points, thus accelerating signature verification over certain curves. This paper modifies and extends Bernstein's algorithm to integer combinations of two or more points.

Firstly, we demonstrate a pathological hash function choice that makes RSA-OAEP insecure. This shows that at least some security property is necessary for the hash functions used in RSA-OAEP. Nevertheless, we conjecture that only some very minimal security properties of the hash functions are actually necessary for the security of RSA-OAEP. Secondly, we consider certain types of reductions that could be used to prove the OW-CPA (i.e., the bare minimum) security of RSA-OAEP. We apply metareductions that show if such reductions existed, then RSA-OAEP would be OW-CCA2 insecure, or even worse, that the RSA problem would solvable. Therefore, it seems unlikely that such reductions could exist. Indeed, no such reductions proving the OW-CCA2 security of RSA-OAEP exist.

A deniable authentication scheme using RSA is described and proven secure in the random oracle model. A countermeasure to a well-known attack on efficient deniable authentication to multiple recipients is describe and proven secure.

Coppersmith's heuristic algorithm for finding small roots of bivariate modular equations can be applied against low-exponent RSA-OAEP if its randomizer is weak. An adversary that knows the randomizer can recover the entire plaintext message, provided it is short enough for Coppersmith's algorithm to work. In practice, messages are symmetric cipher keys and these are potentially short enough for certain sets of key sizes. Weak randomizers could arise in constrained smart cards or in kleptographic implementations. Because RSA's major use is transporting symmetric keys, this attack is a potential concern. In this respect, OAEP's design is more fragile than necessary, because a secure randomizer is critical to prevent a total loss of secrecy, not just a loss of semantic security or chosen-ciphertext security. Countermeasures and more robust designs that have little extra performance cost are proposed and discussed.

For any integer $n$, some side information exists that allows roots of certain polynomials modulo $n$ to be found efficiently (in polynomial time). The quartics $q_{u,a,b}(x) = x^4 - 4ux^3 - 2ax^2 -(8b + 4ua)x + a^2 - 4ub$, where $a$ and $b$ are some fixed integers, can be solved with probability approximately $\frac{1}{4}$ over integers $u$ chosen randomly from in $\{0,1,\dots,n-1\}$. The side information depends on $a$ and $b$, and is derivable from the factorization of $n$. The side information does not necessarily seem to reveal the factorization of $n$. For certain other polynomials, such as $p_u(x) = x^3 - u$, it is an important unsolved problem of theoretical cryptology whether there exists an algorithm for finding roots that does not also reveal the factorization of $n$. Cheng's special-purpose factoring algorithm is also reviewed and some extensions suggested.

If factoring is hard, this paper shows that straight line programs cannot efficiently solve the low public exponent RSA problem. More precisely, no efficient algorithm can take an RSA public key as input and then output a straight line program that efficiently solves the low public exponent RSA problem for the given public key --- unless factoring is easy.

A prompting protocol permits users to securely retrieve secrets with greater entropy than passwords. The retrieved user secrets can have enough entropy to be used to derive cryptographic keys.

The static Diffie-Hellman problem (SDHP) is the special case of the classic Diffie-Hellman problem where one of the public keys is fixed. We establish that the SDHP is almost as hard as the associated discrete logarithm problem. We do this by giving a reduction that shows that if the SDHP can be solved then the associated private key can be found. The reduction also establishes that certain systems have less security than anticipated. The systems affected are based on static Diffie-Hellman key agreement and do not use a key derivation function. This includes some cryptographic protocols: basic ElGamal encryption; Chaum and van Antwerpen's undeniable signature scheme; and Ford and Kaliski's key retrieval scheme, which is currently being standardized in IEEE P1363.2.

Proved here is the sufficiency of certain conditions to ensure the Elliptic Curve Digital Signature Algorithm (ECDSA) existentially unforgeable by adaptive chosen-message attacks. The sufficient conditions include (i) a uniformity property and collision-resistance for the underlying hash function, (ii) pseudo-randomness in the private key space for the ephemeral private key generator, (iii) generic treatment of the underlying group, and (iv) a further condition on how the ephemeral public keys are mapped into the private key space. For completeness, a brief survey of necessary security conditions is also given. Some of the necessary conditions are weaker than the corresponding sufficient conditions used in the security proofs here, but others are identical. Despite the similarity between DSA and ECDSA, the main result is not appropriate for DSA, because the fourth condition above seems to fail for DSA. (The corresponding necessary condition is plausible for DSA, but is not proved here nor is the security of DSA proved assuming this weaker condition.) Brickell et al., Jakobsson et al. and Pointcheval et al. only consider signature schemes that include the ephemeral public key in the hash input, which ECDSA does not do, and moreover, assume a condition on the hash function stronger than the first condition above. This work seems to be the first advance in the provable security of ECDSA.