HartungGorre Verlag
Inh.: Dr.
Renate Gorre D78465
Konstanz Fon: +49 (0)7533 97227 Fax: +49 (0)7533 97228 www.hartunggorre.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 3891917457
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 socalled 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:
HartungGorre Verlag / D78465 Konstanz
Telefon: +49 (0) 7533 97227 Telefax: +49 (0) 7533 97228
http://www.hartunggorre.de eMail: verlag@hartunggorre.de