We use cookies on this site. By browsing our site you agree to our use of cookies. Close this message Find out more

Home > Information Security home > Events > ISG Research Seminar 30 January 2014
More in this section Events articles

ISG Research Seminar 30 January 2014

30/01/2014 (11:00-12:00)

Contact: Lorenzo Cavallaro


Speaker: Martin Albrecht (Royal Holloway University of London, UK)

Martin obtained his Diplom in Computer Science from Universität Bremen and his PhD at the Information Security Group, Royal Holloway, University of London under the supervision of Carlos Cid. He then moved on to work in the group of Jean-Charles Faugère in Paris and Lars Knudsen in Copenhagen. In January 2014 he re-joined the ISG at Royal Holloway to work with Kenny Paterson on multilinear maps.

Title: Lazy Modulus Switching for the BKW Algorithm on LWE


Some recent constructions based on LWE do not sample the secret uniformly atrandom but rather from some distribution which produces small entries. The most prominent of these is the binary-LWE problem where the secret vector is sampled from {0, 1}* or{-1, 0, 1}*. We present a variant of the BKW algorithm for binary-LWE and other small secret variants and show that this variant reduces the complexity for solving binary-LWE. We also give estimates for the cost of solving binary-LWE instances in this setting and demonstrate the advantage of this BKW variant over standard BKW and lattice reduction techniques applied to the SIS problem. Our variant can be seen as a combination of theBKW algorithm with a lazy variant of modulus switching which might be of independent interest.


Comment on this page

Did you find the information you were looking for? Is there a broken link or content that needs updating? Let us know so we can improve the page.

Note: If you need further information or have a question that cannot be satisfied by this page, please call our switchboard on +44 (0)1784 434455.

This window will close when you submit your comment.

Add Your Feedback