More Like this

1. Better Than Advertised: Improved Collision-Resistance Guarantees for MD-Based Hash Functions

   https://doi.org/10.1145/3133956.3134087  

   Bellare, Mihir; Jaeger, Joseph; Len, Julia (January 2017, CCS '17 Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security)

   The MD transform that underlies the MD and SHA families iterates a compression function h to get a hash function H. The question we ask is, what property X of h guarantees collision resistance (CR) of H? The classical answer is that X itself be CR. We show that weaker conditions X, in particular forms of what we call constrained-CR, suffice. This reduces demands on compression functions, to the benefit of security, and also, forensically, explains why collision-finding attacks on compression functions have not, historically, lead to immediate breaks of the corresponding hash functions. We obtain our results via a definitional framework called RS security, and a parameterized treatment of MD, that also serve to unify prior work and variants of the transform. 

   more » « less
2. A GENERALIZATION OF A MICROLOCAL VERSION OF BOCHNER’S THEOREM

   https://doi.org/10.1090/tran/8425  

   Berhanu, S. (April 2021, Transactions of the American Mathematical Society)

   We prove a generalization of the microlocal version of Bochner’s tube theorem obtained in Baouendi and Tr`eves [Indiana Univ. Math. J. 31 (1982), pp. 885–895]. The results provide a class of CR structures where CR functions extend holomorphically to a full neighborhood of a point which may be of infinite type. 

   more » « less
3. A generalization of a micro local version of Bochner's theorem

   Berhanu, S. (April 2021, Transactions of the American Mathematical Society)

   We prove a generalization of the microlocal version of Bochner’s tube theorem obtained in Baouendi and Tr`eves [Indiana Univ. Math. J. 31 (1982), pp. 885–895]. The results provide a class of CR structures where CR functions extend holomorphically to a full neighborhood of a point which may be of infinite type. 

   more » « less
4. On the Complexity of Learning a Class Ratio from Unlabeled Data

   https://doi.org/10.1613/jair.1.12013  

   Fish, Benjamin; Reyzin, Lev (September 2020, Journal of Artificial Intelligence Research)

   In the problem of learning a class ratio from unlabeled data, which we call CR learning, the training data is unlabeled, and only the ratios, or proportions, of examples receiving each label are given. The goal is to learn a hypothesis that predicts the proportions of labels on the distribution underlying the sample. This model of learning is applicable to a wide variety of settings, including predicting the number of votes for candidates in political elections from polls. In this paper, we formally define this class and resolve foundational questions regarding the computational complexity of CR learning and characterize its relationship to PAC learning. Among our results, we show, perhaps surprisingly, that for finite VC classes what can be efficiently CR learned is a strict subset of what can be learned efficiently in PAC, under standard complexity assumptions. We also show that there exist classes of functions whose CR learnability is independent of ZFC, the standard set theoretic axioms. This implies that CR learning cannot be easily characterized (like PAC by VC dimension). 

   more » « less
5. Hybrid Simulations of the Resonant and Non-Resonant Cosmic Ray Streaming Instability

   Haggerty, C.; Caprioli, D.; Zweibel, E. (July 2019, 36th International Cosmic Ray Conference (ICRC2019))

   Using hybrid simulations (kinetic ions--fluid electrons), we test the linear theory predictions of the cosmic ray (CR) streaming instability. We consider two types of CR distribution functions: a "hot" distribution where CRs are represented by a drifting power law in momentum and an anisotropic "beam" of monochromatic particles. Additionally, for each CR distribution we scan over different CR densities to transition from triggering the resonant to the non-resonant (Bell) streaming instability. We determine the growth rates of these instabilities in simulations by fitting an exponential curve during the linear stage, and we show that they agree well with the theoretical predictions as a function of wave number agree. We also examine the magnetic helicity as a function of time and wave number, finding a general good agreement with the predictions, as well as some unexpected non-linear features to the instability development. 

   more » « less