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.

Continue reading “CCA Conversions”

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

Continue reading “16th IMA International Conference on Cryptography and Coding”

Fplll Days 3: July 6 – 14, Amsterdam

We’ll have an fplll coding sprint aka “FPLLL Days” in July. This time around, we plan a slightly modified format compared to previous instances. That is, in order to encourage new developers to get involved, we plan to have a 2 day tutorial session (shorter or longer depending on participants/interest) before the start of FPLLL Days proper.

Continue reading “Fplll Days 3: July 6 – 14, Amsterdam”

fplll 5.1 and fpylll 0.2.4dev

New versions of fplll and fpylll were released today. I’ve reproduced release notes below for greater visibility. The biggest user-visible changes for fplll are probably that

  • CVP enumeration is not experimental any more,
  • support for external enumeration libraries (go write that GPU implementation of enumeration) was added and
  • support for OSX was greatly improved.

On the fpylll side, the biggest user-visible changes are probably various API updates and a much nicer strategy/framework for gathering statistics about BKZ.

The next version of fplll will contain support for LLL reduction on Gram matrices.

Continue reading “fplll 5.1 and fpylll 0.2.4dev”

10 PhD Positions at Royal Holloway’s Centre for Doctoral Training in Cyber Security

At Royal Holloway we once again have ten PhD positions in Cyber Security nee Information Security. The catch is that almost all of those positions are reserved for UK residents. Note that this does not mean nationality, see funding page (there might also be some wiggle room in some cases). For more information see the CDT website and the ISG website for what kind of research we do. Closing date is 30 April.

Welcome to the EPSRC Centre for Doctoral Training (CDT) in Cyber Security at Royal Holloway. The Centre was established in 2013, and has as its main objective to produce cohorts of highly-trained researchers with a broad understanding of cyber security.

The CDT is hosted by the Information Security Group (ISG), and provides multidisciplinary training to annual cohorts of around ten students each. The students follow a 4-year doctoral programme: the first phase consists of a taught component comprising 25 per cent of the programme. The remaining three years follow the more traditional path of doctoral studies, with each student undertaking research in an advanced topic in the field of cyber security. See the CDT Course of Study page for more information about the programme.

CDT recruitment typically runs from November to April, to select students for the CDT cohort starting every October. Selected applicants are awarded fully-funded PhD studentships (stipend and College fees) for four years. We consider applications from candidates with undergraduate and masters qualifications in a wide range of disciplines, including, but not limited to, mathematics, computer science, and electrical and electronic engineering.

We are now open for applications for the 2017/18 CDT cohort. We have a number of fully-funded studentships to award to qualified and eligible candidates, to start their PhD studies in September 2017. Closing date for receiving applications is 30 April 2017. We will however assess applications on an ongoing basis, and we reserve the right to make an offer to candidates before the closing date.

Please explore the links below to learn more about the entry requirements, funding and eligibility, and how to apply to Royal Holloway’s CDT in Cyber Security.

Two Lecturer Positions in the Information Security Group

My department – the Information Security Group at Royal Holloway, University of London – has two open positions. One 4 year teaching focused post and one permanent post with the usual research and teaching profile (similar to, say, a Junior Professor in Germany). It’s a nice place to work, there’s good research going on from cryptography and system security to human and social aspects of information security and the ISG hosts one of the two UK Centres for Doctoral Training in Cyber Security which means we have funding for 10 PhD students per year at the moment. Most teaching is at the MSc level.

Continue reading “Two Lecturer Positions in the Information Security Group”

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))