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

<posted & mailed>

Thorsten Kiefer wrote:

<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

Uhm I mean http://theorie.informatik.uni-ulm.de/Forschung/Poster/search.gif

.

Relevant Pages

  • Re: My attempt to break Rijndael (SAT-attack)
    ... (way more unknown keybits), he'll for sure step upon a growth factor of ... 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)
  • 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)
  • Re: Is "infinite processes" allowed in algorithm for construction?
    ... a formal algorithm must complete in a finite amount of time ... There is also a standard notion of a "probabilistic algorithm" which does ... probabilistic algorithm iterates continually and has a known (or bounded ...
    (sci.math)
  • 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: 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)