## CryptoDB

### Daniel R. L. Brown

#### Publications

**Year**

**Venue**

**Title**

2015

EPRINT

2014

EPRINT

2010

EPRINT

Lower Bounds for Straight Line Factoring
Abstract

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.

2010

EPRINT

Stange's Elliptic Nets and Coxeter Group F4
Abstract

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.

2008

EPRINT

The Encrypted Elliptic Curve Hash
Abstract

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.

2008

EPRINT

Toy Factoring by Newton's Method
Abstract

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.

2008

EPRINT

One-Up Problem for (EC)DSA
Abstract

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.

2008

EPRINT

User-Sure-and-Safe Key Retrieval
Abstract

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.

2007

EPRINT

A Security Analysis of the NIST SP 800-90 Elliptic Curve Random Number Generator
Abstract

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.

2007

EPRINT

Irreducibility to the One-More Evaluation Problems: More May Be Less
Abstract

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.

2006

EPRINT

Conjectured Security of the ANSI-NIST Elliptic Curve RNG
Abstract

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.

2006

EPRINT

Multi-Dimensional Montgomery Ladders for Elliptic Curves
Abstract

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.

2006

EPRINT

What Hashes Make RSA-OAEP Secure?
Abstract

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.

2005

EPRINT

Deniable Authentication with RSA and Multicasting
Abstract

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.

2005

EPRINT

A Weak-Randomizer Attack on RSA-OAEP with e = 3
Abstract

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.

2005

EPRINT

On Finding Roots Without Factoring and A Special Purpose Factoring Algorithm
Abstract

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.

2005

EPRINT

Breaking RSA May Be As Difficult As Factoring
Abstract

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.

2005

EPRINT

Prompted User Retrieval of Secret Entropy: The Passmaze Protocol
Abstract

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.

2004

EPRINT

The Static Diffie-Hellman Problem
Abstract

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.

2002

EPRINT

Generic Groups, Collision Resistance, and ECDSA
Abstract

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.

#### Coauthors

- Adrian Antipa (1)
- Robert P. Gallant (1)
- Kristian Gjøsteen (2)
- Alfred Menezes (1)
- René Struik (1)
- Scott A. Vanstone (1)