Associated metadata for capsules

[fjarri]

The following scheme can be used to associate reencryption conditions (or other metadata) with capsules:

Capsule contains public points $P_r = s_r * G$ and $P_u = s_u * G$ where $s_r$ and $s_u$ are secret (and ephemeral) scalars, and $G$ is the generator. At the moment of capsule creation Enrico can associate some metadata $M$ with it as follows:

• calculate a hash $h = H(M)$ of the metadata;
• generate a secret ephemeral scalar $x$;
• calculate $P_x = x * G$ and $P_h = (x + h (s_r + s_u)) * G$;
• publish $(M, P_x, P_h)$.

Now anyone having that proof and the capsule can verify that the proof was indeed created by the creator of the capsule by checking that $P_x + h * (P_r + P_u) = P_h$. This is essentially the same approach that was used to attach metadata to capsule frags.

Note that this only establishes a one-way correspondence. Given a capsule one cannot know if any proofs were created for it; and Enrico can create several proofs for different metadata which all would pass the verification. Although this may not be important for the goal of attaching reencryption conditions.

[cygnusv]

Hey @fjarri, this is a very cool idea :) This is basically a Schnorr signature of the metadata by Enrico.
I need to think more about it, but it doesn't seem that there's any cryptographic problem with this. My only comment is that I was thinking on using an approach that didn't rey on asymmetric crypto, e.g., using HMACs, which can be much faster, although to be honest, I don't know how noticeable would be the difference.

[cygnusv]

I've been thinking a bit about this, and although I don't see anything incorrect in your original approach, I think we can achieve the same thing following a more common construction, while keeping the spirit of your idea. In Umbral, we do something similar to create a validity check for capsules, that actually it's a mere Schnorr signature (but using the ephemeral private key labeled as $s_r$ by @fjarri). This new idea is as follows (I'm changing the notation to the one used in Umbral docs here just for clarity https://github.com/nucypher/umbral-doc/blob/master/umbral-doc.pdf)

Capsule contains public points $E = r * G$ and $U = u * G$ where $r$ and $u$ are secret (and ephemeral) scalars, and $G$ is the generator. At the moment of capsule creation Enrico can associate some metadata $M$ with it as follows:

Umbral part (for backwards-compatibility):

• Calculate $E = rG$ ( $r$ is acting as ephemeral signing key, and $E$ as ephemeral public key)
• Calculate $V = uG$ ($u$ will effectively act as a nonce, while $V$ is a nonce commitment)
• $K = KDF((r+u)PK_A)$
• Calculate signature $s = u + r\cdot H(E,V)$
• Umbral capsule is $(E, V, s)$
• Capsule can be validated by checking whether $sG = V + H(E,V)\cdot E$

Additional steps:

• Generate additional secret ephemeral scalar $x$ (this will effectively act as another nonce)
• Calculate $X = xG$ (this is a commitment to the nonce)
• Calculate signature with metadata: $z = x + r\cdot H(E,V,s,M,X)$
• New capsule is $(E, V, s, M, X, z)$
• New capsule can be validated by checking with previous procedure and also whether $zG = X + H(E,V,s,M,X)\cdot E$

I think we can even perform the two checks at once to validate capsules with metadata more efficiently:
$(s+z)\cdot G = X + V + [H(E,V) + H(E,V,s,M,X)]\cdot E$

[jMyles]

...but what advantage are we gaining by using a Schnorr sig over a digest (HMAC-ish)? Just that Enrico can optionally reuse the private key as a branding mechanism?

[cygnusv]

...but what advantage are we gaining by using a Schnorr sig over a digest (HMAC-ish)? Just that Enrico can optionally reuse the private key as a branding mechanism?

The problem with HMACs is that they are keyed with a secret key, and we want Ursulas (at the very least, but ideally, anyone) to be able to verify that a ciphertext is associated to a given metadata. How do we communicate such key to Ursulas (with the proper authentication & integrity assurance)? HMACs are fine for an end-to-end setting, but it's not clear to me how to extend them to work for an intermediate party that's not going to decrypt the ciphertext.

[cygnusv]

...but what advantage are we gaining by using a Schnorr sig

Umbral is already using a Schnorr signature internally, so reusing the same cryptographic material to also associated metadata makes sense, while allowing certain backwards-compatibility.