Inh.: Dr. Renate Gorre
Fon: +49 (0)7533 97227
Fax: +49 (0)7533 97228
New publication 1994
ETH Series in Information Processing Vol. 3
Editor: James L. Massey
Alain P. L. Hiltgen
Cryptographically Relevant Contributions
to Combinational Complexity Theory.
1st edition 1994. XII, 130 pages. EUR 34,80.
The provability of certain cryptographic assumptions and, more generally, the existence of provable practical security is investigated. It is argued why combinational complexity is the complexity measure that is most suited if the security of practical cryptographic applications is to be proved.
With respect to this complexity measure, it is shown that, even for practically small input sizes n, there exist Boolean functions (i.e., finite restrictions of decision problems) which are sufficiently complex to serve cryptographic purposes. Combinational complexity theory, however, has not yet brought upon a single technique by which a lower bound larger than 3n on the complexity of an explicitly defined Boolean function could be derived. It is suggested that this might be related to the existence of the so-called mass production effect for certain function classes. This effect allows many independent copies of the same function to be evaluated simultaneously by using much less hardware than would normally be expected. It is proved that the mass production effect exists not only for the hardest functions, which are of course nonlinear, but also for almost all linear functions.
ETH Series in Information Processing
Buchbestellungen in Ihrer Buchhandlung, bei www.amazon.de
Hartung-Gorre Verlag / D-78465 Konstanz
Telefon: +49 (0) 7533 97227 Telefax: +49 (0) 7533 97228
http://www.hartung-gorre.de eMail: email@example.com