Hash Families and Cover-Free Families with Cryptographic Applications

Loading...
Thumbnail Image

Date

2010-09-28T15:17:20Z

Authors

Zaverucha, Gregory

Advisor

Journal Title

Journal ISSN

Volume Title

Publisher

University of Waterloo

Abstract

This thesis is focused on hash families and cover-free families and their application to problems in cryptography. We present new necessary conditions for generalized separating hash families, and provide new explicit constructions. We then consider three cryptographic applications of hash families and cover-free families. We provide a stronger de nition of anonymity in the context of shared symmetric key primitives and give a new scheme with improved anonymity properties. Second, we observe that nding the invalid signatures in a set of digital signatures that fails batch veri cation is a group testing problem, then apply and compare many group testing algorithms to solve this problem e ciently. In particular, we apply group testing algorithms based on cover-free families. Finally, we construct a one-time signature scheme based on cover-free families with short signatures.

Description

Keywords

perfect hash families, separating hash families, cover-free families, group testing, batch verification, shared symmetric key primitives, one-time signatures

LC Keywords

Citation