Hartung-Gorre Verlag Inh.: Dr. Renate Gorre D-78465 Konstanz Fon: +49 (0)7533 97227 Fax: +49 (0)7533 97228 www.hartung-gorre.de

S

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.

ISBN 3-89191-745-7

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

oder direkt:

Hartung-Gorre Verlag / D-78465 Konstanz

Telefon: +49 (0) 7533 97227 Telefax: +49 (0) 7533 97228

http://www.hartung-gorre.de eMail: verlag@hartung-gorre.de