Re: My attempt to break Rijndael (SAT-attack)

<posted & mailed>

Thorsten Kiefer wrote:

Sebastian Gottschalk wrote:

Peter Pearson wrote:

Hey, don't be so grumpy. It is, too, interesting. Keep at it, TK.

No, it's not interesting. Rijndael has be designed such that a simple SAT
won't help in any way. Once he tries to solve some less trivial cases
(way more unknown keybits), he'll for sure step upon a growth factor of
~2 per keybit.

Do you know Schöning's SAT algorithm ?
It solves SAT instances in (3/4)^n, where n is the number of variables.
It is the world record algorithm.
The clue is that it is a probabilistic algorithm.
An so is siege_v4 (my favorite algorithm).
This means that the growth factor is below 2.

Look here: http://theorie.informatik.uni-ulm.de/Forschung/Poster/3sat.gif

If you don't like probabilistic algorithms, then look at that :
http://theorie.informatik.uni-ulm.de/Forschung/Poster/3sat.gif

.

Relevant Pages

  • Re: algorithm implementation
    ... > Kyle, I was with you up to that last sentence. ... > Could the worst case of an algorithm also degenerate through a bad ... A bad implementation that has a higher growth rate than the big O ... You need to define the algorithm in sufficient detail so that it can be ...
    (comp.programming)
  • Re: My attempt to break Rijndael (SAT-attack)
    ... Thorsten Kiefer wrote: ... It is the world record algorithm. ... The clue is that it is a probabilistic algorithm. ... This means that the growth factor is below 2. ...
    (sci.crypt)
  • Re: Data Generation
    ... My algorithm starts to generate random numbers with the full given ... between -4% and +12% (meaning: on average equal to the given compound ... growth rate)? ...
    (microsoft.public.excel.misc)
  • Re: My attempt to break Rijndael (SAT-attack)
    ... Rijndael has be designed such that a simple SAT ... more unknown keybits), he'll for sure step upon a growth factor of ~2 per ... It is the world record algorithm. ... This means that the growth factor is below 2. ...
    (sci.crypt)
  • Q: Factoring a number whose Euler phi is known?
    ... This problem is related to the security of RSA encryption. ... There is a probabilistic algorithm: Choose a "public" exponent ...
    (sci.crypt)