Is there a scheme to enforce a random seed without leaking the seed?

Using Ed25519:

The group size $\ell$ generated by the base point $G$ on the curve is approximately $2^{252}$. As an abbreviation, references below to "252-bit" numbers refer to scalars less than $\ell$.

The client has 128-bit entropy $e$, and picks a uniformly random 252-bit scalar $b$.

The client uses $b$ as a blinding factor to derive the Pedersen commitment $C=eG+bH$. $H$ is a second well-known base point on the curve, picked using a 'nothing-up-my-sleeve' technique such that the discrete log of $H$ w.r.t. $G$ is unknowable.

The client sends $C$ to the server, and the server picks random 128-bit entropy $e'$. The server sends $e'$ to the client.

The client calculates the 128-bit seed $s=(e+e')\ mod\ 2^{128}$. As long as either $e$ or $e'$ is uniformly randomly distributed, $s$ will be uniformly randomly distributed.

The client calculates the commitment: $C'=C+e'G$. Depending on the values of $e$ and $e'$, and thus depending on whether the $mod\ 2^{128}$ operation caused $2^{128}$ to be subtracted from $e+e'$, either $C'$ or $C'-2^{128}G$ will be a commitment to the value $s$.

The server also calculates the same value $C'$ for itself.

If $2^{128}$ was not subtracted during the $mod\ 2^{128}$ operation, this will mean that $C'=C+e'G==eG+bH+e'G==(e+e')G+bH==sG+bH$.

Otherwise, $C'-2^{128}G$ will be a commitment to the value $s$.

At this point, the server could allow both $H_{128}(C')$ and $H_{128}(C'-2^{128}G)$ as the identifier, where $H_{128}(\texttt{input})$ means to hash the input (using a cryptographically secure hash such as SHA512) and return the first 128 bits of the result.

However, that would require the client to remember not only $s$, but also the blinding factor $b$.

To solve this problem, the client now calculates the commitment $C''=sG+H_{252}(s)H$.

$H_{252}(\texttt{input})$ means to hash the input using a cryptographically secure hash and return a 252-bit scalar as the output.

The client creates a proof that $C''$ is a commitment to the same value $s$ as either $C'$ or $C'-2^{128}G$. This proof will allow the server to accept $H_{128}(C'')$ as an identifier because it knows it is based on the same value as $C'$, which itself is based on the server's entropy $e'$.

If we do not care about disclosing whether the $mod\ 2^{128}$ operation caused $2^{128}$ to be subtracted from $e+e'$, we could just inform the server about whether the subtraction occurred or not. Then, the client would provide a signature $\sigma$ (such as a simple Schnorr signature) proving knowledge of the private key $(H_{252}(s)-b)\ mod\ \ell$ for either the public key $C''-C'$ or the public key $C''-C'-2^{128}G$ on the base point $H$.

The reason this signature proves that the commitments are to the same value is that unless $C''-C'$ or $C''-C'-2^{128}G$ causes the values on $G$ to cancel each other out, the discrete log w.r.t $H$ is unknowable.

We can avoid disclosing whether the $mod\ 2^{128}$ operation caused $2^{128}$ to be subtracted from $e+e'$, by using a ring signature. We would prove that we know the private key on the base point $H$ for either $C''-C'$ or $C''-C'-2^{128}G$, but the ring signature will not disclose which.

The client sends $C''$ and the signature or ring signature to the server.

The server verifies the signature, and then records in its database that the identifier $H_{128}(C'')$ will be allowed.

The client now only needs to remember the seed $s$, which will be the hash part of the URL used to access the encrypted resource. The client will reconstruct the identifier $H_{128}(sG+H_{252}(s)H)$, and will encrypt data using a symmetric key derived from $s$ (using a derivation technique such as HKDF-extract).

Solved by user43864 (3,677 )
Jul 18, 2022 at 02:18