Nym's Coconut Credentials - An Overview

Broadly speaking, the internet privacy project I work on, Nym currently has two core technologies.

The first is a mixnet that protects transport data and metadata. Mixnets work against even very strong state/corporate level adversaries who may want to deanonymize users by recording all TCP/IP packets as they transit the internet.

The Nym mixnet fulfils the promise of end-to-end network unlinkability – not only can it protect the content of messages, it also hides who is communicating with who, and the routes taken by individual packets.

The second technology is a selective disclosure credential. We have based the Nym credential on Coconut, a design funded by Decode, a project initiated by the European Union’s Horizon 2020 innovation program to “build a trustworthy and privacy-aware digital society”.

“Selective disclosure credential” is quite a mouthful. What does it mean?

Coconut is a signature scheme. All signature schemes consist of three algorithms:

1. keygen
2. verify
3. sign

A user must be able to keygenerate public/private keypairs. They can then sign a piece of cleartext using the private key. Later, anyone with the public key of the signer should be able to verify that the signature is valid. All signature schemes work like this – RSA, DSA, and newer sexier ones like ED25519.

Coconut extends these basic three functions with several more. Understanding the extra functions is the key to understanding what we can do with it. Let’s see what additional algorithms get added.

4. Blind Issuance

David Chaum invented blind signatures in the 1980s. Blind signatures have some extra properties in addition to those above.

There are still the keygen, verify and sign algorithms. There is also an algorithm which allows someone who doesn’t have the secret signing key to blind a message: take a piece of cleartext, and turn it into gobbledygook which can then be signed by a signer who has the secret key.

The signature is passed back to whoever created the message, still blinded. This signature can then be unblinded by that person. It’s now equivalent to a valid signature on the original cleartext message. Once it’s been unblinded, the signer has no way of linking the unblinded message with the signature on the blinded message.

Examples can help in understanding. Let’s take as an example a simple, fictional private e-cash scheme. Here are the steps that I might undertake in using it:

• I create a message saying I have one dollar, in cleartext.
• I blind it using a blind-signature algorithm. The cleartext message turns into gobbledygook.
• I send the blinded message to the bank along with a dollar.
• The bank signs it, saying it attests I have a dollar, and returns the signature to me.
• I unblind the signature, which de-links it from the signature I got back from the bank. This is the crucial step that ensures my privacy.
• I now have an anonymous bearer token which attests I own a dollar.

The bearer token cannot be linked back to what the bank gave me, but its validity can be verified by anyone with the bank’s public key.

This process is blind issuance: create cleartext, blind, send to signer, sign, return to creator, unblind, use. There is a problem with blind issuance: the signer has no clue what they’re signing.

So if you’re the bank, you get some gobbledygook. How does the bank know it doesn’t say “I have one million dollars”? It’s opaque to them. The standard solution is to use a zero-knowledge proof attesting that the message contains a dollar, but revealing nothing else (serial number, my identity, etc).

Coconut has this zero-knowledge proof ability, so it can do blind issuance. The zero-knowledge proof involved needs to be coded for each domain: a zero-knowledge proof for currency would need to differ from one for identity assertions, or one for anonymous voting protocols.

5. Re-randomisable Signatures

There’s another concept relating to signatures: a re-randomization. This type of signature has one additional algorithm: randomize. It allows the user to take a signature, call randomize() on it, and generate a brand new signature that is valid for the same message. The new bitstring in the re-randomized signature is equivalent to the original signature but unlinkable to it.

What can this be used for?

You can show the signatures to different people and the people you show them to cannot figure out that the signatures are linked to each other, or to you. The underlying message in all cases is the same, so there’s no possibility of forgery. Essentially, we have multiple anonymized bearer tokens.

Coconut does re-randomization.

6. Selective Disclosure

Coconut also allows what’s called selective disclosure.

What is selective disclosure?

In a traditional signature scheme you sign the message, and later anyone with the public key may verify it. There’s usually an implicit constraint here: the verifier must have the full message to verify it.

Instead of needing to show the whole message to verify, selective disclosure allows us to show and verify only some parts of the message, keeping other parts of it private.

Another example: let’s say you want to go to the pub, and need to prove your age at the door. You might present your passport, which has the following attributes:

• name
• nationality
• birthplace
• birthdate
• handwriting
• gender
• age
• photo

You go to the pub. The bouncer at the door doesn’t care about anything else, just your appearance and age. But we need to give up all the info to the bouncer, because we show the whole credential every time.

Selective disclosure allows you to improve this process. You sign a tuple of all the fields in the passport and when it comes to verify, the verifier can verify only some attributes. The verifier here is public, and could be anyone who (a) knows the public key of the passport authority, and (b) sees the signature from the passport authority.

So we have three parties:

1. passport authority
2. subject (you)
3. relying party (bouncer)

You can choose to selectively disclose some, or all attributes in the signed message.

Selective disclosure can be applied to “normal” signature schemes (no blinding, no re-randomization). That is, you can get a signed message from an authority and disclose attributes selectively. This provides privacy against the relying party (bouncer) by not revealing more information than necessary. However, if you go again to the same pub, or if the passport authority sees the message (which they signed), those parties can link signature and verification and thus break the subject’s privacy.

Now the really interesting part, from Nym’s perspective: putting it all together.

If we combine blinded credentials, re-randomizable signatures, and selective disclosure, we can protect the user’s privacy against multiple “shows” (uses of the credential) at the pub. The bouncer will think it’s always the first time you’ve been there, and the passport authority has no way of linking the blinded credentials you’re using to what they issued.

The idea that you can selectively disclose by showing some attributes and not others is a simplification, it’s more powerful than that. Instead of revealing your age directly, you can associate a zero-knowledge proof that asserts “I’m over 18” without revealing your actual age.

7. Threshold Issuance

Blind signatures, re-randomisable credentials and selective disclosure have all existed in the cryptography literature for years, or even decades. As we’ve seen, stringing them together has some interesting properties, but until now, all of these schemes had one thing in common: signing was always centralized.

The major advance in Coconut is threshold issuance. Instead of having one authority doing the signing, Coconut has multiple authorities that sign (either all together, or as a threshold n out of m signature). This makes it possible to issue Coconut-based signatures in a decentralized context, and gain all of the privacy goodness that was previously only available in centralised systems.

In conclusion

To recap, the Nym validators issue signatures based on a scheme called Coconut. All signature schemes have three algorithms:

1. keygen
2. verify
3. sign

Coconut has these, but adds:

4. blind issuance
5. re-randomisable signatures
6. selective disclosure
7. threshold issuance of signatures

These extra functions give very strong privacy guarantees for users of the scheme. Initially, we are planning to use Coconut within Nym for anonymising access credentials and payments to service providers.

Looking forward a bit more, Coconut can also be used to add on-chain transaction privacy to existing blockchain systems (Bitcoin, Ethereum, Libra, Cosmos, Parity, etc). In combination with the Nym mixnet, we can then offer quite sophisticated privacy guarantees even against strong attackers.