Andrew Mendelsohn

We propose a dimension-reducing transformation on Group Ring Learning with Errors (GRLWE) samples. We exhibit an efficiently computable isomorphism which takes samples defined over the group rings used in the construction of GRLWE to twice as many samples defined over matrix rings, in half the dimension. This is done by composing two maps: the first map is a transformation showing that the group rings used are orders in central simple algebras, and the second map takes the obtained central simple algebra to a matrix ring. When combined with lattice reduction on the resulting matrix samples, this gives an attack on the GRLWE problem. We extend this attack to other groups proposed for cryptographic use by the creators of GRLWE, and display some numerical results quantifying the effects of the transformation, using the `Lattice Estimator'. We then give a family of groups from which GRLWE-style group rings can be constructed which are immune to our attack, namely the generalized quaternion groups. Finally, we discuss the merits and vulnerabilities of a number of different forms of structured LWE.

We construct a provably-secure structured variant of Learning with Errors (LWE) using nonassociative cyclic division algebras, assuming the hardness of worst-case structured lattice problems, for which we are able to give a full search-to-decision reduction, improving upon the construction of Grover et al. named `Cyclic Learning with Errors' (CLWE). We are thus able to create structured LWE over cyclic algebras without any restriction on the size of secret spaces, which was required for CLWE as a result of its restricted security proof. We reduce the shortest independent vectors problem in ideal lattices, obtained from ideals in orders of such algebras, to the decision variant of LWE defined for nonassociative CDAs. We believe this variant has greater security and greater freedom with parameter choices than CLWE, and greater asymptotic efficiency of multiplication than module LWE. Our reduction requires new results in the ideal theory of such nonassociative algebras, which may be of independent interest. We then adapt an LPR-like PKE scheme to hold for nonassociative spaces, and discuss the efficiency and security of our construction, showing that it is immune to certain subfield attacks. Finally, we give example parameters to construct algebras for cryptographic use.

Let K be a totally real number field of degree n over [ ], with discriminant and regulator [ ], respectively. In this paper, using a similar method to van Woerden, we prove that the number of classes of perfect unary forms, up to equivalence and scaling, can be bounded above by [ ], where [ ] is the discriminant of the field K, [ ] is the additive Hermite–Humbert constant over positive-definite unary forms for K and [ ] is the covering radius of the log-unit lattice. In particular, when K is Galois over [ ] and n is a prime number, the number of homothety classes of unary forms is upper bounded by [ ], where [ ] is the regulator of K. Moreover, if K is a maximal totally real subfield of a cyclotomic field, the number of homothety classes of perfect unary forms is upper bounded by [ ].

It is shown that the commuting probability of a finite ring cannot be a fraction with square-free denominator, resolving a conjecture of Buckley and MacHale.