1 Search Results for "Gelman, Efraim"

Document

DOI: 10.4230/LIPIcs.FSTTCS.2014.327

The Benes Network is q*(q-1)/2n-Almost q-set-wise Independent

Authors: Efraim Gelman and Amnon Ta-Shma

Published in: LIPIcs, Volume 29, 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)

Abstract

A switching network of depth d is a layered graph with d layers and n vertices in each layer. The edges of the switching network do not cross between layers and in each layer the edges form a partial matching. A switching network defines a stochastic process over Sn that starts with the identity permutation and goes through the layers of the network from first to last, where for each layer and each pair (i,j) in the partial matching of the layer, it applies the transposition (i j) with probability half. A switching network is good if the final distribution is close to the uniform distribution over S_n. A switching network is epsilon-almost q-permutation-wise independent if its action on any ordered set of size q is almost uniform, and is epsilon-almost q-set-wise independent if its action on any set of size q is almost uniform. Mixing of switching networks (even for q-permutation-wise and q-set-wise independence) has found several applications, mostly in cryptography. Some applications further require some additional properties from the network, e.g., the existence of an algorithm that given a permutation can set the switches such that the network generates the given permutation, a property that the Benes network has. Morris, Rogaway and Stegers showed the Thorp shuffle (which corresponds to applying two or more butterflies one after the other) is q-permutation-wise independent, for q=n^gamma for gamma that depends on the number of sequential applications of the butterfly network. The techniques applied by Morris et al. do not seem to apply for the Benes network. In this work we show the Benes network is almost q-set-wise independent for q up to about sqrt(n). Our technique is simple and completely new, and we believe carries hope for getting even better results in the future.

Cite as

Efraim Gelman and Amnon Ta-Shma. The Benes Network is q*(q-1)/2n-Almost q-set-wise Independent. In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 29, pp. 327-338, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{gelman_et_al:LIPIcs.FSTTCS.2014.327,
  author =	{Gelman, Efraim and Ta-Shma, Amnon},
  title =	{{The Benes Network is q*(q-1)/2n-Almost q-set-wise Independent}},
  booktitle =	{34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)},
  pages =	{327--338},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-77-4},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{29},
  editor =	{Raman, Venkatesh and Suresh, S. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2014.327},
  URN =		{urn:nbn:de:0030-drops-48538},
  doi =		{10.4230/LIPIcs.FSTTCS.2014.327},
  annote =	{Keywords: switching network, mixing, Benes}
}

Refine by Author
1 Gelman, Efraim
1 Ta-Shma, Amnon

Refine by Classification

Refine by Keyword
1 Benes
1 mixing
1 switching network

Refine by Type
1 document

Refine by Publication Year
1 2014

1 Search Results for "Gelman, Efraim"

The Benes Network is q*(q-1)/2n-Almost q-set-wise Independent

Abstract

Cite as

Thanks for your feedback!

Could not send message