L4

Pseudorandom functions (PRFs) are one of the fundamental building blocks in cryptography. Traditionally, there have been two main approaches for PRF design: the ``practitioner's approach'' of building concretely-efficient constructions based on known heuristics and prior experience, and the ``theoretician's approach'' of proposing constructions and reducing their security to a previously-studied hardness assumption. While both approaches have their merits, the resulting PRF candidates vary greatly in terms of concrete efficiency and design complexity. In this work, we depart from these traditional approaches by exploring a new space of plausible PRF candidates. Our guiding principle is to maximize simplicity while optimizing complexity measures that are relevant to cryptographic applications. Our primary focus is on weak PRFs computable by very simple circuits (depth-2 ACC^0 circuits). Concretely, our main weak PRF candidate is a ``piecewise-linear'' function that first applies a secret mod-2 linear mapping to the input, and then a public mod-3 linear mapping to the result. We also put forward a similar depth-3 strong PRF candidate.  
The advantage of our approach is twofold. On the theoretical side, the simplicity of our candidates enables us to draw many natural connections between their hardness and questions in complexity theory or learning theory (e.g., learnability of depth-2 ACC^0 circuits and width-3 branching programs, interpolation and property testing for sparse polynomials, and natural proof barriers for showing super-linear circuit lower bounds). On the applied side, the piecewise-linear structure of our candidates lends itself nicely to applications in secure multiparty computation (MPC). Using our PRF candidates, we construct protocols for distributed PRF evaluation that achieve better round complexity and/or communication complexity (often both) compared to protocols obtained by combining standard MPC protocols with PRFs like AES, LowMC, or Rasta (the latter two are specialized MPC-friendly PRFs).
Finally, we introduce a new primitive we call an encoded-input PRF, which can be viewed as an interpolation between weak PRFs and standard (strong) PRFs. As we demonstrate, an encoded-input PRF can often be used as a drop-in replacement for a strong PRF, combining the efficiency benefits of weak PRFs and the security benefits of strong PRFs. We conclude by showing that our main weak PRF candidate can plausibly be boosted to an encoded-input PRF by leveraging standard error-correcting codes.
Joint work with Dan Boneh, Yuval Ishai, Amit Sahai, and David J. Wu.

We provide lattice-based protocols allowing to prove relations among committed integers. While the most general zero-knowledge proof techniques can handle arithmetic circuits in the lattice setting, adapting them to prove statements over the integers is non-trivial, at least if we want to handle exponentially large integers while working with a polynomial-size modulus qq. For a polynomial L, we provide zero-knowledge arguments allowing a prover to convince a verifier that committed L-bit bitstrings x, y and z are the binary representations of integers X, Y and Z satisfying Z=X+Y over the integers. The complexity of our arguments is only linear in L. Using them, we construct arguments allowing to prove inequalities X <Z among committed integers, as well as arguments showing that a committed X belongs to a public interval [α,β], where α and β can be arbitrarily large. Our range arguments have logarithmic cost (i.e., linear in L) in the maximal range magnitude. Using these tools, we obtain zero-knowledge arguments showing that a committed element X does not belong to a public set S using soft-O(n⋅log|S|) bits of communication, where n is the security parameter. We finally give a protocol allowing to argue that committed L-bit integers X, Y and Z satisfy multiplicative relations Z=XY over the integers, with communication cost subquadratic in L. To this end, we use our protocol for integer addition to prove the correct recursive execution of Karatsuba's multiplication algorithm. The security of our protocols relies on standard lattice assumptions with polynomial modulus and polynomial approximation factor.

TBA

The celebrated localisation theorem of Beilinson-Bernstein asserts that there is an equivalence between representations of a Lie algebra and modules over the sheaf of differential operators on the corresponding flag variety. In this talk we discuss certain analogues of this result in various contexts. Namely, there is a localisation theorem for quantum groups due to Backelin and Kremnizer and, more recently, Ardakov and Wadsley also proved a localisation theorem working with certain completed enveloping algebras of p-adic Lie algebras. We then explain how to combine the ideas involved in these results to construct
a p-adic analytic quantum flag variety and a category of D-modules on it, and we show that the global section functor on these D-modules yields an equivalence of categories.

One of the main open problems in loop quantum gravity is to reconcile the fundamental quantum discreteness of space with general relativity in the continuum. In this talk, I present recent progress regarding this issue: I will explain, in particular, how the discrete spectra of geometric observables that we find in loop gravity can be understood from a conventional Fock quantisation of gravitational edge modes on a null surface boundary. On a technical level, these boundary modes are found by considering a quasi-local Hamiltonian analysis, where general relativity is treated as a Hamiltonian system in domains with inner null boundaries. The presence of such null boundaries requires then additional boundary terms in the action. Using Ashtekar’s original SL(2,C) self-dual variables, I will explain that the natural such boundary term is nothing but a kinetic term for a spinor (defining the null flag of the boundary) and a spinor-valued two-form, which are both intrinsic to the boundary. The simplest observable on the boundary phase space is the cross sectional area two-form, which generates dilatations of the boundary spinors. In quantum theory, the corresponding area operator turns into the difference of two number operators. The area spectrum is discrete without ever introducing spin networks or triangulations of space. I will also comment on a similar construction in three euclidean spacetime dimensions, where the discreteness of length follows from the quantisation of gravitational edge modes on a one-dimensional cross section of the boundary.
The talk is based on my recent papers: arXiv:1804.08643 and arXiv:1706.00479.
 

The (total) Steenrod square is a ring homomorphism from the cohomology of a topological space to the Z/2-equivariant cohomology of this space, with the trivial Z/2-action. Given a closed monotone symplectic manifold, one can define a deformed notion of the Steenrod square for quantum cohomology, which will not in general be a ring homomorphism, and prove some properties of this operation that are analogous to properties of the classical Steenrod square. We will then link this, in a more general setting, to a definition by Seidel of a similar operation on Floer cohomology.
 

The Hitchin fibration is a natural tool through which one can understand the moduli space of Higgs bundles and its interesting subspaces (branes). After reviewing the type of questions and methods considered in the area, we shall dedicate this talk to the study of certain branes which lie completely inside the singular fibres of the Hitchin fibrations. Through Cayley and Langlands type correspondences, we shall provide a geometric description of these objects, and consider the implications of our methods in the context of representation theory, Langlands duality, and within a more generic study of symmetries on moduli spaces.