More Like this

1. Non-Uniform Bounds in the Random-Permutation, Ideal-Cipher, and Generic-Group Models

   https://doi.org/10.1007/978-3-319-96884-1_23  

   Coretti, Sandro; Dodis, Yevgeniy; Guo, Siyao (July 2018, Lecture notes in computer science)

   null (Ed.)

   The random-permutation model (RPM) and the ideal-cipher model (ICM) are idealized models that offer a simple and intuitive way to assess the conjectured standard-model security of many important symmetric-key and hash-function constructions. Similarly, the generic-group model (GGM) captures generic algorithms against assumptions in cyclic groups by modeling encodings of group elements as random injections and allows to derive simple bounds on the advantage of such algorithms. Unfortunately, both well-known attacks, e.g., based on rainbow tables (Hellman, IEEE Transactions on Information Theory ’80), and more recent ones, e.g., against the discrete-logarithm problem (Corrigan-Gibbs and Kogan, EUROCRYPT ’18), suggest that the concrete security bounds one obtains from such idealized proofs are often completely inaccurate if one considers non-uniform or preprocessing attacks in the standard model. To remedy this situation, this work defines the auxiliary-input (AI) RPM/ICM/GGM, which capture both non-uniform and preprocessing attacks by allowing an attacker to leak an arbitrary (bounded-output) function of the oracle’s function table; derives the first non-uniform bounds for a number of important practical applications in the AI-RPM/ICM, including constructions based on the Merkle-Damgård and sponge paradigms, which underly the SHA hashing standards, and for AI-RPM/ICM applications with computational security; and using simpler proofs, recovers the AI-GGM security bounds obtained by Corrigan-Gibbs and Kogan against preprocessing attackers, for a number of assumptions related to cyclic groups, such as discrete logarithms and Diffie-Hellman problems, and provides new bounds for two assumptions. An important step in obtaining these results is to port the tools used in recent work by Coretti et al. (EUROCRYPT ’18) from the ROM to the RPM/ICM/GGM, resulting in very powerful and easy-to-use tools for proving security bounds against non-uniform and preprocessing attacks. 

   more » « less
2. Phase-type bounds on network performance

   https://doi.org/10.1109/CISS.2018.8362284  

   Boroujeny, Massieh Kordi; Ephraim, Yariv; Mark, Brian L. (March 2018, 52nd Annual Conference on Information Sciences and Systems (CISS))

   Evaluation of end-to-end network performance using realistic traffic models is a challenging problem in networking. The classical theory of queueing networks is feasible only under rather restrictive assumptions on the input traffic models and network elements. An alternative approach, first proposed in the late 1980s, is to impose deterministic bounds on the input traffic that can be used as a basis for a network calculus to compute end-to-end network delay bounds. Such deterministic bounds are inherently loose as they must accommodate worst case scenarios. Since the early 1990s, efforts have shifted to development of a stochastic network calculus to provide probabilistic end-to-end performance bounds. In this paper, we capitalize on the approach of stochastically bounded burstiness (SBB) which was developed for a general class of bounding functions, and was demonstrated for a bound that is based on a mixture distribution. We specialize the SBB bounds to bounds based on the class of phase-type distributions, which includes mixture distributions as a particular case. We develop the phase-type bounds and demonstrate their performance. 

   more » « less
3. A Five Distance Theorem for Kronecker Sequences

   https://doi.org/10.1093/imrn/rnab205  

   Haynes, Alan; Marklof, Jens (September 2021, International Mathematics Research Notices)

   Abstract The three-distance theorem (also known as the three-gap theorem or Steinhaus problem) states that, for any given real number $$\alpha $$ and integer $$N$$, there are at most three values for the distances between consecutive elements of the Kronecker sequence $$\alpha , 2\alpha ,\ldots , N\alpha $$ mod 1. In this paper, we consider a natural generalization of the three-distance theorem to the higher-dimensional Kronecker sequence $$\vec \alpha , 2\vec \alpha ,\ldots , N\vec \alpha $$ modulo an integer lattice. We prove that in 2D, there are at most five values that can arise as a distance between nearest neighbors, for all choices of $$\vec \alpha $$ and $$N$$. Furthermore, for almost every $$\vec \alpha $$, five distinct distances indeed appear for infinitely many $$N$$ and hence five is the best possible general upper bound. In higher dimensions, we have similar explicit, but less precise, upper bounds. For instance, in 3D, our bound is 13, though we conjecture the truth to be 9. We furthermore study the number of possible distances from a point to its nearest neighbor in a restricted cone of directions. This may be viewed as a generalization of the gap length in 1D. For large cone angles, we use geometric arguments to produce explicit bounds directly analogous to the three-distance theorem. For small cone angles, we use ergodic theory of homogeneous flows in the space of unimodular lattices to show that the number of distinct lengths is (1) unbounded for almost all $$\vec \alpha $$ and (2) bounded for $$\vec \alpha $$ that satisfy certain Diophantine conditions. 

   more » « less
4. CHARACTER LEVELS AND CHARACTER BOUNDS

   https://doi.org/10.1017/fmp.2019.9  

   Guralnick, Robert; Larsen, Michael; Tiep, Pham Huu (January 2020, Forum of mathematics)

   We develop the concept of character level for the complex irreducible characters of finite, general or special, linear and unitary groups. We give characterizations of the level of a character in terms of its Lusztig label and in terms of its degree. Then we prove explicit upper bounds for character values at elements with not-too-large centralizers and derive upper bounds on the covering number and mixing time of random walks corresponding to these conjugacy classes. We also characterize the level of the character in terms of certain dual pairs and prove explicit exponential character bounds for the character values, provided that the level is not too large. Several further applications are also provided. Related results for other finite classical groups are obtained in the sequel [Guralnick et al. ‘Character levels and character bounds for finite classical groups’] 

   more » « less
5. Fragile Complexity of Comparison-Based Algorithms

   https://doi.org/10.4230/LIPIcs.ESA.2019.2  

   Afshani, P.; Fagerberg, R.; Hammer, D.; Jacob, R.; Kostitsyna, I.; Meyer, U.; Penschuck, M.; Sitchinava, N. (September 2019, Proceedings of the 27th European Symposium on Algorithms)

   We initiate a study of algorithms with a focus on the computational complexity of individual elements, and introduce the fragile complexity of comparison-based algorithms as the maximal number of comparisons any individual element takes part in. We give a number of upper and lower bounds on the fragile complexity for fundamental problems, including Minimum, Selection, Sorting and Heap Construction. The results include both deterministic and randomized upper and lower bounds, and demonstrate a separation between the two settings for a number of problems. The depth of a comparator network is a straight-forward upper bound on the worst case fragile complexity of the corresponding fragile algorithm. We prove that fragile complexity is a different and strictly easier property than the depth of comparator networks, in the sense that for some problems a fragile complexity equal to the best network depth can be achieved with less total work and that with randomization, even a lower fragile complexity is possible. 

   more » « less