1,721,171 research outputs found
Doubly-Affine Extractors, and Their Applications
Full text linkIn this work we challenge the common misconception that information-theoretic (IT) privacy is too impractical to be used in the real-world: we propose to build simple and reusable IT-encryption solutions whose only efficiency penalty (compared to computationally-secure schemes) comes from a large secret key size, which is often a rather minor inconvenience, as storage is cheap. In particular, our solutions are stateless and locally computable at the optimal rate, meaning that honest parties do not maintain state and read only (optimally) small portions of their large keys with every use.
Moreover, we also propose a novel architecture for outsourcing the storage of these long keys to a network of semi-trusted servers, trading the need to store large secrets with the assumption that it is hard to simultaneously compromise too many publicly accessible ad-hoc servers. Our architecture supports everlasting privacy and post-application security of the derived one-time keys, resolving two major limitations of a related model for outsourcing key storage, called bounded storage model.
Both of these results come from nearly optimal constructions of so called doubly-affine extractors: locally-computable, seeded extractors Ext(X,S) which are linear functions of X (for any fixed seed S), and protect against bounded affine leakage on X. This holds unconditionally, even if (a) affine leakage may adaptively depend on the extracted key R = Ext(X,S); and (b) the seed S is only computationally secure. Neither of these properties are possible with general-leakage extractors
Small-Box Cryptography
Full text linkOne of the ultimate goals of symmetric-key cryptography is to find a rigorous theoretical framework for building block ciphers from small components, such as cryptographic S-boxes, and then argue why iterating such small components for sufficiently many rounds would yield a secure construction. Unfortunately, a fundamental obstacle towards reaching this goal comes from the fact that traditional security proofs cannot get security beyond 2^{-n}, where n is the size of the corresponding component.
As a result, prior provably secure approaches - which we call "big-box cryptography" - always made n larger than the security parameter, which led to several problems: (a) the design was too coarse to really explain practical constructions, as (arguably) the most interesting design choices happening when instantiating such "big-boxes" were completely abstracted out; (b) the theoretically predicted number of rounds for the security of this approach was always dramatically smaller than in reality, where the "big-box" building block could not be made as ideal as required by the proof. For example, Even-Mansour (and, more generally, key-alternating) ciphers completely ignored the substitution-permutation network (SPN) paradigm which is at the heart of most real-world implementations of such ciphers.
In this work, we introduce a novel paradigm for justifying the security of existing block ciphers, which we call small-box cryptography. Unlike the "big-box" paradigm, it allows one to go much deeper inside the existing block cipher constructions, by only idealizing a small (and, hence, realistic!) building block of very small size n, such as an 8-to-32-bit S-box. It then introduces a clean and rigorous mixture of proofs and hardness conjectures which allow one to lift traditional, and seemingly meaningless, "at most 2^{-n}" security proofs for reduced-round idealized variants of the existing block ciphers, into meaningful, full-round security justifications of the actual ciphers used in the real world.
We then apply our framework to the analysis of SPN ciphers (e.g, generalizations of AES), getting quite reasonable and plausible concrete hardness estimates for the resulting ciphers. We also apply our framework to the design of stream ciphers. Here, however, we focus on the simplicity of the resulting construction, for which we managed to find a direct "big-box"-style security justification, under a well studied and widely believed eXact Linear Parity with Noise (XLPN) assumption.
Overall, we hope that our work will initiate many follow-up results in the area of small-box cryptography
Online Linear Extractors for Independent Sources
Full text linkIn this work, we characterize linear online extractors. In other words, given a matrix A ∈ F₂^{n×n}, we study the convergence of the iterated process S ← AS⊕X, where X∼D is repeatedly sampled independently from some fixed (but unknown) distribution D with (min)-entropy k. Here, we think of S ∈ {0,1}ⁿ as the state of an online extractor, and X ∈ {0,1}ⁿ as its input.
As our main result, we show that the state S converges to the uniform distribution for all input distributions D with entropy k > 0 if and only if the matrix A has no non-trivial invariant subspace (i.e., a non-zero subspace V ⊊ F₂ⁿ such that AV ⊆ V). In other words, a matrix A yields a linear online extractor if and only if A has no non-trivial invariant subspace. For example, the linear transformation corresponding to multiplication by a generator of the field F_{2ⁿ} yields a good linear online extractor. Furthermore, for any such matrix convergence takes at most Õ(n²(k+1)/k²) steps.
We also study the more general notion of condensing - that is, we ask when this process converges to a distribution with entropy at least l, when the input distribution has entropy at least k. (Extractors corresponding to the special case when l = n.) We show that a matrix gives a good condenser if there are relatively few vectors w ∈ F₂ⁿ such that w, A^Tw, …, (A^T)^{n-k}w are linearly dependent. As an application, we show that the very simple cyclic rotation transformation A(x₁,…, x_n) = (x_n,x₁,…, x_{n-1}) condenses to l = n-1 bits for any k > 1 if n is a prime satisfying a certain simple number-theoretic condition.
Our proofs are Fourier-analytic and rely on a novel lemma, which gives a tight bound on the product of certain Fourier coefficients of any entropic distribution
On Seedless PRNGs and Premature Next
Full text linkPseudorandom number generators with input (PRNGs) are cryptographic algorithms that generate pseudorandom bits from accumulated entropic inputs (e.g., keystrokes, interrupt timings, etc.). This paper studies in particular PRNGs that are secure against premature next attacks (Kelsey et al., FSE '98), a class of attacks leveraging the fact that a PRNG may produce an output (which could be seen by an adversary!) before enough entropy has been accumulated. Practical designs adopt either unsound entropy-estimation methods to prevent such attacks (as in Linux’s /dev/random) or sophisticated pool-based approaches as in Yarrow (MacOS/FreeBSD) and Fortuna (Windows).
The only prior theoretical study of premature next attacks (Dodis et al., Algorithmica '17) considers either a seeded setting or assumes constant entropy rate, and thus falls short of providing and validating practical designs. Assuming the availability of random seed is particularly problematic, first because this requires us to somehow generate a random seed without using our PRNG, but also because we must ensure that the entropy inputs to the PRNG remain independent of the seed. Indeed, all practical designs are seedless. However, prior works on seedless PRNGs (Coretti et al., CRYPTO '19; Dodis et al., ITC '21, CRYPTO'21) do not consider premature next attacks.
The main goal of this paper is to investigate the feasibility of theoretically sound seedless PRNGs that are secure against premature next attacks. To this end, we make the following contributions:
1) We prove that it is impossible to achieve seedless PRNGs that are secure against premature-next attacks, even in a rather weak model. Namely, the impossibility holds even when the entropic inputs to the PRNG are independent. In particular, our impossibility result holds in settings where seedless PRNGs are otherwise possible.
2) Given the above impossibility result, we investigate whether existing seedless pool-based approaches meant to overcome premature next attacks in practical designs provide meaningful guarantees in certain settings. Specifically, we show the following.
3) We introduce a natural condition on the entropic input and prove that it implies security of the round-robin entropy accumulation PRNG used by Windows 10, called Fortuna. Intuitively, our condition requires the input entropy "not to vary too wildly" within a given round-robin round.
4) We prove that the "root pool" approach (also used in Windows 10) is secure for general entropy inputs, provided that the system’s state is not compromised after system startup
Efficient Construction of (Distributed) Verifiable Random Functions
No full textWe give the first simple and efficient construction of {\em verifiable
random functions} (VRFs). VRFs, introduced by Micali et al. [MRV99],
combine the properties of regular pseudorandom functions (PRFs)
[GGM86] (i.e., indistinguishability from a random function) and
digital signatures [GMR88] (i.e., one can provide an unforgeable proof
that the VRF\ value is correctly computed). The efficiency of our VRF
construction is only slightly worse than that of a regular PRF
construction of Naor and Reingold [NR97]. In contrast to ours, the
previous VRF constructions [MRV99,Lys02] all involved an expensive
generic transformation from verifiable unpredictable functions (VUFs),
while our construction is simple and direct.
We also provide the first construction of {\em distributed} VRFs. Our
construction is more efficient than the only known construction of
distributed (non-verifiable) PRFs [Nie02], but has more applications
than the latter. For example, it can be used to distributively
implement the random oracle model in a {\em publicly verifiable}
manner, which by itself has many applications (e.g., constructing
threshold signature schemes).
Our main construction is based on a new variant of decisional
Diffie-Hellman (DDH) assumption on certain groups where the regular
DDH assumption does {\em not} hold. We do not make any claims about
the validity of our assumption (which we call {\em sum-free} DDH, or
sf-DDH). However, this assumption seems to be plausible based on our
{\em current} understanding of certain candidate elliptic and
hyper-elliptic groups which were recently proposed for use in
cryptography [JN01,Jou00]. We hope that the demonstrated power of our
sf-DDH assumption will serve as a motivation for its closer study
Exposure-Resilient Cryptography
No full textWe develop the notion of Exposure-Resilient Cryptography. While standard cryptographic definitions and constructions do not guarantee any security even if a tiny fraction of the secret entity (e.g., cryptographic key) is compromised, the objective of Exposure-Resilient Cryptography is to build information structures such that almost complete (intentional or unintentional) exposure of such a structure still protects the secret information embedded in this structure. The key to our approach is a new primitive of independent interest, which..
Beating Shannon requires BOTH efficient adversaries AND non-zero advantage
Full text linkIn this note we formally show a folklore (but, to the best of our knowledge, not documented) fact that in order to beat the famous Shannon lower bound on key length for one-time-secure encryption, one must *simultaneously* restrict the attacker to be efficient, and also allow the attacker to break the system with some non-zero (i.e., negligible) probability. Despite being folklore , we were unable to find a clean and simple proof of this result, despite asking several experts in the field. We hope that cryptography instructors will find this note useful when justifying the transition from information-theoretic to computational cryptography.
We note that our proof cleanly handles *probabilistic* encryption, as well as a small *decryption error*
- …
