Threshold Key Derivation - Privacy on the IC

TL;DR We want to add privacy to the IC by enabling canisters to perform threshold key derivation

Summary

Empower dapps to perform encryption, threshold decryption, and signing on the IC by allowing canisters to call a threshold key derivation interface. This feature will enable canisters or individual users to encrypt messages under the public key of the subnet, so that they can be decrypted by calling the threshold key derivation interface for the corresponding decryption key that is secret-shared among the replicas. Integrating this feature will enable canisters to store end-to-end encrypted user data (e.g., storage, messaging, social networks) without having to rely on browser storage for user-side secrets, as well as enabling transaction privacy within canisters (e.g., closed-bid auctions, front-running prevention).

Status

Discussing

Key People Involved

@gregory, @andrea, @ais, @franzstefan, & @victorshoup

Timelines

  • 1-pager on the Forum (to follow shortly after we see your first comments/requirements)
  • 1st Community Conversation (Concept, context, and use cases, community questions. Confirmed for Nov 29th - Register here!)
  • 2nd Community Conversation (Presentation of proposed design)
  • NNS Motion Proposal (to approve design + project)
  • If the NNS Motion Proposal passes, implementation and deployment would take a few months

Description

The promise of blockchain technologies is to remove a central point of trust allowing anyone to read, write, and verify data on the system. This is often achieved by making operations and data stored on blockchains publicly visible. While this transparency can be useful to build the trust needed in a decentralized system, it can also be prohibitive. This includes using blockchains for public, but also for private and business reasons. Removing a central point of trust should not mean that everyone should sacrifice confidentiality of their data.

Given the existence of public-key encryption, it’s easy to encrypt data and send it or store it on a blockchain, but problems arise when we want to decrypt, especially in the distributed setting. Storing the decryption key on a user’s device is secure and useful in the traditional E2EE case, but if we want to share decryption capabilities, while still maintaining privacy (no single node knows the key), a flexible approach is to require the participation of some threshold of parties. In this proposal we aim to build such a threshold (decryption) key derivation scheme.

High level objective

  • Make a threshold key derivation Interface
  • Canisters can obtain encrypted threshold signatures
  • Allow symmetric encryption and public key / identity-based encryption

Proposal description: Motivated by E2EE and front running use cases, we aim to build a flexible and scalable solution to achieve user privacy by means of a new cryptographic building block called verifiably encrypted threshold key derivation (vetKD). In brief, vetKD can be seen as the key derivation of an (identity-based) encryption scheme where the master secret is secret-shared among a set of servers that can assist users in deriving keys by sending encrypted shares of those keys to the users. The shares are encrypted under a public key provided by the user, so that the servers do not learn the derived key, but can verify that a ciphertext indeed contains a valid key share. Users are therefore guaranteed to recover the correct key if they receive sufficiently many encrypted shares.

A first sketch for an Interface that you can call on the mgmt canister would like something like:
derive_encrypted_key(master_key_id, transport_public_key, identity) -> EncryptedKey

Potential applications include:

  • End to end encryption
  • Secret bid auctions and MEV protection
  • Time-lock encryption
  • Dead man’s switch
  • …

Next steps

The first step is to get feedback from the community. We’re particularly interested to hear what are the issues you have faced wrt privacy or confidentiality. Is there something you couldn’t build because you didn’t have this feature, or do you have specific examples of where it could be useful?

We then plan to outline a design and present it in a community conversation, after which we’re happy to take comments and to adapt. Beyond this, we plan to open the more general privacy conversation by hosting twitter spaces and growing a community in the privacy portal.

Then we’ll issue a motion proposal, which, if accepted, will spark development.

42 Likes

This is an amazing feature and we need it. Looking forward to the discussion.

12 Likes

Do you mind elaborating on who will be using the derived decryption keys? Do the canisters use the key to decrypt user data before returning it to the user (as part of a query method)?

I’m also confused whether the “master key” is user-provided or equivalent to the subnet public key. Sorry id these are silly questions.

Great questions, @jzxchiang !

As for who will be using the derived decryption keys: it could be either the canister, or the user himself. In the latter case, the shares of the decryption key will be sent to the user, encrypted under a “transport key” that the user provided. This way, neither the canister, nor any of the replicas learns the decryption key.

Wrt the master key: yes, you can think of it as the subnet public key. It is generated in a decentralized manner by the nodes in the subnet so that the master secret key is never reconstructed on any machine.

3 Likes

This is definitely what I need!

The current implementation has to store the key on the client side and this creates an UX/UI problem. A user can easily lose access to data if he does not have a key synchronized on another device.

As I understand it, the canister can have the ability to work with encrypted data. The canister, like the user, can be the recipient of the decryption key. That is, the canister can process encrypted data and create new ones based on them. For example, I’m interested in generating previews for encrypted images. Now this needs to be done on the client and sent in encrypted form to the canister.

P.S. I am glad that this topic is being raised and efforts are being made to implement it, this will make a qualitative step in building applications!

5 Likes

Sounds like a good use case of Shamir’s secret sharing… to actually handle the key sharing.

This is required for storing any business data. Also I think it would be required for storing any personal information in many regions… Really there are infinite uses :wink:

2 Likes

Does this cryptographic scheme allow arithmetic operations of data while encrypted?

This is great news! Please see if the following scenario is what will be enabled by this feature:

  1. User generates a fresh pub/sec key pair Pk and Sk for encryption.
  2. User sends pub key Pk to a canister.
  3. The canister is able to reply to the user a message M encrypted using Pk.
  4. User decrypts M with Sk and get the secret S.
  5. Secret S is not known to anyone except the user.

If this is indeed possible, it begs the obvious question: how does the user first generate S and send it to a canister to keep?

3 Likes

Not by itself, no.

But you could use vetKD to “bootstrap” into a (fully or partially) homomorphic encryption scheme by IBE-encrypting the decryption key of the homomorphic scheme. This way, the canister could perform operations on the homomorphically encrypted data and use the vetKD interface to manage who gets to see the result.

6 Likes

Thank you for the response. I have a couple follow-up questions. Apologies if these are quite basic, as I am no cryptography expert.

  1. I know that a subnet’s public key is primarily used to verify signatures created from that subnet’s private key (whose shares are distributed across its nodes). I didn’t know that a subnet’s public key could also be used for encryption. Could you verify that subnet public keys on the IC can indeed be used for asymmetric encryption and not only for digital signatures?

  2. If that is true, what is the purpose of key derivation here? Typically, key derivation is used to generate ephemeral keys for short-lived sessions, I think. But in this case, it seems to be used as a cheap method to generate per-user keys on demand without going through the expensive process of key establishment each time. Is that accurate?

  3. Can users use a master key that is not the subnet public key? If Alice and Bob both use the subnet public key to encrypt their data, and then derive their own secret keys Key-Alice and Key-Bob from it, how does the scheme ensure that the holder of Key-Bob (i.e. Bob) can’t decrypt Alice’s data (since they both used the same public key to encrypt their data)? I think I’m misunderstanding something basic here.

  4. The transport key seems to be somewhat orthogonal to the derived decryption key. In other words, it belongs to a completely separate key pair and isn’t technically a part of the “core feature”, although it helps a lot in providing confidentiality. Is that accurate?

Thank you so much!

2 Likes

Hi @spnrapp,

I’m afraid you lost me at step 4 in your scenario. What is the relation between M and S? Is S included in M? Who chooses M, who chooses S?

Note that there’s not much point in the canister encrypting a secret to a user, because all replicas running that canister will know the secret.

1 Like
  1. I know that a subnet’s public key is primarily used to verify signatures created from that subnet’s private key (whose shares are distributed across its nodes). I didn’t know that a subnet’s public key could also be used for encryption. Could you verify that subnet public keys on the IC can indeed be used for asymmetric encryption and not only for digital signatures?

You’re raising another very good point. We’re planning to support vetKD for the Boneh-Franklin IBE, for which the decryption keys are actually BLS signatures. Algebraically speaking, that means that we could actually re-use the same BLS keys that we already use for subnet signing. However, it would not be good “cryptographic hygiene” to do so, so we’d rather opt for having a separate set of threshold BLS keys for vetKD purposes.

  1. If that is true, what is the purpose of key derivation here? Typically, key derivation is used to generate ephemeral keys for short-lived sessions, I think. But in this case, it seems to be used as a cheap method to generate per-user keys on demand without going through the expensive process of key establishment each time. Is that accurate?

Kind of, yes. The derived decryption keys indeed do not need to be short-lived. For example, in a secure storage use case, you could set the long-term encryption key to be the vetKD decryption key derived from a user’s principal.

  1. Can users use a master key that is not the subnet public key? If Alice and Bob both use the subnet public key to encrypt their data, and then derive their own secret keys Key-Alice and Key-Bob from it, how does the scheme ensure that the holder of Key-Bob (i.e. Bob) can’t decrypt Alice’s data (since they both used the same public key to encrypt their data)? I think I’m misunderstanding something basic here.

Indeed, that’s not obvious: this feature would threshold-derive decryption keys for an identity-based encryption (IBE) scheme. Such a scheme allows anyone to encrypt to a master public key and an identity, so that only the holder of the decryption key of that identity (that is derived from the master secret key and the identity) can decrypt.

The transport key seems to be somewhat orthogonal to the derived decryption key. In other words, it belongs to a completely separate key pair and isn’t technically a part of the “core feature”, although it helps a lot in providing confidentiality. Is that accurate?

As a mental model, that’s exactly right. But… :slight_smile: Without wanting to get too much into the nitty-gritty details of the vetKD scheme, but it can make sense to use a particular transport encryption scheme that has some sort of “homomorphism” that enables replicas to (1) check that an encrypted key share indeed contains a valid key share, or (2) to aggregate sufficiently many encrypted key shares into a compact encrypted key. But these are optimizations, really, the basic principle can work without such homomorphism.

6 Likes

I have a project were I need to store some secrets (symmetric AES-128 encryption keys) to state, separate from any 1 particular user. The issue is that a malicious node provider may be able to read the state. Would this feature essentially solve that issue?

For reference, this is my project:
https://twitter.com/ntagled

I have some workaround solutions planned, but confidential canister state and end-to-end encryption would be the ideal solution!

1 Like

I’m assuming that, in your use case, a first user generates a random AES key that a second, unrelated user should be able to read? Yes, this feature would solve that.

The easiest way is simply to let the AES key be the threshold-derived decryption key for some identifier of the object that the AES key encrypts. The canister then decides which users it grants access to the same derived key; none of the nodes ever get to see the decryption key, only the allowed users do.

If for some reason it’s important in your use case that the first user chooses the AES key himself, you can have him IBE-encrypt that key under some identifier and store the ciphertext in the canister. The canister can then decide which users get access to the corresponding IBE decryption key, and hence the AES key. Again, nodes don’t get to see the IBE decryption key or the AES key.

2 Likes

Hi Greg,

If we look at this type

The EncryptedKey would be M, and actual Key (the secret) would be S.

I want to ask if Key is fixed per (master_key_id, identity) pair? If it is, then a user can’t really choose the secret, and once the secret is leaked, it is no longer secure and a new identity must be used. Is this understanding correct?

1 Like

I want only the canister to be able to access the key, not any particular user.

I’m making transferrable HW wallets. There are two secrets:

  1. A randomly generated AES key associated with each NFC tag, which is held by the canister to authenticate messages from these tags (they generate a unique URL with each scan). It’s important that this key is never externally shared to any party. The principal owning the tag will change, and no previous owner should retain any rights to the asset whatsoever, so this key cannot be associated to any particular user. The NFC tags are also very simple, they cannot sign any ECDSA messages.
  2. A randomly generated 16 byte “Transfer Code” which is externally given only to the current owner of the tag. This is physically written to the tag when the owner decides to (unlock) the tag. Then the next person to scan the tag will immediately become the new owner, as long as the tag credentials and transfer code are valid. If the scan credentials are valid but the transfer code is not, then they only get “read only” access and cannot claim ownership of the tag.

As mentioned before, neither of these secrets can be stored in the state in their raw form, otherwise a node provider would be able to remotely claim ownership of a tag. The entire point of the project is to make sure that the only way to claim ownership of the tag is if you have it in your hand in person.

1 Like

This rabbit hole goes deeper than I thought (as usual). Thanks for the explanation!

1 Like

Can an unintended person take ownership of a tag that is in transit being mailed to someone who has bought it? by scanning it

If the tag is unlocked, the next person to scan it can take over ownership (after they log into the dapp with their IC wallet).

However, to scan it your device needs to be within 10 cm (basically touching it), so they wouldn’t be able to scan it through a shipping box while in transit. If you wanted to ship it in a thin envelope, you could simply wrap it in a small piece of aluminum foil to block any possible passive scanning attempts.

In this sense, it’s basically the same as shipping cash. You’d be able to ship it discreetly, but at the end of the day if someone steals the package and opens it there’s only so much you can do. Frankly, in this case most people would have no idea that the tag held crypto, or that it could even be scanned with their phone, or that they’d need an IC wallet to claim it, so it would actually be a lot more secure than shipping cash.

Also, the tag can only be unlocked in person, not even the owner could unlock it remotely, so it needs to be shipped unlocked.

When I ship tags to customers, it’ll be in discreet envelopes and I’ll make sure any passive scan attempts would be blocked.

That’s right, the key is fixed per (master_key_id, identity) pair, and if it were to get leaked, one would have to switch to a different identity.

I’m not sure how that’s a drawback, though. If you want to store a user-chosen secret, then just encrypt that secret with the derived key and store that ciphertext within the canister. To recover the secret, you re-derive the decryption key and decrypt the secret from the stored ciphertext.

Also, if a user-chosen secret leaks, you would also have to switch to a different secret, so I’m not sure how that’s any different either?

1 Like