International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Daniel R. L. Brown

Publications

Year
Venue
Title
2016
JOFC
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2014
EPRINT
2010
EPRINT
Lower Bounds for Straight Line Factoring
Daniel R. L. Brown
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
Daniel R. L. Brown
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
Daniel R. L. Brown
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
Daniel R. L. Brown
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
Daniel R. L. Brown
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
Daniel R. L. Brown
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
CRYPTO
2007
EPRINT
A Security Analysis of the NIST SP 800-90 Elliptic Curve Random Number Generator
Daniel R. L. Brown Kristian Gjøsteen
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
Daniel R. L. Brown
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
Daniel R. L. Brown
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
Daniel R. L. Brown
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?
Daniel R. L. Brown
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
Daniel R. L. Brown
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
Daniel R. L. Brown
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
Daniel R. L. Brown
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
Daniel R. L. Brown
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
Daniel R. L. Brown
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
Daniel R. L. Brown Robert P. Gallant
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.
2003
PKC
2002
EPRINT
Generic Groups, Collision Resistance, and ECDSA
Daniel R. L. Brown
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.