BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Carl Bootland (KU Leuven)\, Wouter Castryck (KU Leuven)\, and Fred erik Vercauteren (KU Leuven) DTSTART:20200704T163000Z DTEND:20200704T170000Z DTSTAMP:20260423T200406Z UID:ANTS14/28 DESCRIPTION:Title: On the security of the multivariate ring learning with errors problem\ nby Carl Bootland (KU Leuven)\, Wouter Castryck (KU Leuven)\, and Frederik Vercauteren (KU Leuven) as part of Algorithmic Number Theory Symposium (A NTS XIV)\n\n\nAbstract\nThe Multivariate Ring Learning with Errors ($m$-RL WE) problem was introduced in 2015 by Pedrouzo-Ulloa\, Troncoso-Pastoriza and Pérez-González. Instead of working over a polynomial residue ring wi th one variable as in RLWE\, it works over a polynomial residue ring in se veral variables. However\, care must be taken when choosing the multivaria te rings for use in cryptographic applications as they can be either weak or simply equivalent to univariate RLWE. For example\, Pedrouzo-Ulloa et a l.\\ suggest using tensor products of cyclotomic rings\, in particular pow er-of-two cyclotomic rings. They claim incorrectly that the security incre ases with the product of the individual degrees. In this paper\, we presen t simple methods to solve the search $m$-RLWE problem far more efficiently than is stated in the current literature by reducing the problem to the R LWE problem in dimension equal to the maximal degree of its components (an d not the product) and where the noise increases with the square-root of t he degree of the other components. Our methods utilise the fact that the d efining cyclotomic polynomials share algebraically related roots. We use t hese methods to successfully attack the search variant of the $m$-RLWE pro blem for a set of parameters estimated to offer more than 2600 bits of sec urity\, and being equivalent to solving the bounded distance decoding prob lem in a highly structured lattice of dimension 16384\, in less than two w eeks of computation time or just a few hours if parallelized on 128 cores. \n\nChair: Divesh Aggarwal and Emmanuel Thomé\n LOCATION:https://researchseminars.org/talk/ANTS14/28/ END:VEVENT END:VCALENDAR