Search Results

Documents authored by Skorski, Maciej

Document
DOI: 10.4230/LIPIcs.ISAAC.2022.18
Entropy Matters: Understanding Performance of Sparse Random Embeddings

Authors: Maciej Skorski

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
This work shows how the performance of sparse random embeddings depends on the Renyi entropy-like property of data, improving upon recent works from NIPS'18 and NIPS'19. While the prior works relied on involved combinatorics, the novel approach is simpler and modular. As the building blocks, it develops the following probabilistic facts of general interest: b) a comparison inequality between the linear and quadratic chaos c) a comparison inequality between heterogenic and homogenic linear chaos d) a simpler proof of Latala’s strong result on estimating distributions of IID sums e) sharp bounds for binomial moments in all parameter regimes.
Cite as

Maciej Skorski. Entropy Matters: Understanding Performance of Sparse Random Embeddings. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 18:1-18:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{skorski:LIPIcs.ISAAC.2022.18,
  author =	{Skorski, Maciej},
  title =	{{Entropy Matters: Understanding Performance of Sparse Random Embeddings}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{18:1--18:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.18},
  URN =		{urn:nbn:de:0030-drops-173037},
  doi =		{10.4230/LIPIcs.ISAAC.2022.18},
  annote =	{Keywords: Random Embeddings, Sparse Projections, Renyi Entropy}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.15
Tight Chernoff-Like Bounds Under Limited Independence

Authors: Maciej Skorski

Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)

Abstract
This paper develops sharp bounds on moments of sums of k-wise independent bounded random variables, under constrained average variance. The result closes the problem addressed in part in the previous works of Schmidt et al. and Bellare, Rompel. The work also discusses other applications of independent interests, such as asymptotically sharp bounds on binomial moments.
Cite as

Maciej Skorski. Tight Chernoff-Like Bounds Under Limited Independence. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 15:1-15:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{skorski:LIPIcs.APPROX/RANDOM.2022.15,
  author =	{Skorski, Maciej},
  title =	{{Tight Chernoff-Like Bounds Under Limited Independence}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{15:1--15:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.15},
  URN =		{urn:nbn:de:0030-drops-171372},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.15},
  annote =	{Keywords: concentration inequalities, tail bounds, limited independence, k-wise independence}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.20
Renyi Entropy Estimation Revisited

Authors: Maciej Obremski and Maciej Skorski

Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)

Abstract
We revisit the problem of estimating entropy of discrete distributions from independent samples, studied recently by Acharya, Orlitsky, Suresh and Tyagi (SODA 2015), improving their upper and lower bounds on the necessary sample size n. For estimating Renyi entropy of order alpha, up to constant accuracy and error probability, we show the following * Upper bounds n = O(1) 2^{(1-1/alpha)H_alpha} for integer alpha>1, as the worst case over distributions with Renyi entropy equal to H_alpha. * Lower bounds n = Omega(1) K^{1-1/alpha} for any real alpha>1, with the constant being an inverse polynomial of the accuracy, as the worst case over all distributions on K elements. Our upper bounds essentially replace the alphabet size by a factor exponential in the entropy, which offers improvements especially in low or medium entropy regimes (interesting for example in anomaly detection). As for the lower bounds, our proof explicitly shows how the complexity depends on both alphabet and accuracy, partially solving the open problem posted in previous works. The argument for upper bounds derives a clean identity for the variance of falling-power sum of a multinomial distribution. Our approach for lower bounds utilizes convex optimization to find a distribution with possibly worse estimation performance, and may be of independent interest as a tool to work with Le Cam’s two point method.
Cite as

Maciej Obremski and Maciej Skorski. Renyi Entropy Estimation Revisited. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 20:1-20:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{obremski_et_al:LIPIcs.APPROX-RANDOM.2017.20,
  author =	{Obremski, Maciej and Skorski, Maciej},
  title =	{{Renyi Entropy Estimation Revisited}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
  pages =	{20:1--20:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-044-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{81},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.20},
  URN =		{urn:nbn:de:0030-drops-75699},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.20},
  annote =	{Keywords: Renyi entropy, entropy estimation, sample complexity, convex optimization}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.39
Non-Uniform Attacks Against Pseudoentropy

Authors: Krzysztof Pietrzak and Maciej Skorski

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
De, Trevisan and Tulsiani [CRYPTO 2010] show that every distribution over n-bit strings which has constant statistical distance to uniform (e.g., the output of a pseudorandom generator mapping n-1 to n bit strings), can be distinguished from the uniform distribution with advantage epsilon by a circuit of size O( 2^n epsilon^2). We generalize this result, showing that a distribution which has less than k bits of min-entropy, can be distinguished from any distribution with k bits of delta-smooth min-entropy with advantage epsilon by a circuit of size O(2^k epsilon^2/delta^2). As a special case, this implies that any distribution with support at most 2^k (e.g., the output of a pseudoentropy generator mapping k to n bit strings) can be distinguished from any given distribution with min-entropy k+1 with advantage epsilon by a circuit of size O(2^k epsilon^2). Our result thus shows that pseudoentropy distributions face basically the same non-uniform attacks as pseudorandom distributions.
Cite as

Krzysztof Pietrzak and Maciej Skorski. Non-Uniform Attacks Against Pseudoentropy. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 39:1-39:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{pietrzak_et_al:LIPIcs.ICALP.2017.39,
  author =	{Pietrzak, Krzysztof and Skorski, Maciej},
  title =	{{Non-Uniform Attacks Against Pseudoentropy}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{39:1--39:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.39},
  URN =		{urn:nbn:de:0030-drops-74738},
  doi =		{10.4230/LIPIcs.ICALP.2017.39},
  annote =	{Keywords: pseudoentropy, non-uniform attacks}
}
Document
DOI: 10.4230/LIPIcs.STACS.2017.57
Lower Bounds on Key Derivation for Square-Friendly Applications

Authors: Maciej Skorski

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Abstract
Security of cryptographic applications is typically defined by security games. The adversary, within certain resources, cannot win with probability much better than 0 (for unpredictability applications, like one-way functions) or much better than 1/2 (indistinguishability applications for instance encryption schemes). In so called squared-friendly applications the winning probability of the adversary, for different values of the application secret randomness, is not only close to 0 or 1/2 on average, but also concentrated in the sense that its second central moment is small. The class of squared-friendly applications, which contains all unpredictability applications and many indistinguishability applications, is particularly important for key derivation. Barak et al. observed that for square-friendly applications one can beat the "RT-bound", extracting secure keys with significantly smaller entropy loss. In turn Dodis and Yu showed that in squared-friendly applications one can directly use a "weak" key, which has only high entropy, as a secure key. In this paper we give sharp lower bounds on square security assuming security for "weak" keys. We show that any application which is either (a) secure with weak keys or (b) allows for entropy savings for keys derived by universal hashing, must be square-friendly. Quantitatively, our lower bounds match the positive results of Dodis and Yu and Barak et al. (TCC'13, CRYPTO'11) Hence, they can be understood as a general characterization of squared-friendly applications. While the positive results on squared-friendly applications where derived by one clever application of the Cauchy-Schwarz Inequality, for tight lower bounds we need more machinery. In our approach we use convex optimization techniques and some theory of circular matrices.
Cite as

Maciej Skorski. Lower Bounds on Key Derivation for Square-Friendly Applications. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 57:1-57:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{skorski:LIPIcs.STACS.2017.57,
  author =	{Skorski, Maciej},
  title =	{{Lower Bounds on Key Derivation for Square-Friendly Applications}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{57:1--57:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.57},
  URN =		{urn:nbn:de:0030-drops-69761},
  doi =		{10.4230/LIPIcs.STACS.2017.57},
  annote =	{Keywords: key derivation, square-friendly applications, lower bounds}
}
Document
DOI: 10.4230/OASIcs.ICCSW.2014.83
On Recent Advances in Key Derivation via the Leftover Hash Lemma

Authors: Maciej Skorski

Published in: OASIcs, Volume 43, 2014 Imperial College Computing Student Workshop

Abstract
Barak et al. showed how to significantly reduce the entropy loss, which is necessary in general, in the use of the Leftover Hash Lemma (LHL) to derive a secure key for many important cryptographic applications. If one wants this key to be secure against any additional short leakage, then the min-entropy of the source used with the LHL must be big enough. Recently, Berens came up with a notion of collision entropy that is much weaker than min-entropy and allows proving a version of the LHL with leakage robustness but without any entropy saving. We combine both approaches and extend the results of Barak et. al to the collision entropy. Summarizing, we obtain a version of the LHL with optimized entropy loss, leakage robustness and weak entropy requirements.
Cite as

Maciej Skorski. On Recent Advances in Key Derivation via the Leftover Hash Lemma. In 2014 Imperial College Computing Student Workshop. Open Access Series in Informatics (OASIcs), Volume 43, pp. 83-90, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{skorski:OASIcs.ICCSW.2014.83,
  author =	{Skorski, Maciej},
  title =	{{On Recent Advances in Key Derivation via the Leftover Hash Lemma}},
  booktitle =	{2014 Imperial College Computing Student Workshop},
  pages =	{83--90},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-76-7},
  ISSN =	{2190-6807},
  year =	{2014},
  volume =	{43},
  editor =	{Neykova, Rumyana and Ng, Nicholas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ICCSW.2014.83},
  URN =		{urn:nbn:de:0030-drops-47783},
  doi =		{10.4230/OASIcs.ICCSW.2014.83},
  annote =	{Keywords: Key derivation, Leftover Hash Lemma, leakage robustness}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact