A time-luck tradeoff in relativized cryptography

摘要

New definitions are proposed for the security of Transient-Key Cryptography (a variant on Public-Key Cryptography) that account for the possibility of super-polynomial-time Monte Carlo cryptanalytical attacks. Weaker definitions no longer appear to be satisfactory in the light of Adleman's recent algorithm capable of breaking the Diffie-Hellman scheme in RTIME(O(20(√n log n))) for keys of length n. The basic question we address is: How can one relate the amount of time a cryptanalyst is willing to spend decoding cryptograms to his likelihood of success? What more can one say than the obvious “The more time he uses, the less lucky he needs to be?” These questions and others are partially answered in a relativized model of computation in which there exists a transient-key cryptosystem such that even a cryptanalyst willing to spend as much as (almost) O(2n/log n) steps on length n cryptograms cannot hope to break but an exponentially small fraction of them, even if he is allowed to make use of a true random number generator. This is rather tight because the same cryptosystem falls immediately if the cryptanalyst is willing to spend O(2cn) steps for any constant c > 0.