Sage & LMonade GSOC 2014

This year Sage and lmonade are mentoring organizations for the Google Summer of Code again. We have many exciting projects for students to work (from home) over the summer, get mentored by experts in the field and get paid by Google.

Note that projects are not limited to the ideas presented on these pages. That is, if you have a nice project you’d like to propose, by all means do so! The application deadline for students is March 21st. These days they should be talking to potential mentors and forming an applications. If you know any student who might be interested or have access to any forum such students might read, please forward this announcement.

Cryptanalysis of the FHE based on GACD?

Jintai Ding and Chengdong Tao published a new preprint on the IACR’s ePrint titled A New Algorithm for Solving the Approximate Common Divisor Problem and Cryptanalysis of the FHE based on GACD.

Abstract. In this paper, we propose a new algorithm for solving the approximate common divisors problems, which is based on LLL reduction algorithm of certain special lattice and linear equation solving algorithm over integers. Through both theoretical argument and experimental data, we show that our new algorithm is a polynomial time algorithm under reasonable assumptions on the parameters. We use our algorithm to solve concrete problems that no other algorithm could solve before. Further more, we show that our algorithm can break the fully homomorphic encryption schemes, which are based on the approximate common divisors problem, in polynomial time in terms of the system parameter λ.

It is worth emphasising that the Approximate GCD problem not only underpins one of the few fully homomorphic encryption schemes we have but it is also somewhat related to one of two candidates for multilinear maps. So if it could be shown to be easy then this would be somewhat sad as the choice of problems for building fancy crypto schemes would have gotten a lot smaller. So what is the Approxmiate GCD problem? Continue reading

Three sweet but short postdocs in France

The HPAC project has three one-year postdoc positions available:

Three research positions (postdoc or research engineer), offered by the French ANR project HPAC  (High Performance Algebraic Computation), are open.

Title: High Performance Algebraic Computing

Keywords: parallel computing, computer algebra, linear algebra, C/C++ programming


  • Grenoble, France (LIG-MOAIS, LJK-CASYS),
  • Lyon, France (LIP-AriC),
  • Paris, France (LIP6-PolSys),

Starting date: between June 2014 and January 2015

Type of position: 3 postdoc or research engineer positions of 1 year each

Detailed descriptions:

General Context:

The ambition of the project HPAC is to provide international reference high-performance libraries for exact linear algebra and algebraic systems on multi-processor architectures and to influence parallel programming approaches for algebraic computing. It focuses on the design of new parallel algorithms and building blocks dedicated to exact linear algebra routines. These blocks will then be used for the parallelization of the sequential code of the LinBox and FGb libraries, state of the art for exact linear algebra and polynomial systems solving, and used in many computer algebra systems. The project combines several areas of expertise: parallel runtime and language, exact,
symbolic and symbolic/numeric algorithmic, and software engineering.

Profile of the positions:

We are seeking for candidates with solid expertise in software library design and developments (e.g. C, C++, OpenMP, Autotools, versioning,…) with preferably good background on mathematical software and computer algebra algorithmic. The main outcome of the work will depend on the type of the position (postdoc or engineer) and include code development in open-source C/C++ libraries such as LinBox, FGb, Kaapi and research publications in international journals or conferences.

Each location is seeking for candidates matching with the following keywords:

  • Lyon: (contact: Gilles… High performance/parallel computer algebra, symbolic and mixed symbolic-numeric linear algebra,  validated computation, high performance Euclidean lattice computation, lattice basis reduction.
  • Grenoble: (contact: Jean-Guill… Library design and development, LinBox, Sage, XKaapi, parallel exact linear algebra, work-stealing and data-flow tasks.
  • Paris: (contact: Jean-Charl… Polynomial system solving, Gröbner basis computations, parallel exact linear algebra, algebraic cryptanalysis, distributed computing.

Feel free to exchange with the contact person of each site for further information.

Postdoc position in Cryptology at DTU

DTU has a postdoc position available in the crypto group. I can highly recommend working there.

Apply for the job at DTU Compute by completing the following form.

Department of Applied Mathematics and Computer Science, Technical University of Denmark, would like to invite applications for a Postdoc position of 18 months, starting 1 April 2014 or soon thereafter.

The topic of the project is lightweight cryptology, which regards scenarios involving strongly resource-constrained devices.

Candidates for the position should have a solid background in hardware design and automation and be able to work on the physical constraints and optimization of the hardware implementations or, alternatively, we will consider candidates with a strong cryptanalytic and mathematical background who are able to analyse the security of ciphers to be designed.

All candidates must have a PhD degree in applied mathematics, computer science, or engineering or academic qualifications equivalent to the PhD degree in engineering and they should have demonstrated qualifications in cryptology. The candidate must be well versed in written and spoken English.

We offer
We offer an interesting and challenging job in an international environment focusing on education, research, public-sector consultancy and innovation, which contribute to enhancing the economy and improving social welfare. We strive for academic excellence, collegial respect and freedom tempered by responsibility. The Technical University of Denmark (DTU) is a leading technical university in northern Europe and benchmarks with the best universities in the world.

Salary and terms of appointment
The Danish Research Council finances the positions. The appointment will be based on the collective agreement with the Confederation of Professional Associations. The allowance will be agreed with the relevant union.

Further Information
Further information can be obtained from Professor Lars R. Knudsen, DTU Compute, e-mail:

You can read more about DTU Compute on

Application procedure
Please submit your online application no later than 15 March 2014. Applications must be submitted as one PDF file containing all materials to be given consideration. To apply, please open the link “Apply online,” fill in the online application form, and attach all your materials in English in one PDF file. The file must include:

  • Application (cover letter)
  • CV
  • Diploma
  • List of publications

How to print at the ISG at Royal Holloway

It seems all the information on printing from proper operating systems at the Information Security Group at Royal Holloway, University of London available online is a bit outdated. So here’s what you should do when using CUPS:

  1. The URL for printing is lpd:// where USERNAME is your college username (it’s a random looking combination of letters and numbers). The trick I was missing for a long time was that you need to add your username. Thanks, Jacob.
  2. Download the right PPD for KONICA MINOLTA bizhub C452 from the Konica website.
  3. Now print to MA-Follow-Me, go to, say, the postroom, swipe your card and retrieve your sweet, sweet print outs.

Back at Royal Holloway

Since the beginning of this month I am back at the Information Security Group (which is now its own department) at Royal Holloway, University of London. In particular, I have a three year postdoc position on a project looking into multilinear maps. The project is with Kenny Paterson.

It seems the Information Security Group has grown considerably since 2010 (when I left), but maybe only more people attend the research seminar now. Speaking of which, they are open to all and here is this term’s schedule:

  • 16 Jan 2014 (Thu): Corrado Leita (Symantec Research Labs, EU), “Who switched off the lights? Detecting targeted attacks against the power grid“,  room ABLT3
  •  21 Jan 2014 (Tue): Viktor Mayer-Schönberger (University of Oxford, UK), TBD, room MLT
  • 30 Jan 2014 (Thu): Martin Albrecht (Royal Holloway University of London, UK), “Lazy Modulus Switching for the BKW Algorithm on LWE“, room ABLT3
  • 05 Feb 2014 (Wed): Elisabeth Oswald (University of Bristol, UK), TBD, room ABLT2
  • 13 Feb 2014 (Thu): Andreas Schaad (SAP, GE), TBD, room ABLT3
  • 20 Feb 2014 (Thu): TBA, room ABLT3
  • 27 Feb 2014 (Thu): Frederik Mennes (Vasco, UK), “Leveraging Trustworthy Computing Mechanisms to Enhance DIGIPASS Strong Authentication Technology“, room  ABLT3
  • 05 Mar 2014 (Wed): Emiliano De Cristofaro (University College London, UK), TBD, room ABLT3
  • 13 Mar 2014 (Thu): Leyla Bilge, (Symantec Research Labs, EU), TBD, room ABLT3 
  • 20 Mar 2014 (Thu): Andrew S. Tanenbaum (Vrije Universiteit Amsterdam, NL), TBD, room ABLT3
  • 27 Mar 2014 (Thu): Juan Caballero (IMDEA Software, ES), TBD, room ABLT3

Best check the official seminar website for updates to talk titles etc.

PS: In related old news for those who missed it: a few UK researchers got together and expressed their criticism of NSA’s and GCHQ’s undermining of cryptography. It’s a bit tame and to get a newline one needs a professor title apparently, but it’s a start.

BatzenCA – OpenPGP Key Management for Mailing Lists

Lately, I have been writing a little Python library which is aimed at managing OpenPGP encrypted mailing lists easier. In particular, it addresses the following scenario. A group of users setup a normal mailing list – say a Google group. To realise encryption all users encrypt to all users, say, by relying on Thunderbird’s/Enigmail’s “Per-Recipient Rules”. This is annoying, but doable for groups sufficiently small. However, doing all the mutual key authentications for all users would be a lot more annoying. Our users could rely on the web of trust, but many people who use encryption seem to be reluctant to publish a social graph on the Internet, so they’d rely on exchanging this information somewhat privately, e.g. on the list itself.

Hence, to make matters simpler, our mailing list might nominate a certification authority – one user they all trust who takes care of key verification and publishes signatures to those keys she verified. In the scenario I am concerned with this happens by irregular e-mails to the mailing list itself. BatzenCA is a set of Python tools to make the CA’s job easier. In particular, it helps to organise such irregular e-mails which inform users about added/removed keys – called “releases” in the package. It relies on SQLAlchemy and a patched version of PyME. I’ve been using it for a little while now and it seems to do what I want it to do. I wonder if anybody else has similar requirements where this set of tools could be useful?

Warning: While I know a little bit about cryptography and have quite a bit experience writing Python code, I am not an expert on security engineering and most software I write is rather mathematical, i.e. not aimed at practical security.