Abstract | ||
---|---|---|
The unicity distance of a cascade of random ciphers, with respect to known plaintext attack, is shown to be the sum of the key lengths. A time-space trade-off for the exhaustive cracking of a cascade of ciphers is shown. The structure of the set of permutations realized by a cascade is studied; it is shown that only l.2k exhaustive experiments are necessary to determine the behavior of a cascade of l stages, each having k key bits. It is concluded that the cascade of random ciphers is not a random cipher. Yet, it is shown that, with high probability, the number of permutations realizable by a cascade of l random ciphers, each having k key bits, is 2lk. Next, it is shown that two stages are not worse than one, by a simple reduction of the cracking problem of any of the stages to the cracking problem of the cascade. Finally, it is shown that proving a nonpolynomial lower bound on the cracking problem of long cascades is a hard task, since such a bound implies that P ≉ NP. |
Year | DOI | Venue |
---|---|---|
1985 | 10.1145/214438.214442 | ACM Trans. Comput. Syst. |
Keywords | Field | DocType |
permutations realizable,exhaustive experiment,k key bit,long cascade,high probability,cascade cipher,hard task,l stage,key length,l random cipher,random cipher,known plaintext attack,lower bound | Block size,Cipher,Discrete mathematics,Unicity distance,Upper and lower bounds,Computer science,Known-plaintext attack,Permutation,Algorithm,Cascade,Distributed computing,Differential cryptanalysis | Journal |
Volume | Issue | ISSN |
3 | 2 | 0734-2071 |
Citations | PageRank | References |
32 | 5.65 | 5 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
shimon even | 1 | 2873 | 981.78 |
Oded Goldreich | 2 | 554 | 123.34 |