Cryptographically proving timed validity without showing an expiry date

However, occasionally there are problems for which existing cryptography simply doesn't suffice. In such situations, making new crypto code can be the only option. And though difficult, it can also be a satisfying challenge.

Recently David Venhoek, one of the developers at Tweede Golf, together with Sietse Ringers, IRMA architect & lead developer at SIDN, got the opportunity to work on just such a problem. The Dutch Ministry of Health (VWS) asked for an investigation of some fairly novel crypto as an option for use in the Dutch Corona test app, called "CoronaCheck".

The app is under active open-source development and will soon be extended to prove vaccination in addition to proving a recent Corona test, providing a Corona Passport.

The problem

The goal of the CoronaCheck app is to provide confidence that the person in front of you has been tested recently. At the same time, the Ministry of Health wants to adhere to the principles of privacy by design, i.e. this process should reveal a minimum of other information, so as to minimize possibilities for tracking people through these checks.

Dutch Ministry of Health statement on privacy of the app

The main problem here is to verify that a Corona test was done recently enough. This could be done by simply revealing the actual moment a test was done, but that has a major flaw. Since Corona tests have a very short period for which they are valid (a few days), the indicated time of testing would need to be reasonably precise, significantly reducing the number of other people having the same testing time.

To avoid tracking through the testing time, ideally we would like to validate that the moment of testing was recent enough without actually disclosing that time. The goal of this project was to implement cryptography that would make this possible.

Investigating solutions

Early on in the project, we identified two potential approaches to proving time validity of a test result:

1. Prove that the time difference between the expiration date of the test and the current time is non-negative by proving we know a way to write this (signed) difference (in seconds) as a sum of squares, without revealing the actual numbers involved.
2. Have a predefined set of signatures over all possible valid time differences between the expiration date of the test and the current time, then proving that we have a signature for the actual time difference, without revealing that difference or which signature we used.

Approach 1 had the advantage that it was defined in the standard for idemix, the underlying cryptography system we were working in. It also provided more flexibility, allowing easier generalization of the proof technique to more general statements of one quantity being larger or smaller than another. However, for the CoronaCheck app, keeping the size of the produced proofs small was crucial for usability, because these are to be transmitted through QR codes. As presented in the literature, these proofs would have pushed the boundaries of what was usable.

Approach 2, in contrast, had the potential to result in significantly smaller proofs. However, this approach was far less studied in the literature. This meant that it was unclear at the start whether it was completely feasible, and furthermore would have required significant further study.

Through some additional design work, we realised that by using 3 instead of 4 squares, and combining some parts of the proof in approach 1, its proof size could be significantly reduced. Although still producing larger proofs than the second approach, the difference was now small relative to the total size. Therefore, in discussions with the Ministry of Health, we decided to proceed with approach 1.

Implementation

Before starting to write actual code, it was necessary to prove mathematically that the modifications made to Approach 1 did not actually impact its security. For this, we wrote a reduction proof, showing that if someone can fake our proofs, they can also solve a mathematics problem that is generally considered infeasible to solve (in our case, the so-called "Strong RSA problem"). This turned out to be relatively straightforward, as it could be based in large part on previous results published on idemix.

Once we were satisfied with the validity of the approach, the actual implementation effort for these proofs was started. The CoronaCheck app makes use of the Idemix cryptography library "gabi" developed by the Privacy by Design Foundation for identity platform IRMA, and our new code was added to this library. It took about 1.5 days to get an initial working implementation, and a further 3 days of work to test the resulting code, provide proper integration with the rest of the IRMA cryptography and provide sample material on how to use the proof code.

The final step in the process was an in-depth review of the produced code. This was successfully completed with no major changes to the core crypto code, and the resulting implementation has been successfully merged.

Conclusion

With the cryptography in place, these improvements are ready to be added to the app. At the time of writing, integration into the CoronaCheck app is still being evaluated. We'll update this article when it ships.

For us, it was a great challenge technically to work on this project and at the same time very satisfying to contribute to privacy improvements of the CoronaCheck app.

Images by coronacheck.nl and Dutch Ministry of Health