Lattice-based privacy-preserving cryptography
Lattice-based cryptography is named after the mathematical object of a lattice, over which various interesting problems can be defined. The best known is the so-called "shortest vector problem" (SVP), which asks for the shortest vector in a given lattice. The special thing about this problem is that despite intensive research, no algorithm is known that solves the problem efficiently. Even more so, no quantum algorithm is known that solves the problem significantly faster, which contrasts with the factoring and discrete logarithm problems typically used in cryptography, which are solved by Shor's algorithm in polynomial time. Thus, lattice problems provide a way to develop post-quantum secure cryptography.
Typically, however, SVP is not used in the construction of lattice-based methods. Instead, one uses problems like "short integer solution" (SIS) or "learning with errors" (LWE) or their more efficient relatives RSIS and RLWE, which base their security only on a more structured class of lattices.
Besides the post-quantum security of lattice problems, there is another advantage. Lattices allow the construction of so-called "fully homomorphic encryption" (FHE). Here, it is possible to encrypt sensitive data and then compute on the data without knowing the data, i.e. while the data remains encrypted. As an example, it is possible for a hospital to give encrypted patient data to an external service provider so that the latter can calculate statistics on the patient data without having any information about the content of the patient data.
The equivalent of FHE with its encryptions exists for signatures, i.e. homomorphic signatures. They can be used to sign data and then, in parallel to a result about the data, to calculate a signature for the result without knowing the secret key. This makes ideas like "verifiable computation" possible, where, for example, you give signed data to an external service provider who computes statistics about the data, as with FHE. But instead of protecting the secrecy of the data, the service provider can compute a signature without the secret key for the result, so that afterwards you can verify that the result of the statistic was computed correctly.
One research direction of ours is to further develop homomorphic signatures. Here, for example, we are looking at how to improve so-called "context-hiding", which allows one not to be able to tell from a signature of a result which signatures contributed to the creation of the result signature. Another property of homomorphic signatures that we are trying to improve is aggregability. Here, we try to combine signatures from several sources into one signature, which is then shorter overall.
One of our research focuses is on lattice-based privacy-preserving cryptography. The goal here is to give users control over their own data, for example, to protect their anonymity. A classic example in this field is group signatures. Here there is a group, for example the employees of a company, who are all authorised to create a signature in the name of the group, for example to sign a contract. However, it should not be possible to distinguish who from the group has signed a contract, in order to prevent information about the users from being learned, for example, who takes care of which contracts in the company.
An extension of this idea are anonymous reputation systems. These form the privacy-preserving counterpart to customer ratings in online portals. While at present it is clear to see which customer has rated which trader and how, with anonymous reputation systems one can ensure that the authorship of reviews remains hidden. This prevents, for example, a trader from punishing a customer for a bad review. At the same time, anonymous reputation systems can also ensure that only customers who have been authorised to do so can rate a trader. Furthermore, it is recognisable if a customer has rated a trader twice, for example because the trader has updated his rating.
Other examples from the field of privacy-preserving cryptography are anonymous credential systems and incentive systems.