Re: unprovability of the security of computational cryptography

From: Bill Unruh (unruh_at_string.physics.ubc.ca)
Date: 10/17/03 

Date: Fri, 17 Oct 2003 16:11:15 +0000 (UTC)

"Ernst Lippe" <ernstl-at-planet-dot-nl@ignore.this> writes:

]On Fri, 17 Oct 2003 09:49:45 +0000, Mack wrote:

]> On Thu, 16 Oct 2003 18:26:35 +0200, "Ernst Lippe"
]> <ernstl-at-planet-dot-nl@ignore.this> wrote:
]>
]>>On Wed, 15 Oct 2003 13:08:43 +0000, Mack wrote:
]>>
]>>> On Tue, 14 Oct 2003 21:42:01 -0400, Nicol So
]>>> <anonymous@no.spam.please> wrote:
]>>>
]>>>>Mack wrote:
]>>>>
]>>>>> In reality the key of RSA is not the composite used but
]>>>>> either one of its factors. Therefore the equation could
]>>>>> also be said to hold there also if the factors are half the
]>>>>> length of k.
]>>>>
]>>>>No. Factoring is subexponential.
]>>> I stand corrected. Still we have a good grounding in the
]>>> problem. Public key algorithms are based on factoring
]>>> and discrete log which have well known complexities.
]>>
]>>No, they don't. We only know the complexity of the current algorithms.
]>>Given the recent history it is very well possible that better
]>>algorithms for these problems can be found. We don't yet have a
]>>non-trivial lower bound for the complexity of these problems.
]>
]> All cipher complexities suffer from no non-trivial lower bound
]> of complexity. The complexities of factoring and discrete log
]> are well known in the sense that these problems have been
]> worked on for a long time and the difficulties of finding an easy
]> solution are known. Since it isn't even known if P=NP or P!=NP
]> the complexity of any algorithm can't be said to be known
]> unless it is in P.

]Of course there are algorithms that have a non-polynomial
]complexity. Also there are problems that are definitely
]not in P, e.g. EXPTIME-complete problems.

]>>> For block ciphers, we still use the assumption that they
]>>> require 2^key bits time/text to break to be secure.
]>>
]>>The standard definition of a break is an attack with a lower
]>>complexity than was claimed for that cipher. There are no good
]>>reasons why the claimed complexity should always be O(2^key). For
]>>example, if you would want to build a block cipher whose security was
]>>based on the hardness of well-known problems such as factoring, it is
]>>very well possible that such a block cipher would have a provable
]>>complexity that is less than O(2^key). I see no reason why such a
]>>cipher would be "broken", especially because it would have a much
]>>better security proof than all standard block ciphers.
]>>
]>>So your definition of a break is so much stricter than the
]>>traditional one that it is not a very useful definition.
]> In my opinion the definition is accurate for block ciphers
]> without some other proof of security.

]Because this is the (sometimes implicetely) claimed complexity
]for most block ciphers, your definition coincides in most cases with the
]standard one. But how do you generalize your definition to
]other cryptographical primitives?

]Also, did you consider DES broken immediately when it
]was discovered that only 2^55 plaintexts were needed
]due to is complement structure?

]> As I said in another message above (changed to caps to highlight):
]>>>>You are correct that definition has only been applied
]>>>>to block cipher and stream cipher algorithms WITHOUT
]>>>>OTHER PROOFS OF SECURITY. Public key methods rest
]>>>>on the belief that NP!=P. That is another line of this
]>>>>thread.

No they do not. They rest on the belief that certain functions are much
more difficult to calculate in one direction than another. P or NP are
completely irrelevant for any finite key. They refer to assymptotic
estimates. Thus even if P=NP if it were shown that say factoring has a
difficulty that scaled as L^100 AND that that that applied also to short
keys and that the prefactor was small, then that would make an equally
good crypto primative as if it could be shown that factoring went as
exp [L^(1/1000)]
The latter is non-polynomial, but pretty useless for crypto, while the
former is polynomial and very useful for crypto.
Sure, if the key is longer than 10^80 digits the latter might beat the
former, but who cares.
Ie, P and NP are really irrelevant for crypto. Hard and easy are much
more useful (although also much vaguer) concepts for crypto.

Relevant Pages

  • Re: unprovability of the security of computational cryptography
    ... Public key algorithms are based on factoring ... We only know the complexity of the current algorithms. ... if you would want to build a block cipher whose security was ...
    (sci.crypt)
  • Re: unprovability of the security of computational cryptography
    ... We only know the complexity of the current algorithms. ... The complexities of factoring and discrete log ... if you would want to build a block cipher whose security was ...
    (sci.crypt)
  • Re: unprovability of the security of computational cryptography
    ... We only know the complexity of the current algorithms. ... >>The standard definition of a break is an attack with a lower ... if you would want to build a block cipher whose security was ...
    (sci.crypt)
  • Re: complexity of LP
    ... one must discern between the complexity in regards of step numbers ... An algorithm for solving linear programming problems in $O$ operations. ... On the worst case complexity of potential reduction algorithms for linear programming. ...
    (sci.math.num-analysis)
  • Re: Intro to Programming w/ Machine Language
    ... )> If n is sufficiently large, the Ocomplexity obviously matters. ... You only stated that big-oh complexity ... Not if the algorithms were carefully chosen in the first place. ... Or, much more prevalent, the choice of datatypes for search lists, ...
    (comp.programming)