Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I'd like to have an implementation of elliptic curve cryptography along the lines of secp256k1 which is secure until some information is published after which it is broken.

One idea would be to use elliptic curves over a ring $Z_n$ where $n=pq$ or perhaps $n=pqr$ where $p$, $q$ and $r$ are primes of similar size and the order of the curve over each factor is also prime. The factors would be small enough that discrete logarithms on curves over individual factors would be very practical but factoring $n$ would still be hard.

With the above construction the "order" of the ring would be a large composite which would be hard to factor so there wouldn't be a problem publishing that and the chances of happening across points for which the addition operation is undefined (hence leading to a factorization of n) is small.

These parameters could be used to implement a scheme which would be secure until the factorization of $n$ is published whereupon it is broken. Are there any problems with this scheme?

ByteCoin

share|improve this question
    
The ring $\mathbb{Z}/n\mathbb{Z}$ is not a field, if $n$ is composite. This might even having elliptic curve arithmetic complicated, not to speak of security at all. –  Paŭlo Ebermann Oct 15 '11 at 1:44
    
I know it's not a field but it behaves like one for most purposes. If one could not ignore this fact then elliptic curve factorization would be much faster. That being said - with this scheme you have more information than just knowing $n$ is composite. I want to know whether that introduces a flaw. –  ByteCoin Oct 15 '11 at 3:17
add comment

2 Answers

If discrete logarithm on the curve over $\mathbb{Z}_n$ is easy then $n$ can be as easily factored, precisely by using the Elliptic Curve Factorization Method, in which we indeed work with a curve over the ring $\mathbb{Z}_n$ and fervently hope for the computation to fail, i.e. to hit a non-invertible value. With figures: in practice, ECM works well when the smallest factor is no longer than 200 bits, but an "easy" discrete logarithm on an elliptic curve requires a much smaller field (an effort at breaking a single discrete logarithm on a 128-bit curve has begun, but it will take several years).

share|improve this answer
    
Do I understand right, this means that factoring our composed modulus is quite easier than solving discrete logarithms in the curves over the resulting smaller rings (instead of the other way around), and ByteCoin's proposed method will not work? –  Paŭlo Ebermann Oct 15 '11 at 3:37
    
Yes, that's it. It is even structural: the known algorithms for solving DL on elliptic curves can be transformed into factorization algorithms of $n$ by using them on the curve over $\mathbb{Z}_n$, in quite the same way than ECM factorization works. If DL on the curve over $\mathbb{Z}_p$ is easy, then factorization of $n$ is necessarily at least as easy. In practice, it is even easier, through ECM. –  Thomas Pornin Oct 15 '11 at 3:40
    
Ok. Thomas makes a good point. How about we choose curves where logs are easy to find? If the curves over $Z_p$, $Z_q$ etc are anomalous then the ECDLP can be solved in essentially linear time. This means that the factors can be chosen sufficiently large so that n can't be factored easily. –  ByteCoin Oct 15 '11 at 4:35
    
It would require to have a good look at the easy ECDLP solving algorithm on anomalous curves, to see whether the same method cannot be applied by simply computing modulo $n$ (i.e. doing it over $\mathbb{Z}_p$ and $\mathbb{Z}_q$ simultaneously, with the CRT). Anomalous curves "make me nervous". Also, if you end up computing modulo a hard-to-factor $n$, aren't you just reinventing RSA, but slower ? –  Thomas Pornin Oct 16 '11 at 14:07
    
Yes there are the problems you mention and the fact that n has to be hard to factor makes the signatures etc ridiculously large and slow. It was an idea for a particular implementation where it had to be ECC-based and security during operation was not terribly important but insecurity after termination was important. If there's a better way of getting this functionality then that would be interesting. Unfortunately I can't think of another way to generate an elliptic curve with some secret backdoor that would allow the rapid calculation of logarithms. –  ByteCoin Oct 16 '11 at 18:49
add comment

Apparently, my question had already been asked as shown in Trapdooring Discrete Logarithms on Elliptic Curves over Rings

My particular answer is shown to be broken in Security of an Identity-Based Cryptosystem and the Related Reductions

Briefly, when you specify an elliptic curve over a field and give its order, you of course get the twist's order for free. For an x-coordinate randomly chosen you have a roughly equal chance of getting a point on the intended curve or the twist. Similar considerations apply with elliptic curves over rings and by multiplying a few arbitrary points by the "group" order of the ring, you can factor n.

The article outlines some interesting reductions from knowing the order of a curve over $n$ to factoring $n$.

The former paper seems to offer solutions to the fundamental problem I was seeking to solve.

ByteCoin

share|improve this answer
    
Just a note: Signing your posts is not necessary (there is your userCard with name and avatar below any post), and a bit frowned upon in the Stack Exchange network. (About deleting own posts, we found out (just after I deleted your answer) that this is only possible for registered users (i.e. users with an OpenID linked to their account). –  Paŭlo Ebermann Oct 16 '11 at 23:43
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.