BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Maciej Skorski

Maciej Skorski contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Cryptography and SecurityMachine Learningmath.PRInformation Theorymath.ITmath.STStatistics TheoryComputationComputational ComplexityApplicationsData Structures and Algorithmsmath.OC

Trust snapshot

Quick read

Trust 21 - Emerging
16works
0followers
12topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

16 published item(s)

preprint2022arXiv

Handy Formulas for Binomial Moments

Despite the relevance of the binomial distribution for probability theory and applied statistical inference, its higher-order moments are poorly understood. The existing formulas are either not general enough, or not structured and simplified enough for intended applications. This paper introduces novel formulas for binomial moments, in form of \emph{polynomials in the variance} rather than in the success probability. The obtained formulas are arguably better structured, simpler and superior in their numerical properties compared to prior works. In addition, the paper presents algorithms to derive these formulas along with working implementation in the Python symbolic algebra package. The novel approach is a combinatorial argument coupled with clever algebraic simplifications which rely on symmetrization theory. As an interesting byproduct we establish \emph{asymptotically sharp estimates for central binomial moments}, improving upon partial results from prior works.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Robust and Provable Guarantees for Sparse Random Embeddings

In this work, we improve upon the guarantees for sparse random embeddings, as they were recently provided and analyzed by Freksen at al. (NIPS'18) and Jagadeesan (NIPS'19). Specifically, we show that (a) our bounds are explicit as opposed to the asymptotic guarantees provided previously, and (b) our bounds are guaranteed to be sharper by practically significant constants across a wide range of parameters, including the dimensionality, sparsity and dispersion of the data. Moreover, we empirically demonstrate that our bounds significantly outperform prior works on a wide range of real-world datasets, such as collections of images, text documents represented as bags-of-words, and text sequences vectorized by neural embeddings. Behind our numerical improvements are techniques of broader interest, which improve upon key steps of previous analyses in terms of (c) tighter estimates for certain types of quadratic chaos, (d) establishing extreme properties of sparse linear forms, and (e) improvements on bounds for the estimation of sums of independent random variables.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Concentration Bounds for the Collision Estimator

We prove a strong concentration result about the natural collision estimator, which counts the number of collisions that occur within an iid sample. This estimator is at the heart of algorithms used for uniformity testing and entropy assessment. While the prior works were limited to only variance, we use elegant techniques of independent interest to bounds higher moments and conclude concentration properties. As an immediate corollary we show that the estimator achieves high-probability guarantee on its own and there is no need for boosting (aka median/majority trick).

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Missing Mass Concentration for Markov Chains

The problem of missing mass in statistical inference (posed by McAllester and Ortiz, NIPS'02; most recently revisited by Changa and Thangaraj, ISIT'2019) seeks to estimate the weight of symbols that have not been sampled yet from a source. So far all the approaches have been focused on the IID model which, although overly simplistic, is already not straightforward to tackle. The non-trivial part is in handling correlated events and sums of variables with very different scales where classical concentration inequalities do not yield good bounds. In this paper we develop the research on missing mass further, solving the problem for Markov chains. We reduce the problem to studying the tails of hitting times and finding \emph{log-additive approximations} to them. More precisely, we combine the technique of majorization and certain estimates on set hitting times to show how the problem can be eventually reduced back to the IID case. Our contribution are a) new technique to obtain missing mass bounds - we replace traditionally used negative association by majorization which works for a wider class of processes b) first (exponential) concentration bounds for missing mass in Markov chain models c) simplifications of recent results on set hitting times and d) simplified derivation of missing mass estimates for memory-less sources.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Practical Estimation of Renyi Entropy

Entropy Estimation is an important problem with many applications in cryptography, statistic,machine learning. Although the estimators optimal with respect to the sample complexity have beenrecently developed, there are still some challenges we address in this paper.The contribution is a novel estimator which is built directly on the birthday paradox. Theanalysis turns out to be considerably simpler and offer superior confidence bounds with explicitconstants. We also discuss how streaming algorithm can be used to massively improve memoryconsumption. Last but not least, we study the problem of estimation in low or moderate regimes,adapting the estimator and proving rigorus bounds.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Random Embeddings with Optimal Accuracy

This work constructs Jonson-Lindenstrauss embeddings with best accuracy, as measured by variance, mean-squared error and exponential concentration of the length distortion. Lower bounds for any data and embedding dimensions are determined, and accompanied by matching and efficiently samplable constructions (built on orthogonal matrices). Novel techniques: a unit sphere parametrization, the use of singular-value latent variables and Schur-convexity are of independent interest.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Revisiting Initialization of Neural Networks

The proper initialization of weights is crucial for the effective training and fast convergence of deep neural networks (DNNs). Prior work in this area has mostly focused on balancing the variance among weights per layer to maintain stability of (i) the input data propagated forwards through the network and (ii) the loss gradients propagated backwards, respectively. This prevalent heuristic is however agnostic of dependencies among gradients across the various layers and captures only firstorder effects. In this paper, we propose and discuss an initialization principle that is based on a rigorous estimation of the global curvature of weights across layers by approximating and controlling the norm of their Hessian matrix. The proposed approach is more systematic and recovers previous results for DNN activations such as smooth functions, dropouts, and ReLU. Our experiments on Word2Vec and the MNIST/CIFAR image classification tasks confirm that tracking the Hessian norm is a useful diagnostic tool which helps to more rigorously initialize weights

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Simple Analysis of Johnson-Lindenstrauss Transform under Neuroscience Constraints

The paper re-analyzes a version of the celebrated Johnson-Lindenstrauss Lemma, in which matrices are subjected to constraints that naturally emerge from neuroscience applications: a) sparsity and b) sign-consistency. This particular variant was studied first by Allen-Zhu, Gelashvili, Micali, Shavit and more recently by Jagadeesan (RANDOM'19). The contribution of this work is a novel proof, which in contrast to previous works a) uses the modern probability toolkit, particularly basics of sub-gaussian and sub-gamma estimates b) is self-contained, with no dependencies on subtle third-party results c) offers explicit constants. At the heart of our proof is a novel variant of Hanson-Wright Lemma (on concentration of quadratic forms). Of independent interest are also auxiliary facts on sub-gaussian random variables.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Simulating Auxiliary Inputs, Revisited

For any pair $(X,Z)$ of correlated random variables we can think of $Z$ as a randomized function of $X$. Provided that $Z$ is short, one can make this function computationally efficient by allowing it to be only approximately correct. In folklore this problem is known as \emph{simulating auxiliary inputs}. This idea of simulating auxiliary information turns out to be a powerful tool in computer science, finding applications in complexity theory, cryptography, pseudorandomness and zero-knowledge. In this paper we revisit this problem, achieving the following results: \begin{enumerate}[(a)] We discuss and compare efficiency of known results, finding the flaw in the best known bound claimed in the TCC'14 paper "How to Fake Auxiliary Inputs". We present a novel boosting algorithm for constructing the simulator. Our technique essentially fixes the flaw. This boosting proof is of independent interest, as it shows how to handle "negative mass" issues when constructing probability measures in descent algorithms. Our bounds are much better than bounds known so far. To make the simulator $(s,ε)$-indistinguishable we need the complexity $O\left(s\cdot 2^{5\ell}ε^{-2}\right)$ in time/circuit size, which is better by a factor $ε^{-2}$ compared to previous bounds. In particular, with our technique we (finally) get meaningful provable security for the EUROCRYPT'09 leakage-resilient stream cipher instantiated with a standard 256-bit block cipher, like $\mathsf{AES256}$.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A New Approximate Min-Max Theorem with Applications in Cryptography

We propose a novel proof technique that can be applied to attack a broad class of problems in computational complexity, when switching the order of universal and existential quantifiers is helpful. Our approach combines the standard min-max theorem and convex approximation techniques, offering quantitative improvements over the standard way of using min-max theorems as well as more concise and elegant proofs.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A Time-Success Ratio Analysis of wPRF-based Leakage-Resilient Stream Ciphers

Weak pseudorandom functions (wPRFs) found an important application as main building blocks for leakage-resilient ciphers (EUROCRYPT'09). Several security bounds, based on different techniques, were given to these stream ciphers. The security loss in these reduction-based proofs is always polynomial, but has not been studied in detail. The aim of this paper is twofold. First, we present a clear comparison of quantitatively different security bounds in the literature. Second, we revisit the current proof techniques and answer the natural question of how far we are from meaningful and provable security guarantees, when instantiating weak PRFs with standard primitives (block ciphers or hash functions). In particular, we demonstrate a flaw in the recent (TCC'14) analysis of the EUROCRYPT'09 stream cipher, which means that we still don't know if it offers provable security when instantiated with a standard block cipher. Our approach is a \emph{time-to-success Ratio} analysis, a universal measure introduced by Luby, which allow us to compare different security bounds.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Condensed Unpredictability

We consider the task of deriving a key with high HILL entropy from an unpredictable source. Previous to this work, the only known way to transform unpredictability into a key that was $\eps$ indistinguishable from having min-entropy was via pseudorandomness, for example by Goldreich-Levin (GL) hardcore bits. This approach has the inherent limitation that from a source with $k$ bits of unpredictability entropy one can derive a key of length (and thus HILL entropy) at most $k-2\log(1/ε)$ bits. In many settings, e.g. when dealing with biometric data, such a $2\log(1/ε)$ bit entropy loss in not an option. Our main technical contribution is a theorem that states that in the high entropy regime, unpredictability implies HILL entropy. The loss in circuit size in this argument is exponential in the entropy gap $d$. To overcome the above restriction, we investigate if it's possible to first "condense" unpredictability entropy and make the entropy gap small. We show that any source with $k$ bits of unpredictability can be condensed into a source of length $k$ with $k-3$ bits of unpredictability entropy. Our condenser simply "abuses" the GL construction and derives a $k$ bit key from a source with $k$ bits of unpredicatibily. The original GL theorem implies nothing when extracting that many bits, but we show that in this regime, GL still behaves like a "condenser" for unpredictability. This result comes with two caveats (1) the loss in circuit size is exponential in $k$ and (2) we require that the source we start with has \emph{no} HILL entropy (equivalently, one can efficiently check if a guess is correct). We leave it as an intriguing open problem to overcome these restrictions or to prove they're inherent.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Lower bounds on $q$-wise independence tails and applications to min-entropy condensers

We present novel and sharp lower bounds for higher load moments in the classical problem of mapping $M$ balls into $N$ bins by $q$-universal hashing, specialized to the case when $M=N$. As a corollary we prove a tight counterpart for the result about min-entropy condensers due to Dodis, Pietrzak and Wichs (CRYPTO'14), which has found important applications in key derivation. It states that condensing $k$ bits of min-entropy into a $k$-bit string $ε$-close to almost full min-entropy (precisely $ k-\log\log(1/ε)$ bits of entropy) can be achieved by the use of $q$-independent hashing with $q= \log(1/ε)$. We prove that when given a source of min-entropy $k$ and aiming at entropy loss $\ell = \log\log (1/ε) - 3$, the independence level $q=(1-o(1))\log(1/ε)$ is necessary (for small values of $ε$), which almost matches the positive result. Besides these asymptotic bounds, we provide clear hard bounds in terms of Bell numbers and some numerical examples. Our technique is based on an explicit representation of the load moments in terms of Stirling numbers, some asymptotic estimates on Stirling numbers and a tricky application of the Paley-Zygmund inequality. \keywords{ min-entropy condensers, key derivation, balls and bins hashing, anti-concentration inequalities }

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Modulus Computational Entropy

The so-called {\em leakage-chain rule} is a very important tool used in many security proofs. It gives an upper bound on the entropy loss of a random variable $X$ in case the adversary who having already learned some random variables $Z_{1},\ldots,Z_{\ell}$ correlated with $X$, obtains some further information $Z_{\ell+1}$ about $X$. Analogously to the information-theoretic case, one might expect that also for the \emph{computational} variants of entropy the loss depends only on the actual leakage, i.e. on $Z_{\ell+1}$. Surprisingly, Krenn et al.\ have shown recently that for the most commonly used definitions of computational entropy this holds only if the computational quality of the entropy deteriorates exponentially in $|(Z_{1},\ldots,Z_{\ell})|$. This means that the current standard definitions of computational entropy do not allow to fully capture leakage that occurred "in the past", which severely limits the applicability of this notion. As a remedy for this problem we propose a slightly stronger definition of the computational entropy, which we call the \emph{modulus computational entropy}, and use it as a technical tool that allows us to prove a desired chain rule that depends only on the actual leakage and not on its history. Moreover, we show that the modulus computational entropy unifies other,sometimes seemingly unrelated, notions already studied in the literature in the context of information leakage and chain rules. Our results indicate that the modulus entropy is, up to now, the weakest restriction that guarantees that the chain rule for the computational entropy works. As an example of application we demonstrate a few interesting cases where our restricted definition is fulfilled and the chain rule holds.

0 citations0 reviewsNo code linkedOpen access