More Like this

1. Nonmalleable Digital Lockers and Robust Fuzzy Extractors in the Plain Model

   https://doi.org/10.1007/978-3-031-22972-5_13  

   Apon, Daniel; Cachet, Chloe; Fuller, Benjamin; Hall, Peter; Liu, Feng-Hao (January 2023, Advances in Cryptology - Asiacrypt)

   We give the first constructions in the plain model of 1) nonmalleable digital lockers (Canetti and Varia, TCC 2009) and 2) robust fuzzy extractors (Boyen et al., Eurocrypt 2005) that secure sources with entropy below 1/2 of their length. Constructions were previously only known for both primitives assuming random oracles or a common reference string (CRS). Along the way, we define a new primitive called a nonmalleable point function obfuscation with associated data. The associated data is public but protected from all tampering. We use the same paradigm to then extend this to digital lockers. Our constructions achieve nonmalleability over the output point by placing a CRS into the associated data and using an appropriate non-interactive zero-knowledge proof. Tampering is protected against the input point over low-degree polynomials and over any tampering to the output point and associated data. Our constructions achieve virtual black box security. These constructions are then used to create robust fuzzy extractors that can support low-entropy sources in the plain model. By using the geometric structure of a syndrome secure sketch (Dodis et al., SIAM Journal on Computing 2008), the adversary’s tampering function can always be expressed as a low-degree polynomial; thus, the protection provided by the constructed nonmalleable objects suffices. 

   more » « less
2. The Forms and Functions of Switch Reference in A’ingae

   https://doi.org/10.3390/languages8020137  

   AnderBois, Scott; Altshuler, Daniel; Silva, Wilson D. (June 2023, Languages)

   This paper examines switch reference (SR) in A’ingae, an understudied isolate language from Amazonian Ecuador. We present a theoretically informed survey of SR, identifying three distinct uses of switch reference: in clause chaining, adverbial clauses, and so-called ‘bridging’ clause linkage. We describe the syntactic and semantic properties of each use in detail, the first such description for A’ingae, showing that the three constructions differ in important ways. While leaving a full syntactic analysis to future work, we argue that these disparate properties preclude a syntactic account that unifies these three constructions to the exclusion of other environments without SR. Conversely, while a full semantic account is also left to future work, we suggest that a unified semantic account in terms of discourse coherence principles appears more promising. In particular, we propose that switch reference in A’ingae occurs in all and only the constructions that are semantically restricted to non-structuring coordinating coherence relations in the sense of Segmented Discourse Representation Theory. 

   more » « less
3. Shadow Cones: A Generalized Framework for Partial Order Embeddings

   Yu, Tao; Liu, Toni; Tseng, Albert; De_Sa, Christopher (May 2024, ICLR 2024)

   Hyperbolic space has proven to be well-suited for capturing hierarchical relations in data, such as trees and directed acyclic graphs. Prior work introduced the concept of entailment cones, which uses partial orders defined by nested cones in the Poincar'e ball to model hierarchies. Here, we introduce the ``shadow cones" framework, a physics-inspired entailment cone construction. Specifically, we model partial orders as subset relations between shadows formed by a light source and opaque objects in hyperbolic space. The shadow cones framework generalizes entailment cones to a broad class of formulations and hyperbolic space models beyond the Poincar'e ball. This results in clear advantages over existing constructions: for example, shadow cones possess better optimization properties over constructions limited to the Poincar'e ball. Our experiments on datasets of various sizes and hierarchical structures show that shadow cones consistently and significantly outperform existing entailment cone constructions. These results indicate that shadow cones are an effective way to model partial orders in hyperbolic space, offering physically intuitive and novel insights about the nature of such structures. 

   more » « less
4. Classes of preferential attachment and triangle preferential attachment models with power-law spectra

   https://doi.org/10.1093/comnet/cnz040  

   Eikmeier, Nicole; Gleich, David F (August 2020, Journal of Complex Networks)

   Estrada, Ernesto (Ed.)

   Abstract Preferential attachment (PA) models are a common class of graph models which have been used to explain why power-law distributions appear in the degree sequences of real network data. Among other properties of real-world networks, they commonly have non-trivial clustering coefficients due to an abundance of triangles as well as power laws in the eigenvalue spectra. Although there are triangle PA models and eigenvalue power laws in specific PA constructions, there are no results that existing constructions have both. In this article, we present a specific Triangle Generalized Preferential Attachment Model that, by construction, has non-trivial clustering. We further prove that this model has a power law in both the degree distribution and eigenvalue spectra. 

   more » « less
5. Symbolic Proofs for Lattice-Based Cryptography

   Barthe, Gilles; Fan, Xiong; Gancher, Joshua; Grégoire, Benjamin; Jacomme, Charlie; Shi, Elaine (January 2018, ACM Conf. on Computer and Communications Security)

   Symbolic methods have been used extensively for proving security of cryptographic protocols in the Dolev-Yao model, and more recently for proving security of cryptographic primitives and constructions in the computational model. However, existing methods for proving security of cryptographic constructions in the computational model often require significant expertise and interaction, or are fairly limited in scope and expressivity. This paper introduces a symbolic approach for proving security of cryptographic constructions based on the Learning With Errors assumption (Regev, STOC 2005). Such constructions are instances of lattice-based cryptography and are extremely important due to their potential role in post-quantum cryptography. Following (Barthe, Gre ́goire and Schmidt, CCS 2015), our approach combines a computational logic and deducibility problems—a standard tool for representing the adversary’s knowledge, the Dolev-Yao model. The computational logic is used to capture (indistinguishability-based) security notions and drive the security proofs whereas deducibility problems are used as side-conditions to control that rules of the logic are applied correctly. We then use AutoLWE, an implementation of the logic, to deliver very short or even automatic proofs of several emblematic constructions, including CPA- PKE (Gentry et al., STOC 2008), (Hierarchical) Identity-Based Encryption (Agrawal et al. Eurocrypt 2010), Inner Product Encryption (Agrawal et al. Asiacrypt 2011), CCA-PKE (Micciancio et al., Eurocrypt 2012). The main technical novelty beyond AutoLWE is a set of (semi-)decision procedures for deducibility problems, using extensions of Grobner basis computations for subalgebras in the (non-)commutative setting (instead of ideals in the commutative setting). Our procedures cover the theory of matrices, which is required for lattice-based assumption, as well as the theory of non-commutative rings, fields, and Diffie-Hellman exponentiation, in its standard, bilinear and multilinear forms. Additionally, AutoLWE supports oracle-relative assumptions, which are used specifically to apply (advanced forms of) the Leftover Hash Lemma, an information-theoretical tool widely used in lattice-based proofs. 

   more » « less