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
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:
https://lup.lub.lu.se/record/1157335
- author
- Kurosawa, K.
; Johansson, Thomas
LU
and Stinson, D.
- organization
- publishing date
- 1997
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- host publication
- 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
- conference location
- Konstanz, Germany
- conference dates
- 1997-05-11 - 1997-05-15
- 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
- 2016-04-01 12:25:54
- date last changed
- 2024-01-08 20:16:34
@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}},
doi = {{10.1007/3-540-69053-0_28}},
volume = {{1233}},
year = {{1997}},
}