## Abstract

Universal One-Way Hash Functions (UOWHFs) may be used in place of collision-resistant functions in many public-key cryptographic applications. At Asiacrypt 2004, Hong, Preneel and Lee introduced the stronger security notion of higher order UOWHFs to allow construction of long-input UOWHFs using the Merkle-Damgård domain extender. However, they did not provide any provably secure constructions for higher order UOWHFs. We show that the subset sum hash function is a kth order Universal One-Way Hash Function (hashing n bits to m < n bits) under the Subset Sum assumption for k = O(log n). Therefore we strengthen a previous result of Impagliazzo and Naor, who showed that the subset sum hash function is a UOWHF under the Subset Sum assumption. We believe our result is of theoretical interest; as far as we are aware, it is the first example of a natural and computationally efficient UOWHF which is also a provably secure higher order UOWHF under the same well-known cryptographic assumption, whereas this assumption does not seem sufficient to prove its collision-resistance. A consequence of our result is that one can apply the Merkle-Damgård extender to the subset sum compression function with 'extension factor' k + 1, while losing (at most) about k bits of UOWHF security relative to the UOWHF security of the compression function. The method also leads to a saving of up to m log(k + 1) bits in key length relative to the Shoup XOR-Mask domain extender applied to the subset sum compression function.

Original language | English |
---|---|

Title of host publication | Public Key Cryptography - PKC 2006 - 9th International Conference on Theory and Practice in Public-Key Cryptography, Proceedings |

Editors | Moti Yung, Yevgeniy Dodis, Aggelos Kiayias, Tal Malkin |

Place of Publication | Berlin ; New York |

Publisher | Springer, Springer Nature |

Pages | 157-173 |

Number of pages | 17 |

Volume | 3958 LNCS |

ISBN (Print) | 3540338519, 9783540338512 |

DOIs | |

Publication status | Published - 2006 |

Event | 9th International Conference on Theory and Practice in Public-Key Cryptography, PKC 2006 - New York, NY, United States Duration: 24 Apr 2006 → 26 Apr 2006 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 3958 LNCS |

ISSN (Print) | 03029743 |

ISSN (Electronic) | 16113349 |

### Other

Other | 9th International Conference on Theory and Practice in Public-Key Cryptography, PKC 2006 |
---|---|

Country/Territory | United States |

City | New York, NY |

Period | 24/04/06 → 26/04/06 |