The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

Almost k-wise independent sample spaces and their cryptologic applications

Author

Summary, in English

An almost k-wise independent sample space is a small subset of m bit sequences in which any k bits are “almost independent”. We show that this idea has close relationships with useful cryptologic notions such as multiple authentication codes (multiple A-codes), almost strongly universal hash families and almost k-resilient functions.

We use almost k-wise independent sample spaces to construct new efficient multiple A-codes such that the number of key bits grows linearly as a function of k (here k is the number of messages to be authenticated with a single key). This improves on the construction of Atici and Stinson [2], in which the number of key bits is Ω (k 2).

We also introduce the concept of ∈-almost k-resilient functions and give a construction that has parameters superior to k-resilient functions.

Finally, new bounds (necessary conditions) are derived for almost k-wise independent sample spaces, multiple A-codes and balanced ε-almost k-resilient functions.

Publishing year

1997

Language

English

Pages

409-421

Publication/Series

Advances in Cryptology / Lecture Notes in Computer Science

Volume

1233

Document type

Conference paper

Publisher

Springer

Topic

  • Electrical Engineering, Electronic Engineering, Information Engineering

Conference name

International Conference on the Theory and Application of Cryptographic Techniques - EUROCRYPT'97

Conference date

1997-05-11 - 1997-05-15

Conference place

Konstanz, Germany

Status

Published

ISBN/ISSN/Other

  • ISSN: 1611-3349
  • ISSN: 0302-9743
  • ISBN: 978-3-540-62975-7