The Ring-LWE Problem in Lattice-Based Cryptography: The Case of Twisted Embeddings.

Several works have characterized weak instances of the Ring-LWE problem by exploring vulnerabilities arising from the use of algebraic structures. Although these weak instances are not addressed by worst-case hardness theorems, enabling other ring instantiations enlarges the scope of possible applications and favors the diversification of security assumptions. In this work, we extend the Ring-LWE problem in lattice-based cryptography to include algebraic lattices, realized through twisted embeddings. We define the class of problems Twisted Ring-LWE, which replaces the canonical embedding by an extended form. By doing so, we allow the Ring-LWE problem to be used over maximal real subfields of cyclotomic number fields. We prove that Twisted Ring-LWE is secure by providing a security reduction from Ring-LWE to Twisted Ring-LWE in both search and decision forms. It is also shown that the twist factor does not affect the asymptotic approximation factors in the worst-case to average-case reductions. Thus, Twisted Ring-LWE maintains the consolidated hardness guarantee of Ring-LWE and increases the existing scope of algebraic lattices that can be considered for cryptographic applications. Additionally, we expand on the results of Ducas and Durmus (Public-Key Cryptography, 2012) on spherical Gaussian distributions to the proposed class of lattices under certain restrictions. As a result, sampling from a spherical Gaussian distribution can be done directly in the respective number field while maintaining its format and standard deviation when seen in Zn via twisted embeddings.

The Fisher-Rao Distance between Multivariate Normal Distributions: Special Cases, Bounds and Applications.

The Fisher-Rao distance is a measure of dissimilarity between probability distributions, which, under certain regularity conditions of the statistical model, is up to a scaling factor the unique Riemannian metric invariant under Markov morphisms. It is related to the Shannon entropy and has been used to enlarge the perspective of analysis in a wide variety of domains such as image processing, radar systems, and morphological classification. Here, we approach this metric considered in the statistical model of normal multivariate probability distributions, for which there is not an explicit expression in general, by gathering known results (closed forms for submanifolds and bounds) and derive expressions for the distance between distributions with the same covariance matrix and between distributions with mirrored covariance matrices. An application of the Fisher-Rao distance to the simplification of Gaussian mixtures using the hierarchical clustering algorithm is also presented.