0
$\begingroup$

I am not sure whether crypto.SE is the right place for this question, but I assume this is closest to on-topic here.

I am doing personal research on cryptography using elliptic curves. I can see that many projects starting to utilize deterministic key derivation (my terminology may be off here, see below what I mean by it).

What I am wondering is whether knowing how derivation process is done, is it possible to verify signature made my root private key using child public key?

Assuming:

random -> root keypair (rootPriv, rootPub) -> KDF(rootPriv) = childPriv, KDF(rootPub) = childPub

Then assuming two parties Alice and Bob:

  • Alice holds rootPriv/rootPub and childPriv/childPub.
  • Bob holds only childPub.
  • Alice wants to send message to Bob and ensure Bob receives it untampered. Alice then signs message using rootPriv and sends to Bob message and signature.

How can Bob (if it all possible) verify the signature knowing KDF and childPub without knowing rootPriv/rootPub/childPriv?

If that is possible for EC, does such requirement pose any restrictions on which curve can be used or on KDF? E.g. can any curve be used (Ed25519 or any other?) and would KDF need to be reversible in nature or any other restriction?

PS: This is about EC strictly though

$\endgroup$
0
$\begingroup$

I think you're asking about what are called hierarchical signature schemes or blinded signature schemes. There's a root private key $a$ and public key $A$, and for any tweak $t$, there is a derived private key $a_t = f(a, t)$, and a derived public key $A_t = F(A, t)$, such that signatures made with $a_t$ can be verified by $A_t$, but the set $\{A_t\}_t$ is supposed to be indistinguishable from $\{A'_t\}_t$ for any other $A'$ to anyone who doesn't know $A$. See an earlier answer for some references.

I think you're further asking about whether there is an easy way to compute $A$ given $A_t$ and $t$, although you didn't mention $t$ so maybe there is only one possible derived key pair. Whether you can do this depends on the specific signature scheme, so let's pick one for illustration:

Signatures. $\newcommand{\Z}{\mathbb Z}\newcommand{\concat}{\mathop{\Vert}}$Let $k$ be the field $\Z/(2^{255} - 19)\Z$, and let $E/k$ be the twisted Edwards curve $$E/k\colon -x^2 + y^2 = 1 - (121665/121666) x^2 y^2,$$ whose group $E(k)$ of $k$-rational points has order $h\ell$ for large prime $\ell$ and cofactor $h = 8$. A public key is a point $A \in E(k)$, and a signature on a message $m$ is an encoded pair $(R, s)$ of $R \in E(k)$ and a 253-bit integer $s$ satisfying the verification equation $$[h s] B = [h] R + [h H(R\concat A\concat m)]\,A,$$ where $B$ is the standard base point and $H$ is the standard hash function mapping long messages to 512-bit integers.

A signer chooses a secret 256-bit scalar $a$ (usually with $a \equiv 0 \pmod h$ and $2^{254} < a < 2^{255}$ so that it is compatible with X25519 secrets, but this is irrelevant to signature security) and a secret 256-bit string $\kappa$ as their private key, and publishes $A = [a]B$ as their public key. To sign message $m$, they compute $r = H(\kappa\concat m)$, $R = [r]B$, and $$s \equiv r + H(R\concat A\concat m)\,a \pmod \ell.$$

Hierarchical signatures. So far this is just standard Ed25519. For a tweak $t$, we can let \begin{align*} a_t &\equiv a H(A\concat t) \pmod \ell, \\ A_t &= [H(A\concat t)] A. \end{align*} Note that $$A_t = [H(A\concat t)]([a]B) = [a H(A\concat t)]B = [a_t]B,$$ so that $A_t$ is the ordinary Ed25519 public key for the private key $a_t$.

Question. In this hierarchical signature scheme, given $A_t$ and $t$ but not $A$, and given a signature $(R, s)$ on a message $m$ under key $A$, can we verify the signature?

Suppose $H(A\concat t)$ is coprime with $\ell$; then it has a multiplicative inverse, say $\xi$, modulo $\ell$, so that $$\xi H(A\concat t) \equiv 1 \pmod \ell.$$ If $A_t$ is a scalar multiple of the order-$\ell$ point $B$, then $$[\xi]A_t = [\xi]([H(A\concat t)]A) = [\xi H(A\concat t)]A = A.$$ Thus we can recover $A$ from $A_t$ and $t$, and use that to verify the signature $(R, s)$ on $m$.

Under uniform random choice of $H$, then probability that $\ell$ divides $H(A\concat t)$ is negligible; under the standard $H$ based on SHA-512, the overwhelming majority of outputs are not multiples of $\ell$. If this bothers you on aesthetic grounds (the probability is so small it is inconsequential for security), you could use $H(A\concat t) \bmod 2^{252}$ instead of $H(A\concat t)$ in the above protocol.

Adapting this to other hierarchical signature schemes and other curves is left as an exercise for the reader.

$\endgroup$
  • $\begingroup$ Thank you for detailed answer. I will need to revisit some of my university math memories. However from your explanation it is that the At=F(A,t) must be reversible in nature, so that the process of verification begins with getting A based on known At,t. Would there be any ways to achieve the same with F(A,t) being irreversible? (I presume there may be not, but I may be wrong about that). $\endgroup$ – Alexey Kamenskiy Sep 6 '17 at 2:57
  • $\begingroup$ This system works because $F_t\colon A \mapsto F(A, t)$ is reversible, yes. Is there another way to do this in some signature scheme without recovering $A$ as an intermediate step? Maybe, maybe not. Certainly the easiest way to design a cryptosystems with the properties you sought is to make $F_t$ reversible. In the case of Ed25519, you definitely need to recover $A$, because the verifier has to be able to compute computes $H(R\mathop\Vert A\mathop\Vert m)$. $\endgroup$ – Squeamish Ossifrage Sep 6 '17 at 13:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.