Re: triple algorithms

On 26 Feb, 23:55, Paul Rubin <http://phr...@xxxxxxxxxxxxxx> wrote:
Simon  Johnson <simon.john...@xxxxxxxxx> writes:

A much stronger assumption for a cipher is to know that in order to
break it you have to perform action x and x is a known hard problem.
BBS is a cipher with this property.  We know that any solution to BBS
must provide us with the factors of the modulus. We know integer
factorization is a hard problem for sufficiently large values of n.

Actually we don't know that a fast factoring algorithm won't be
discovered tomorrow.  Such a discovery wouldn't really break any
cherished beliefs about complexity, like P vs NP.

Yup. I propose we have a Godwin style law regarding P vs NP.

P vs NP has nothing to do with cryptography what-so-ever and
mentioning only confuses the discussion further.

It's worth noting that there is an important difference between AES et
al and something like the BBS.

AES is secure only in the sense that nobody has discovered an
effective attack for it.

BBS is secure in the sense that the *only* way to attack it is to
factor n. Any attack that breaks it must also factor n. This is a
stronger underlying security assumption than any block-cipher
currently has.

Therefore BBS is more secure than AES in a certain sense since its
security depends only on the single assumption that factoring is hard.

This is very dubious, if you consider the progress that's been made in
factoring over the past few decades.  The first deployed use of RSA
was at Sandia Labs.  The modulus length was 336 bits, IIRC.  

It's true that we've made progress on factoring integers but it's
important to put this in to context.

Say I need a throughput of x bytes per seconds for a particular
application. There will be a given size modulus n that will give me
encryption speeds of the required throughput.

It is true that for a fixed n, as time goes on the strength of the
data encrypted with BBS will decrease.

However, this is not the full story. Because of continual improvements
in hardware, in eighteen months time there will be a larger value of n
that gives me the same throughput as before. This bigger n will also
be much harder to factor. Adding ten digits to a modulus roughly
doubles the run time of the GNFS. Yet the extra processing time of
working with a number ten digits longer is negligible. It certainly
isn't anywhere near half as slow.

So provided you change your keys every so often and grow your n
accordingly, the strength of BBS will increase over time.

Simon.
.

Relevant Pages

  • Re: triple algorithms
    ... break it you have to perform action x and x is a known hard problem. ... BBS is a cipher with this property. ... security depends only on the single assumption that factoring is hard. ... The modulus length was 336 bits, ...
    (sci.crypt)
  • Re: More about MT19937 in crypto
    ... breaking BBS is at least as hard as factoring. ... > Some people might find it more plausible that cracking AES is hard. ... exist unknown attacks which require less work than these known attacks. ...
    (sci.crypt)
  • Re: triple algorithms
    ... break it you have to perform action x and x is a known hard problem. ... BBS is a cipher with this property. ... Such a discovery wouldn't really break any ... security depends only on the single assumption that factoring is hard. ...
    (sci.crypt)
  • Re: More about MT19937 in crypto
    ... Benjamin Goldberg wrote: ... > breaking BBS is at least as hard as factoring. ... It's a real proof that BBS is as hard as factoring. ...
    (sci.crypt)