Plenary Lecture

Digital Signature and Hash Function Irregularity

Abstract: Use of computer networks is expanding in many important areas such as e-government, e-business, e-learning etc. In any such communications network it is crucial to be able to authenticate both the contents and the origin of a message. Digital signatures (based on public key schemas) are used for authentication and ideally they should provide the same guarantees as a handwritten signatures: unforgeability (only the author of a message should be able to sign his name to a message), undeniability (the author of a message should not be able to deny he signed it at a later stage) and authentication (the signature should allow the contents of the message to be authenticated).
In order to provide message authentication the signature must depend on the contents of the message being signed. Two major problems with the public key-based signature schemes are that they are existentially forgeable and if the message is long then the signature will take a long time to compute. To overcome both of these problems hash functions that map a (possibly lengthy) message to a small digest h(M) are used. Among other desirable properties (the length of h(M) should be small, the function h should be a publicly known one-way function, it should destroy algebraic relationships between messages and signatures), an interesting one is that it should be ‘collision-resistant’, that is it should be difficult to find two messages with the same hash value.
To find a collision the birthday attack is used, which shows that attacker may not need to examine too many messages before he ?nds a collision. If attacker generates random messages and computes their hash values then with probability at least ½ he ?nds a collision after generating ?2|R| messages, where |R| is the total number of possible hash values for the corresponding hash function. The real situation is even worse. In previous estimates it is always assumed that the hash function is regular, meaning that all points in the range have the same number of pre-images under h. If h is not regular, fewer trials are required. Here we examine different types of irregularity of the hash function and the quantitative changes in the required number of trials to find a collision.

Brief Biography of the Speaker:
Milan Tuba received B. S. in Mathematics, M. S. in Mathematics, M. S. in Computer Science, M. Ph. in Computer Science, Ph. D. in Computer Science from University of Belgrade and New York University. From 1983 to 1987 he was a graduate student and teaching and research assistant at Vanderbilt University in Nashville and Courant Institute of Mathematical Sciences, New York University. From 1987 to 1993. he was Assistant Professor of Electrical Engineering at Cooper Union Graduate School of Engineering, New York. During that time he was the founder and director of Microprocessor Lab and VLSI Lab, leader of scientific projects and supervisor of many theses. From 1994 he was Associate professor of Computer Science and Director of Computer Center at University of Belgrade, Faculty of Mathematics, and from 2004 also Professor of Computer Science and Dean of the College of Computer Science, Megatrend University Belgrade. He was teaching about 20 graduate and undergraduate courses, from VLSI Design and Computer Architecture to Computer Networks, Image Processing, Calculus and Queuing Theory. His research interest include mathematical, queuing theory and algorithmic optimizations applied in computer networks, image processing and combinatorial problems. He is the author of more than 60 scientific papers and a monograph. He was coeditor or member of the board of editors of number of scientific journals and conferences. Member ACM 1983, IEEE 1984, AMS 1995, New York Academy of Sciences 1987.