Cryptographic protection necessarily induces an overhead in the form of increased computational costs and larger messages sizes. While for many simple cryptographic tasks such as encryption and signatures, basic tricks like hybrid encryption or hashing can be used to reduce the communication costs, the situation is very different for more complex tasks such as multiparty computation.
Secure Computation on large Datasets with low Communication. The overhead of multiparty computation protocols typically scales with the size of a boolean circuit representing the computation. In the worst case, this can result in secure protocols being exponentially slower than their insecure counterpart. While this is acceptable for small and simple programs, it becomes problematic on large datasets such as genomic data. We investigate techniques that allow for secure computation on large datasets with small communication complexity and workloads of similar magnitude as the baseline insecure protocols.
Signing documents anonymously. Ring signatures are a special type of cryptographic signature scheme which allow a signer to sign a document on behalf of a large group of potential signers without revealing his identity. This primitive can, for instance, be used to enable electronic elections while protecting the anonymity of voters. Current constructions of this primitive suffer from several drawbacks. Either the size of signatures grows with the size of the group in which the signer hides, which is very undesirable if the group is very large, or some additional trust is needed. We investigate novel techniques which suffer from none of the these drawbacks.
Reducing communication costs to the bare minimum. The communication cost of securely computing a function in a distributed setting is typically bigger by a large factor compared to computing such a function insecurely. We are working towards reducing the communication cost of cryptographic protection from a multiplicative factor down to a small additive term.