Almost kwise independent sample spaces and their cryptologic applications
(1997) International Conference on the Theory and Application of Cryptographic Techniques  EUROCRYPT'97 In Advances in Cryptology / Lecture Notes in Computer Science 1233. p.409421 Abstract
 An almost kwise 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 Acodes), almost strongly universal hash families and almost kresilient functions.
We use almost kwise independent sample spaces to construct new efficient multiple Acodes 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 kresilient... (More)  An almost kwise 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 Acodes), almost strongly universal hash families and almost kresilient functions.
We use almost kwise independent sample spaces to construct new efficient multiple Acodes 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 kresilient functions and give a construction that has parameters superior to kresilient functions.
Finally, new bounds (necessary conditions) are derived for almost kwise independent sample spaces, multiple Acodes and balanced εalmost kresilient functions. (Less)
Please use this url to cite or link to this publication:
http://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
 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
 16113349
 03029743
 ISBN
 9783540629757
 DOI
 10.1007/3540690530_28
 language
 English
 LU publication?
 yes
 id
 99985f104f4545218f22445ccb7a89df (old id 1157335)
 date added to LUP
 20080609 13:15:34
 date last changed
 20170416 03:39:12
@inproceedings{99985f104f4545218f22445ccb7a89df, abstract = {An almost kwise 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 Acodes), almost strongly universal hash families and almost kresilient functions. <br/><br> We use almost kwise independent sample spaces to construct new efficient multiple Acodes 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 kresilient functions and give a construction that has parameters superior to kresilient functions. <br/><br> Finally, new bounds (necessary conditions) are derived for almost kwise independent sample spaces, multiple Acodes and balanced εalmost kresilient functions.}, author = {Kurosawa, K. and Johansson, Thomas and Stinson, D.}, booktitle = {Advances in Cryptology / Lecture Notes in Computer Science}, isbn = {9783540629757}, issn = {16113349}, language = {eng}, pages = {409421}, publisher = {Springer}, title = {Almost kwise independent sample spaces and their cryptologic applications}, url = {http://dx.doi.org/10.1007/3540690530_28}, volume = {1233}, year = {1997}, }