Foundational Cryptography, IBM Research Zurich

Background

Over the last few years, the Foundational Cryptography group at IBM Research in Zurich has become the leading industrial research cryptography center of competency worldwide, both within IBM as well as in the cryptography research community.

IBM Research has an extensive history in cryptography research. In the late 1960s, IBM Chairman Thomas J. Watson Jr. set up a cryptography research group in IBM Research, headed by cryptographer Horst Feistel. The group created an encryption method, named “Lucifer,” to protect the data for a cash-dispensing system that IBM had developed for Lloyds Bank in the United Kingdom. This encryption method evolved to become the first-ever Data Encryption Standard (DES).

This was the start of a long history of pioneering contributions to the cryptographic design of many familiar standards helping secure modern communications and interactions. The success and impact would not have been possible without the significant theoretical work conducted by cryptography researchers working across IBM. It resulted in major achievements in the mathematical foundations of cryptography and led to some of the greatest innovations in the area, including:

pioneering work in quantum-safe cryptography,
seminal contributions to cryptanalysis,
the development of lattice-based cryptosystems,
the advancement of distributed cryptography and proactive security, and
the breakthrough invention of fully homomorphic encryption.

Most recently, the focus of our group in Zurich has expanded to include password related protocols, Key Encapsulation and Combiners, Functional Encryption, and Zero Knowledge Proofs.

News

Video from Crypto 2022

Lattice-Based Zero-Knowledge Proofs and Applications: Shorter, Simpler, and More General

Fields of Research

Number Theoretic Cryptography: Elliptic Curves, Isogenies and More

Since the beginnings of public key cryptography, number theory has been at the forefront of it. The Factorization (RSA) and Discrete logarithm (Diffie–Hellman, ECDH) problems are still the two pillars that support all our secure communication infrastructure today. The next generation of quantum-safe protocols also leans heavily on number theory: ideal lattices (NTRU, Crystals, ...) and isogenies of elliptic curves (SIKE) are among the finalists of NIST’s standardization process.
At IBM we work on all aspects of number theoretic cryptography, from the development of new schemes, to cryptanalysis, and to the security of real-world implementations.

Time and Space Efficient Proof Systems

Imagine that a client with few resources wants to outsource an expensive computer simulation to a powerful, but untrusted cloud server. The client cannot run the simulation for themselves, so how can they check whether the results are correct?

Zero-knowledge proof (ZKP) systems solve this problem. Using a ZKP, the server can provide a proof that they ran the simulation correctly. Years of dedicated research on ZKPs mean that clients can check proofs at a tiny fraction of the cost of the simulation. However, the cost of producing proofs remains high, leading to a large gap between what can be outsourced, and what can be verifiably outsourced.

ZKPs based on hash-functions offer the best solution to this problem. They are transparent, quantum-safe, and have the lowest computational overhead of all known ZKPs. By improving hash-based ZKPs, we will eliminate the verification gap and enable truly large-scale outsourced computing applications.

Functional Encryption

Cryptography has found multiples applications that go well beyond traditional encryption. One prominent line of work introduced encryption schemes with advanced functionalities, such as the capability to compute a selective function on the encrypted data or enforce fine-grained access control. Much like homomorphic encryption, but featuring different and complementary properties, such encryption schemes fall under the umbrella notion of Functional Encryption.

We contribute to building Functional Encryption from the ground up, starting with simple and practical functionalities, such as private aggregation (i.e. computing a weighted sum on the encrypted plaintexts), and exploring more sophisticated computations that could serve to perform privacy-preserving machine learning. A particular emphasis is given to decentralized schemes, where the required trust is minimal, and users can join the system dynamically.

Lattice-Based Zero-Knowledge Proof Systems and Privacy

Zero-knowledge proofs are the core building block for most of privacy-centered cryptography. There is currently a large performance gap between non-quantum-safe (pairing-based) zero-knowledge proof systems and quantum-safe hash-based ones. One promising avenue for shrinking this gap is via the introduction of computational hardness assumptions such as lattice assumptions. In the area of basic signature schemes, lattice-based signatures are now significantly more efficient than hash-based signatures, both in terms of bandwidth requirements and computational performance. Therefore, it is likely that the same can eventually also be achieved for more advanced algorithms such as zero-knowledge proof systems used in privacy-based protocols and even for proving general circuits.

Our group is at the forefront of research in this area and we have achieved a steady stream of progress in terms of proof size over the last years. The proof systems we have developed can be used in the construction of privacy-preserving cryptography and lead to very practical schemes that are the best quantum-safe alternatives known to date.

Digital Identity Management

In the connected world we live in we maintain an increasing number of digital identities. To claim such identities, we type in passwords, slide our fingers over sensors, or use the secure storage of our personal devices to authenticate. But often, cryptographic authentication protocols rely on a single point of trust – such as an identity provider who checks our password, or a phone’s TEE that compares biometric templates or handles secret key material. Compromise of this single point of failure results in identity theft, the risk of impersonation, and leakage of biometric data that uniquely identifies its source.

We research advanced protocols for personal identification and authentication that do not rely on a single point of failure. For example, we develop password authentication protocols that leak no information about the password a user types except for “correct”/”wrong”. We deploy threshold cryptography to distribute the role of a single identity provider, to reduce the risk of impersonation and loss of personal data. Finally, we develop the next generation of biometric authentication protocols that minimize leakage of users’ biometric data towards identity providers.

Cryptographic Protocols

A cryptographic protocol constructs application-level services from underlying cryptographic primitives. Challenges connected to protocol design include the identification and appropriate modeling of the many possible requirements of application types (e.g. communication channels, online voting, …), the identification and appropriate modeling of the properties offered by the available primitives (e.g. one-way functions, public key encryption, zero-knowledge proofs, …), and the exploration of sound ways of leveraging the one to achieve the other. Key aspects here are clean abstractions of functionality and security, and reductionist security proofs for solution candidates.

The novel primitives that we develop at IBM Research unfold their full potential only when used in matching protocols that translate their functionality and security profiles to properties required by real-world applications. Our group hence has a focus on providing precisely this.

Project Highlights

European Research Council (ERC) Consolidator Grant

PLAZA: Post-Quantum Lattice-Based Zero-Knowledge (2021 – 2026)

The digital world is experiencing a major shift in the direction of more privacy and decentralization. The currently most efficient privacy-granting cryptographic schemes, however, are not quantum-safe.
The goal of the PLAZA project is to extend the efficient lattice-based techniques that were used to create the new quantum-safe NIST standards to create practical zero-knowledge proofs and privacy-based protocols. It is our hope to have all the necessary pieces in place before the decentralized, privacy-based ecosystem receives widespread adoption.

Principal investigator:
Vadim Lyubashevsky

Swiss National Science Fund (SNSF), AMBIZIONE

Your Biometrics, Please! Cryptographic Protocols for Human Authentication and the IoT

Developing methods for biometric authentication that severely limit the exposure and the risk of leakage of biometric data to external providers.

Principal investigator:
Julia Hesse