I am an intern (I started yesterday) in a research lab on lattice based cryptography and I have a more mathematical background, in particular algebra.

I would like to know what type of algebraic problems intervene in lattice based cryptography?

I am supposed to do a phd and I would like to work more on algebraic aspects of cryptography, but I have no idea where to look at.

  • 1
    $\begingroup$ Shouldn't you ask your PhD supervisor for some direction? He's probably in a room around the corner :-) $\endgroup$
    – kodlu
    Mar 27 '19 at 23:32
  • $\begingroup$ Yeah sure, I should ask for it. But as I just started I am a bit shy hahaha. $\endgroup$
    – Pierre21
    Mar 28 '19 at 8:18

Studying lattices (and lattice-based schemes) does not necessary involves algebraic number theory (or other somehow advanced topics). The security reductions uses more aspects of complexity theory and probabilities. And the algorithms to solve lattices problems (for instance, to solve SVP, CVP, BDD, etc), in general, use more linear algebra.

I think you should check the structured versions of lattice-based problems (like RLWE and RSIS). For instance, the description of RLWE typically involves Cyclotomic number fields and the their rings of integers.

The manual A Toolkit for Ring-LWE Cryptography can be a good starting point.

But even if they use a lot of concepts from Number theory and Algebraic Number Theory, they are not necessarily based on problems studied in these fields (the security of schemes based on ring variants of LWE and SIS relies basically on the assumption that SVP and other lattice problems are still hard over the lattices generated by such structured problems... e.g. ideal lattices).

One problem that is maybe more related to algebra but is also studied in cryptography is the problem of finding short generators of principal ideals. You can easily find papers about it. For example, this one: Recovering Short Generators of Principal Ideals in Cyclotomic Rings.

  • $\begingroup$ Thank you very much for your answer ! I'm going to get a look at those papers ! $\endgroup$
    – Pierre21
    Mar 28 '19 at 8:19
  • $\begingroup$ Well I hope as a mathematician I could find someething to do with my knowledge in Lattices based crypto. $\endgroup$
    – Pierre21
    Mar 28 '19 at 12:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.