Re: unprovability of the security of computational cryptography

From: Ernst Lippe (ernstl-at-planet-dot-nl_at_ignore.this)
Date: 10/16/03 

Date: Thu, 16 Oct 2003 18:26:35 +0200

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.

> 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.

greetings,

Ernst Lippe

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)