## On dual lattice attacks against small-secret LWE and parameter choices in HElib and SEAL

My paper on solving small, sparse secret instances is now on ePrint. Here’s the abstract:

We present novel variants of the dual-lattice attack against LWE in the presence of an unusually short secret. These variants are informed by recent progress in BKW-style algorithms for solving LWE. Applying them to parameter sets suggested by the homomorphic encryption libraries HElib and SEAL yields revised security estimates. Our techniques scale the exponent of the dual-lattice attack by a factor of $(2\,L)/(2\,L+1)$ when $\log q = \Theta{\left(L \log n\right)}$, when the secret has constant hamming weight $h$ and where $L$ is the maximum depth of supported circuits. They also allow to half the dimension of the lattice under consideration at a multiplicative cost of $2^{h}$ operations. Moreover, our techniques yield revised concrete security estimates. For example, both libraries promise 80 bits of security for LWE instances with $n=1024$ and $\log_2 q \approx {47}$, while the techniques described in this work lead to estimated costs of 68 bits (SEAL) and 62 bits (HElib).

If you want to see what its effect would be on your favourite small, sparse secret instance of LWE, the code for estimating the running time is included in our LWE estimator. The integration into the main function estimate_lwe is imperfect, though. To get you started, here’s the code used to produce the estimates for the rolling example in the paper.

• Our instance’s secret has hamming weight $h=64$ and a ternary secret. We always use sieving as the SVP oracle in BKZ:

sage: n, alpha, q = fhe_params(n=2048, L=2)
sage: kwds = {"optimisation_target": "sieve", "h":64, "secret_bounds":(-1,1)}

• We establish a base line:

sage: print cost_str(sis(n, alpha, q, optimisation_target="sieve"))

• We run the scaled normal form approach from Section 4 and enable amortising costs from Section 3 by setting use_lll=True:

sage: print cost_str(sis_small_secret_mod_switch(n, alpha, q, use_lll=True, **kwds))

• We run the approach from Section 5 for sparse secrets. Setting postprocess=True enables the search for solutions $\mathbf{s}_1$ with very low hamming weight (page 17):

sage: print cost_str(drop_and_solve(sis, n, alpha, q, postprocess=True, **kwds))

• We combine everything:

sage: f = sis_small_secret_mod_switch
sage: print cost_str(drop_and_solve(f, n, alpha, q, postprocess=True, **kwds))


## Postdoc position at Royal Holloway

We got a one year crypto postdoc position in the Information Security Group.

 Location Egham Salary £33,789 to £39,902 per annum – including London Allowance Closing Date Monday 10 October 2016 Interview Date To be confirmed Reference 0916-295

The ISG is seeking to recruit a post-doctoral research assistant to work in the area of Cryptography. The position is available now for the period of one year.

The PDRA will work alongside Prof. Kenny Paterson and other cryptographic researchers at Royal Holloway on topics in Cryptography. Our current areas of interest include lattice-based cryptography, multilinear maps, indistinguishability obfuscation, and applied cryptography.

Applicants should have already completed (essential if COS required), or be close to completing, a PhD in a relevant discipline. Applicants should have an outstanding research track record in Cryptography. Applicants should be able to demonstrate scientific creativity, research independence, and the ability to communicate their ideas effectively in written and verbal form.

This is a full time post, available as soon as possible for a fixed term period of 12 months. This post is based in Egham, Surrey, where the College is situated in a beautiful, leafy campus near to Windsor Great Park and within commuting distance from London.

Informal enquiries can be made to Kenny Paterson at kenny.paterson@rhul.ac.uk.

The Human Resources Department can be contacted with queries by email at: recruitment@rhul.ac.uk.

## London-ish Lattice Coding & Crypto Meeting: 21 September 2016

The next London-ish Lattice Coding & Crypto Meeting is coming up on September 21.

## Programme

• 11:00–12:30 | Jean-Claude Belfiore: Ideal Lattices: Connections between number fields and coding constructions
• 13:30–15:00 | Dan Shepherd: Rings and Modules for Identity-Based Post-Quantum Public-Key Cryptography
• 15:30–16:30 | Antonio Campello: Sampling Algorithms for Lattice Gaussian Codes
• 16:30–17:00 | Cong Ling: Lattice Gaussian Sampling with Markov Chain Monte Carlo (MCMC)
• 17:00–18:30 | Daniel Dadush: Solving SVP and CVP in 2^n Time via Discrete Gaussian Sampling

## Venue

Arts Building Ground Floor Room 24
Royal Holloway, University of London
Egham Hill
Egham
Surrey TW20 0EX

See meeting website for details.

## Handling Email with Emacs

Like many other people, I write, receive and loath a lot of email. Writing it goes something like this:

1. Create a new draft,
2. figure out the right address to put into the To: field,
3. write “Hi <first name>”,
4. write the actual message,
5. attach the correct file (if any),
6. append “Cheers, Martin”.

Also, a lot of email is repetitive and boring but necessary, such as asking seminar speakers for their titles and abstracts, giving people advise on how to claim reimbursement when they visit Royal Holloway, responding to requests of people who’d like to pursue a PhD.

Here is my attempt to semi-automate some of the boring steps in Emacs.

## fpylll

fpylll is a Python library for performing lattice reduction on lattices over the Integers. It is based on the fplll, a C++ library which describes itself as follows:

fplll contains several algorithms on lattices that rely on floating-point computations. This includes implementations of the floating-point LLL reduction algorithm, offering different speed/guarantees ratios. It contains a ‘wrapper’ choosing the estimated best sequence of variants in order to provide a guaranteed output as fast as possible. In the case of the wrapper, the succession of variants is oblivious to the user. It also includes a rigorous floating-point implementation of the Kannan-Fincke-Pohst algorithm that finds a shortest non-zero lattice vector, and the BKZ reduction algorithm.