Large Modulus Ring-LWE and Module-LWE

Our paper Large Modulus Ring-LWE ≥ Module-LWE — together with Amit Deo — was accepted at AsiaCrypt 2017. Here’s the abstract:

We present a reduction from the module learning with errors problem (MLWE) in dimension $d$ and with modulus $q$ to the ring learning with errors problem (RLWE) with modulus $q^{d}$. Our reduction increases the LWE error rate $\alpha$ by a quadratic factor in the ring dimension $n$ and a square root in the module rank $d$ for power-of-two cyclotomics. Since, on the other hand, MLWE is at least as hard as RLWE, we conclude that the two problems are polynomial-time equivalent. As a corollary, we obtain that the RLWE instance described above is equivalent to solving lattice problems on module lattices. We also present a self reduction for RLWE in power-of-two cyclotomic rings that halves the dimension and squares the modulus while increasing the error rate by a similar factor as our MLWE to RLWE reduction. Our results suggest that when discussing hardness to drop the RLWE/MLWE distinction in favour of distinguishing problems by the module rank required to solve them.

Our reduction is an application of the main result from Classical Hardness of Learning with Errors in the context of MLWE. In its simplest form, that reduction proceeds from the observation that for $\mathbf{a}, \mathbf{s} \in \mathbb{Z}_{q}^{d}$ with $\mathbf{s}$ small it holds that

$q^{d-1} \cdot \langle{\mathbf{a},\mathbf{s}}\rangle \approx \left(\sum_{i=0}^{d-1} q^{i} \cdot a_{i}\right) \cdot \left(\sum_{i=0}^{d-1} q^{d-i-1} \cdot s_{i}\right) \bmod q^{d} = \tilde{a} \cdot \tilde{s} \bmod q^{d}.$

Thus, if there exists an efficient algorithm solving the problem in $\mathbb{Z}_{q^d}$, we can use it to solve the problem in $\mathbb{Z}_{q}^d$.

In our paper, we essentially show that we can replace integers mod $q$ resp. $q^d$ with the ring of integers $R$ of a Cyclotomic field (considered mod $q$ resp. $q^d$). That is, we get the analogous reduction from $R_{q}^d$ (MLWE) to $R_{q^d}$ (RLWE). The bulk of our paper is concerned with making sure that the resulting error distribution is sound. This part differs from the Classical Hardness paper since our target distribution is in $R$ rather than $\mathbb{Z}$.

Revisiting the Expected Cost of Solving uSVP and Applications to LWE

Our — together with Florian Göpfert, Fernando Virdia and Thomas Wunderer — paper Revisiting the Expected Cost of Solving uSVP and Applications to LWE is now available on ePrint. Here’s the abstract:

Reducing the Learning with Errors problem (LWE) to the Unique-SVP problem and then applying lattice reduction is a commonly relied-upon strategy for estimating the cost of solving LWE-based constructions. In the literature, two different conditions are formulated under which this strategy is successful. One, widely used, going back to Gama & Nguyen’s work on predicting lattice reduction (Eurocrypt 2008) and the other recently outlined by Alkim et al. (USENIX 2016). Since these two estimates predict significantly different costs for solving LWE parameter sets from the literature, we revisit the Unique-SVP strategy. We present empirical evidence from lattice-reduction experiments exhibiting a behaviour in line with the latter estimate. However, we also observe that in some situations lattice-reduction behaves somewhat better than expected from Alkim et al.’s work and explain this behaviour under standard assumptions. Finally, we show that the security estimates of some LWE-based constructions from the literature need to be revised and give refined expected solving costs.

Our work is essentially concerned with spelling out in more detail and experimentally verifying a prediction made in the New Hope paper on when lattice reduction successfully recovers an unusually short vector.

Denoting by $v$ the unusually short vector in some lattice $\Lambda$ of dimension $d$ (say, derived from some LWE instance using Kannan’s embedding), $\beta$ the block size used for the BKZ algorithm and $\delta_0$ the root-Hermite factor for $\beta$, then the New Hope paper predicts that $v$ can be found if

$\sqrt{\beta/d} \|v\| \leq \delta_0^{2\beta-d} \, {\mathrm{Vol}(\Lambda)}^{1/d},$

under the assumption that the Geometric Series Assumption holds (until a projection of the unusually short vector is found).

The rationale is that this condition ensures that the projection of $v$ orthogonally to the first $d-\beta$ (Gram-Schmidt) vectors (denoted as $\pi_{d-\beta+1}(v)$) is shorter than the expectation for the $d-\beta+1$-th Gram-Schmidt vector $b_{d-\beta+1}^*$ under the GSA and thus would be found by the SVP oracle when called on the last block of size $\beta$. Hence, for any $\beta$ satisfying the above inequality, the actual behaviour would deviate from that predicted by the GSA. Finally, the argument can be completed by appealing to the intuition that a deviation from expected behaviour on random instances — such as the GSA — leads to a revelation of the underlying structural, secret information. In any event, such a deviation would already solve Decision-LWE.

In our work, we spell out this argument in more detail (e.g. how $v$ is recovered from $\pi_{d-\beta+1}(v)$) and throw 23k core hours at the problem of checking if the predicted behaviour, e.g.

matches the observed behaviour, e.g.

Just like for the above plots, the general answer is a clear “yes”.

Pretty Pictures or GTFO

I forgot the most important bit. The behaviour of the BKZ algorithm on uSVP(-BDD) instances can be observed in this video.

You can observe the basis approaching the GSA until the SVP oracle finds the unusually short vector $\pi_{d-\beta+1}(v)$. From $\pi_{d-\beta+1}(v)$, $v$ is then immediately recovered using size reduction. The grey area is the currently worked on block. The notation in the legend isn’t consistent with the plots above or even internally ($n$ v $d$), but the general idea should still be apparent. In case you’re wondering about the erratic behaviour of the tails (which occasionally goes all over the place), this is due to a bug in fpylll which has recently been fixed.

Reading Material on Gender Essentialism

In a memo titled Google’s Ideological Echo Chamber James Damore claims that “the distribution of preferences and abilities of men and women differ in part due to biological causes and that these differences may explain why we don’t see equal representation of women in tech and leadership” with the aim to show that “discrimination to reach equal representation is unfair, divisive, and bad for business.” Soon after the memo went viral, tech sites such as Hacker News started to see supportive statements. Motherboard reports that the verdicts expressed in the memo have some traction amongst the author’s former co-workers. It stands to reason that this agreement is not the privilege of Google employees, or as Alice Goldfuss put it:

I’ve read the Google anti-diversity screed and you should, too. You meaning men. Women have heard this shit before. Why should men read it? Because it’s a 10 page essay that eloquently tears away the humanity of women and non-white men. It uses bullet points and proper spelling and sounds very calm and convincing. And it should, because it was written by one of your peers.

— Alice Goldfuss (@alicegoldfuss) August 5, 2017

While I do not work in (US) “tech” (I’m an academic cryptographer at a British university), I guess the fields are close enough. Besides, gender essentialism is a prevalent idea beyond the confines of STEM disciplines. As mentioned above, the memo offers a bullet point list to support its claim:

1. [The differences between men and women] are universal across human cultures
2. They often have clear biological causes and links to prenatal testosterone
3. Biological males that were castrated at birth and raised as females often still identify and act like males
4. The underlying traits are highly heritable
5. They’re exactly what we would predict from an evolutionary psychology perspective

The memo and its defenders accuse those who disagree with its claims as being ideologically driven moralists1, hence the memo’s title. Alas, since I read several good critiques and their source material over the last few days, I figured I might attempt to summarise some of these arguments.2 Initially, my plan was to simply dump a list of books and articles here, but reading around as someone not so familiar with this literature, I found this mode of presentation (“well, my meta-study says your meta-study is full of it”) rather unhelpful. Thus, I opted for spelling out in more detail which arguments I found particularly illuminating.3

Postdoc at Royal Holloway on Quantum-Safe Cryptography in Hardware

Together with Carlos Cid, we have a two-year postdoc position available. The position is focused on hardware implementations of quantum-safe cryptography such as lattice-based, code-based, hash-based or mq-based schemes. If you are interested, feel free to get in touch with Carlos or me. If you know of somone who might be interested, we would appreciate if you could make them aware of this position.

Adventures in Cython Templating

Fpylll makes heavy use to Cython to expose Fplll’s functionality to Python. Fplll, in turn, makes use of C++ templates. For example, double, long double, dd_real (http://crd.lbl.gov/~dhbailey/mpdist/) and mpfr_t (http://www.mpfr.org/) are supported as floating point types. While Cython supports C++ templates, we still have to generate code for all possible instantiations of the C++ templates for Python to use/call. The way I implemented these bindings is showing its limitations. For example, here’s how attribute access to the dimension of the Gram-Schmidt object looks like:

    @property
def d(self):
"""
Number of rows of B (dimension of the lattice).

>>> from fpylll import IntegerMatrix, GSO, set_precision
>>> A = IntegerMatrix(11, 11)
>>> M = GSO.Mat(A)
>>> M.d
11

"""
if self._type == gso_mpz_d:
return self._core.mpz_d.d
IF HAVE_LONG_DOUBLE:
if self._type == gso_mpz_ld:
return self._core.mpz_ld.d
if self._type == gso_mpz_dpe:
return self._core.mpz_dpe.d
IF HAVE_QD:
if self._type == gso_mpz_dd:
return self._core.mpz_dd.d
if self._type == gso_mpz_qd:
return self._core.mpz_qd.d
if self._type == gso_mpz_mpfr:
return self._core.mpz_mpfr.d

if self._type == gso_long_d:
return self._core.long_d.d
IF HAVE_LONG_DOUBLE:
if self._type == gso_long_ld:
return self._core.long_ld.d
if self._type == gso_long_dpe:
return self._core.long_dpe.d
IF HAVE_QD:
if self._type == gso_long_dd:
return self._core.long_dd.d
if self._type == gso_long_qd:
return self._core.long_qd.d
if self._type == gso_long_mpfr:
return self._core.long_mpfr.d

raise RuntimeError("MatGSO object '%s' has no core."%self)



In the code above uppercase IF and ELSE are compile-time conditionals, lowercase if and else are run-time checks. If we wanted to add Z_NR<double> to the list of supported integer types (yep, Fplll supports that), then the above Python approximation of a switch/case statement would grow by a factor 50%. The same would have to be repeated for every member function or attribute. There must be a more better way.

CCA Conversions

In Tightly Secure Ring-LWE Based Key Encapsulation with Short Ciphertexts we — together with Emmanuela Orsini, Kenny Paterson, Guy Peer and Nigel Smart — give a tight reduction of Alex Dent’s IND-CCA secure KEM conversion (from an OW-CPA schemes) when the underlying scheme is (Ring-)LWE:

Abstract: We provide a tight security proof for an IND-CCA Ring-LWE based Key Encapsulation Mechanism that is derived from a generic construction of Dent (IMA Cryptography and Coding, 2003). Such a tight reduction is not known for the generic construction. The resulting scheme has shorter ciphertexts than can be achieved with other generic constructions of Dent or by using the well-known Fujisaki-Okamoto constructions (PKC 1999, Crypto 1999). Our tight security proof is obtained by reducing to the security of the underlying Ring-LWE problem, avoiding an intermediate reduction to a CPA-secure encryption scheme. The proof technique maybe of interest for other schemes based on LWE and Ring-LWE.

16th IMA International Conference on Cryptography and Coding

IMA-CCC is a crypto and coding theory conference biennially held in the UK. It was previously held in Cirencester. So you might have heard of it as the “Cirncester” conference. However, it has been moved to Oxford, so calling it Cirencester now is a bit confusing. Anyway, it is happening again this year. IMA is a small but fine conference with the added perk of being right before Christmas. This is great because around that time of the year Oxford is a fairly Christmas-y place to be.

12 – 14 December 2017, St Catherine’s College, University of Oxford