Binary decision trees are basically super optimizers: minimizing the number of gates needed to make a Chip's logic (multiply circuits or whatever)
Sure, and unbreakable crypto is notoriously difficult to make
Not really. It's the unbreakable AND efficient requirement combined that's hard.
Just run anything over a random xor shift add kernel about 1 million times and it's unbreakable (so long as xor / shift forms a bijection). It's just inefficient.
Finding the smallest number of iterations that works is the hard part. Usually, people try to break it (ex, AES was originally broken over 4 iterations) then double or triple your best attempt, and you are set.
AES is now broken over 5 iterations IIRC, but still a long way to go to break full 8 iteration AES.
More modern ciphers (SHA512) are like 80 iterations of a simpler kernel.
Even 'broken' ciphers like TEA or RC4 are hard to break in practice if you just increase the iteration count up the wazzoo. The problem is: AES gets to security in just 8 iterations.
So to be better than AES requires both efficiency AND security. After all, 100 iterations of AES is going to be more secure if you don't care about efficiency. (10x more iterations than the default spec)
Comments
Sure, and unbreakable crypto is notoriously difficult to make. I wouldn't expect a situation like that to come up in a real-world problem.
Binary decision trees are basically super optimizers: minimizing the number of gates needed to make a Chip's logic (multiply circuits or whatever)
Not really. It's the unbreakable AND efficient requirement combined that's hard.
Just run anything over a random xor shift add kernel about 1 million times and it's unbreakable (so long as xor / shift forms a bijection). It's just inefficient.
Finding the smallest number of iterations that works is the hard part. Usually, people try to break it (ex, AES was originally broken over 4 iterations) then double or triple your best attempt, and you are set.
AES is now broken over 5 iterations IIRC, but still a long way to go to break full 8 iteration AES.
More modern ciphers (SHA512) are like 80 iterations of a simpler kernel.
Even 'broken' ciphers like TEA or RC4 are hard to break in practice if you just increase the iteration count up the wazzoo. The problem is: AES gets to security in just 8 iterations.
So to be better than AES requires both efficiency AND security. After all, 100 iterations of AES is going to be more secure if you don't care about efficiency. (10x more iterations than the default spec)