1
$\begingroup$

Recently, I've been reading a couple of papers about building cryptosystems that are secure for up to 30 years. But for some applications, this seems a bit low to me. So I am wondering if considering the current state of the art in cryptography and computing power evolution forecasts, one could instead build a public-key encryption system, running on today's consumer hardware, which is secure for any foreseeable future.

Of course, written like this, the problem is too broad, so my specific criteria are as follows:

  • Keys are permanent, ciphertext which has been encrypted today must remain secure
  • Security is broken if an attacker can reliably decipher text which has been encrypted with the public key, without possessing the private key
  • Scenarios in which the attacker gets a hold of the private key by stealing, torture, and other means of extracting it from the rightful owner, are not considered a breach of security
  • My (very generous) upper bound for performance forecast realism is 1000 years in the future
  • I personally do not consider general-purpose quantum computers, based on logic gates operating on a large number of entangled qubits, to be viable in any foreseeable future, so security against them is just a nice extra
  • More specialized quantum computing systems like D-wave's quantum annealing, however, which do not rely on many-particle entanglement, are within the realm of possibilities
  • Attacker may be considered to have access to exabytes of ciphertext and terabytes of plain text - ciphertext pairs
  • Attacker may have access to state-of-the-art computing power, like the supercomputers of his generation
  • It must be possible to transfer public keys over the Internet within a reasonable time (absolute maximum is 1 day on a low-end 30 kB/s Internet connection -> 2GB), but they do not need to be transmitted frequently so it is acceptable if the keys are unusually big
  • Encryption must be fast on today's hardware, let's say 30 MB/s on a high-end laptop as a lower performance bound

Is this totally crazy, or can it be done using today's knowledge in cryptographic algorithms + implementations which are either available today or can be made available in the near future?

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ "Security is broken if an attacker can ... or reliably forge a message that looks like it has $\hspace{1.1 in}$ been encrypted with the private key" is an odd criterion. $\;$ $\endgroup$
    – user991
    Commented Apr 15, 2015 at 9:13
  • $\begingroup$ You are right. I realized that this question was wrong while re-reading my post after posting, but I do not have editing rights on this section of StackExchange yet. Although I'm also interested in long-lived digital signature, mixing digital signature and encryption together makes this an unnecessary complex question. Let's keep this focused on encryption only. $\endgroup$
    – Hadrien G.
    Commented Apr 15, 2015 at 11:18
  • $\begingroup$ -> Fixed, I can actually edit my posts, I just didn't find the link yet $\endgroup$
    – Hadrien G.
    Commented Apr 15, 2015 at 11:31
  • $\begingroup$ If the public key can be computed from the secret key, the adversary can always brute force all secret keys and recover it if he has unlimited time. $\endgroup$
    – Florian Bourse
    Commented Apr 15, 2015 at 15:44
  • 1
    $\begingroup$ It is not stated to what certainty degree it is required that the scheme remains secure after 1000 years, and that's an important parameter. It is much easier to predict very long term things with 30% chances to be wrong, rather than with 0.03% chances (a residual risk level often accepted in security, about that of having one's Smart Card pin guessed). One reason many key length estimates in the distant future are so conservative is that they are made with the intend to only err on the safe side. $\endgroup$
    – fgrieu ♦
    Commented Apr 15, 2015 at 17:15

2 Answers 2

Reset to default
3
$\begingroup$

... are secure for up to 30 years.

Unfortunately, you didn't reference where this number comes from. Breaking asymmetric cryptosystems comes with various flavors:

  • Scientific advances and new records, e.g. the factorization of RSA-768 in 2009
  • What intelligence agencies are capable of (it can be assumed to be a few years ahead of scientific advances, because of a massive resources in people and computing power)
  • Achievable on "normal" hardware (outside of a computing center)

The difference in this is quite massive. The 2009 factorization record was done with around 2000 computing years over 2 actual years. From that point we can use additional assumptions, like limiting the computing power by the energy consumption equal to the world GDP (assuming current price), apply More's law to computing power, etc.

All this is just the progression, if there is no major breakthrough in number theory, because that could change the entire picture fundamentally. Then all forecasts are off. But we don't know if that is even possible any more.

What can we do then? Well, there are various recommendations for several decades into the future, and on keylength.com notes the most common/serious/realistic ones. However, your assumption about 1000 years into the future is just not reasonable any more. This is like asking for an accurate weather forecast for several years. Of course you could extend the current calculations to that point in time, but it would not have any meaning, because long before then we will run into other limiting factors, like resources (to build computers), energy, etc.

To finish it off:

  • Almost all your criteria are trivially met by current standards.
  • Current security definitions are a lot stronger than yours, because you only assume a known plaintext attack. Security definitions like IND-CPA are a lot stronger statements.
  • If you use RSA with a keylength of 4096 or more, then you are probably beyond what will ever be breakable on this tiny planet until the end of the universe. Unless there are number theoretic advances.
Improve this answer
$\endgroup$
3
  • $\begingroup$ The numbers I found came from NIST and ECRYPT, but this website is awesome and I'm totally bookmarking it right now. Much more convenient than manually finding and checking papers on key length recommandations. $\endgroup$
    – Hadrien G.
    Commented Apr 15, 2015 at 15:12
  • $\begingroup$ Also, my 1000 years number was just here to say that I'm considering "humane" time scale, as proving anything forever would be extremely difficult (though e.g. some people used such proofs to state that 128-bit integers will always be big enough). I obviously also have some doubt about predictions reaching so far in the future. In any case, thanks for this thoughtful and detailed answer ! $\endgroup$
    – Hadrien G.
    Commented Apr 15, 2015 at 15:19
  • 1
    $\begingroup$ @HadrienG: These proofs of 128-bit security being strong enough assume that brute force is only possible approach. Unfortunately, given long enough time, it is not sure if brute force remains the only possibility, one hundred years is such time. $\endgroup$
    – user4982
    Commented Apr 15, 2015 at 21:00
5
$\begingroup$

I think that there is no chance of getting such an asymmetric cipher simply because you forgot about science.

The security on todays asymmetric cryptography is mostly based on the assumption that some mathematical algorithms cannot be reversed (e.g. the discrete logarithm or integer factorization).

If mathematics solves this problems then the algorithm is broken.

Such a breakthrough in mathematics can occur (e.g. for Fermat's Last Theorem in 1994).

So the major problem with assuring asymmetric cryptography as secure is to assure that no such breakthrough will occur.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Very interesting thinking track, and one which I didn't think much about indeed ! However, some symmetric ciphers are provably mathematically irreversible, the one-time pad is perhaps the most well-known example. Have there been successful attempts at building asymmetric ciphers that are similarly provably secure, even on the face of future scientific progress? $\endgroup$
    – Hadrien G.
    Commented Apr 15, 2015 at 11:29
  • 1
    $\begingroup$ @HadrienG. : $\;\;\;$ No, since there isn't even a known proof that there is no extremely practical algorithm for QBFs. $\:$ There is a complete PKE scheme, but it's completely impractical. $\;\;\;\;\;\;\;\;$ $\endgroup$
    – user991
    Commented Apr 15, 2015 at 11:38
  • 1
    $\begingroup$ @Hadrien Actually, what there are are proofs that no public-key encryption can be secure in the way a OTP is. Also, the provably secure symmetric ciphers are basically useless in practice, as information-theoretical security requires securely transmitting a truly random key as long as the message. $\endgroup$
    – cpast
    Commented Apr 15, 2015 at 16:56
  • $\begingroup$ Indeed, now that I think of it, these ciphers are almost always useless because if you have a secure channel capable of transmitting the full message, you might as well transmit it directly instead of using cryptography. They may still be useful in scenarios where people have a secure communication channel now, but may lose it in the future, though, am I right? $\endgroup$
    – Hadrien G.
    Commented Apr 16, 2015 at 9:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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