The role of Institute for Scientific Computing in SFB CROSSING (Cryptography-Based Security Solutions: Enabling Trust in New and Next Generation Computing Environments)
There will essentially be no security in present and next-generation computing environments without secure and efficient public-key encryption and digital signature schemes, as these are fundamental building blocks of many security solutions. For example, confidential communication is enabled by public-key encryption and remote software updates are authenticated by digital signatures. In addition, public-key schemes with advanced functionalities will be required, in particular homomorphic encryption schemes which support, for instance, privacy in cloud computing.
However, it is currently unclear if appropriate practical and secure public-key encryption and signature schemes will be available in the future. All practical schemes that are currently available will become insecure in the presence of future quantum computers. Indeed, there are strong international efforts to build large quantum computers. Also, no practical schemes with certain important properties are available at the moment, for example encryption schemes that are fully homomorphic. It is therefore crucial to come up with new secure and practical schemes that are able to protect applications of the future.
The project P1 in CROSSING, which is a joint effort of SC and the research group of Johannes Buchmann on cryptorgraphy is researching practical and secure lattice-based public-key encryption and signature schemes that satisfy the requirements of new and next-generation computing environments. In addition to schemes with basic functionalities, the project will also provide practical and quantum resistant homomorphic encryption schemes (in a single operation and somewhat) required by other projects in CROSSING.
To achieve its goal, the project meets two challenges. The first challenge is to assess the hardness of the underlying computational lattice problems in the presence of modern parallel computing architectures both experimentally and theoretically. This assessment permits selecting parameters for lattice-based cryptosystems that provide an aspired security level. Here, we also assess the hardness of these problems in the presence of quantum computers which presumably will become efficient in future.
The security of lattice-based schemes relies on the hardness of computational lattice problems. In particular, it relies on the hardness of the shortest vector problem (SVP) and its approximate version (aSVP). SVP consists in finding the shortest vector of a lattice, whereas in aSVP the goal is to find a lattice vector whose length is at most the length of the shortest vector of the lattice multiplied by an approximation factor. To properly estimate the power of the attacks that might be done, one has to implement SVP and aSVP-solvers on the most high-end current architectures, such as multi-core CPUs and GPUs.
