Post-quantum Lattice-based Cryptography

Abstract: In a future full of quantum computers, new foundations for asymmetric cryptography are needed. We study the theoretical foundations for lattice-based cryptography as well as the current state on cryptographic attacks against them. We then turn our attention to signature systems and especially the system BLISS from 2013. We give an overview of the BLISS protocol and its security, and analyse its object sizes and resistance to attacks. We find that BLISS does not provide as high security as initially claimed. We then propose modifications to BLISS in order to allow for freer choices of dimension and modulus. We also propose novel implementation tricks and accommodate for these in the protocol. We call our modified system REBLISS and propose parameter sets. Our performance measurements suggest that this is a good alternative to BLISS.