Quickstart

This guide will introduce you to the ideas of the paper "Transparency Dictionaries with Succinct Proofs of Correct Operation". We will go through the necessary cryptography and provide further links in many places to deepen the knowledge and not to completely interrupt the reading flow on the topic.

What is it all about?

The paper is about Verdict, an untrusted service that manages data - more precisely, a label-value-map - and produces evidence that it has acted correctly and honestly. Correct and honest here refers to a predefined way (called application-specific policies) by which it purports to act. Thus, in the following, we deal in principle with a system that does not need to be trusted because it is provably honest. Incidentally, the proofs save us some computational effort, but we will come to that later. For the moment, however, we note that these are such relevant and beautiful properties that it is worth delving deeper into the subject.

A practical application

Let's first go a bit further into the functions of the service and how they are provided. So that we don't have to deal with an abstract idea in the following, Let's look at a concrete application example of Verdict. In the paper from Tzialla et al. "Keypal" is described as a concrete application example, which I will take up as a basis in the work and change in certain places or add approaches. For this reason, we will refer to the modified implementation described here as Deimos. We can think of Deimos as a service that manages a two-column table. The first column stores unique identifiers, namely e-mail addresses, and the corresponding column on the right also stores a list. In this list, public keys are stored (in a roundabout way, more about this later). To illustrate this, let's go through the whole thing again slowly with a use case.

In cryptography, we often talk about two participants interacting with each other: Participant A and Participant B. Since A and B are somewhat impersonal, we'll call them Alice and Bob. Alice in our case wants to write an email to Bob and would like to encrypt this email. She knows that she can achieve secure encryption using different encryption methods. She chooses hybrid encryption and needs, among other things, a public key B_pubKey from Bob. So she looks in the list of the untrusted service for Bob's E-Mail address and finds one of his public keys in the corresponding column. She encrypts the email with a symmetric key k and encrypts this key again with Bob's public key B_pubKey. Then she sends both the encrypted mail M_k and the encrypted key C_k to Bob, and only because Bob has the private key B_privKey can he decrypt the key to decrypt the mail. This is illustrated again here.

Missing pieces lead to core elements

So far we have mainly looked at the ids (i.e. the email addresses) in Deimos. We have also found that in some way we want to trace the behavior of Deimos in a provably correct way. Users should be able to add and revoke public keys to their Ids. Now, if we think about how to represent this, one can come up with the idea of simply storing a list of non-revoked keys in the right column. However, at second glance, it is not hard to imagine that this would cause us to lose considerable knowledge about, in particular, the revoke operation. All keys that have been revoked will then no longer appear and since our goal is to be able to trace the behavior correctly and provably at any time and for any operation, we need a different solution and not a simple list, but a data structure that incidentally also ensures the order of the operations applied, since this is also important. So in the next chapter we will have a closer look at the data structures of Verdict and Deimos respectively, in order to be able to understand the application better. We will find out that these missing pieces lead us to basic structures of Deimos, on which many further ideas are based.

What's next?

Great, we now have an overview of the basic function of Deimos, a concrete use case of Verdict. The fact that we don't understand any details yet and that everything will only make more sense later, we have to accept for the moment. Here's a quick overview of what we'll look at next:

• Let's understand the data structures
• Ready for the first little proofs?
• Zero knowledge to save time and resources