Advanced

Almost k-wise independent sample spaces and their cryptologic applications

Kurosawa, K.; Johansson, Thomas LU and Stinson, D. (1997) International Conference on the Theory and Application of Cryptographic Techniques - EUROCRYPT'97 In Advances in Cryptology / Lecture Notes in Computer Science 1233. p.409-421
Abstract
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... (More)
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. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
in
Advances in Cryptology / Lecture Notes in Computer Science
volume
1233
pages
13 pages
publisher
Springer
conference name
International Conference on the Theory and Application of Cryptographic Techniques - EUROCRYPT'97
external identifiers
  • scopus:37249055417
ISSN
0302-9743
1611-3349
ISBN
978-3-540-62975-7
DOI
10.1007/3-540-69053-0_28
language
English
LU publication?
yes
id
99985f10-4f45-4521-8f22-445ccb7a89df (old id 1157335)
date added to LUP
2008-06-09 13:15:34
date last changed
2017-04-16 03:39:12
@inproceedings{99985f10-4f45-4521-8f22-445ccb7a89df,
  abstract     = {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. <br/><br>
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). <br/><br>
We also introduce the concept of ∈-almost k-resilient functions and give a construction that has parameters superior to k-resilient functions. <br/><br>
Finally, new bounds (necessary conditions) are derived for almost k-wise independent sample spaces, multiple A-codes and balanced ε-almost k-resilient functions.},
  author       = {Kurosawa, K. and Johansson, Thomas and Stinson, D.},
  booktitle    = {Advances in Cryptology / Lecture Notes in Computer Science},
  isbn         = {978-3-540-62975-7},
  issn         = {0302-9743},
  language     = {eng},
  pages        = {409--421},
  publisher    = {Springer},
  title        = {Almost k-wise independent sample spaces and their cryptologic applications},
  url          = {http://dx.doi.org/10.1007/3-540-69053-0_28},
  volume       = {1233},
  year         = {1997},
}