Nanyang Technological University

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.

The Bayesian approach to inverse problems is of paramount importance in quantifying uncertainty about the input to and the state of a system of interest given noisy observations. Herein we consider the forward problem of the forced 2D Navier Stokes equation. The inverse problem is inference of the forcing, and possibly the initial condition, given noisy observations of the velocity field. We place a prior on the forcing which is in the form of a spatially correlated temporally white Gaussian process, and formulate the inverse problem for the posterior distribution. Given appropriate spatial regularity conditions, we show that the solution is a continuous function of the forcing. Hence, for appropriately chosen spatial regularity in the prior, the posterior distribution on the forcing is absolutely continuous with respect to the prior and is hence well-defined. Furthermore, the posterior distribution is a continuous function of the data.

\\ \\

This is a joint work with Andrew Stuart and Kody Law (Warwick)

We study the problem of covering R^d by overlapping translates of a convex polytope, such that almost every point of R^d is covered exactly k times. Such a covering of Euclidean space by a discrete set of translations is called a k-tiling. The investigation of simple tilings by translations (which we call 1-tilings in this context) began with the work of Fedorov and Minkowski, and was later extended by Venkov and McMullen to give a complete characterization of all convex objects that 1-tile R^d. By contrast, for k ≥ 2, the collection of polytopes that k-tile is much wider than the collection of polytopes that 1-tile, and there is currently no known analogous characterization for the polytopes that k-tile. Here we first give the necessary conditions for polytopes P that k-tile, by proving that if P k-tiles R^d by translations, then it is centrally symmetric, and its facets are also centrally symmetric. These are the analogues of Minkowski’s conditions for 1-tiling polytopes, but it turns out that very new methods are necessary for the development of the theory. In the case that P has rational vertices, we also prove that the converse is true; that is, if P is a rational, centrally symmetric polytope, and if P has centrally symmetric facets, then P must k-tile R^d for some positive integer k.