IACR News item: 30 April 2012
Leo Ducas, Alain Durmus
ePrint Report(Eurocrypt 2010), has been steadily finding many uses in numerous
cryptographic applications. Still, the Ring-LWE problem defined
in [LPR10] involves the
fractional ideal $R^\\vee$, the dual of the ring $R$, which is the
source of many theoretical and implementation technicalities. Until
now, getting rid of $R^\\vee$, required some relatively complex
transformation that substantially increase the magnitude of the
error polynomial and the practical complexity to sample it.
It is only for rings $R=\\Z[X]/(X^n+1)$ where $n$ a power of
$2$, that this transformation is simple and benign.
In this work we show that by applying a different, and much simpler
transformation, one can transfer the results from [LPR10] into an ``easy-to-use\'\' Ring-LWE setting ({\\em i.e.} without the dual ring $R^\\vee$), with only a very
slight increase in the magnitude of the noise coefficients.
Additionally, we show that creating the correct noise distribution
can also be simplified by generating a Gaussian distribution over a
particular extension ring of $R$, and then performing a reduction
modulo $f(X)$. In essence, our results show that one does not need
to resort to using any algebraic structure that is more complicated
than polynomial rings in order to fully utilize the hardness of the
Ring-LWE problem as a building block for cryptographic applications.
Additional news items may be found on the IACR news page.