"Safe" or Safest Method for Non-Hardened Key Derivation Functionality

Question

I'm currently working on the development of an unorthodox system in which, ideally, there would be one master key pair, with thousands of keys derived from it. There needs to be a way to prove that any one of those keys is derived from the master key. In this scenario, the private and the public keys of all of the derived keys can be considered common knowledge and can be used in that verification process. The public key in the master key pair may also be considered common knowledge. The only secret entity is the private key in the master key pair. I am aware that using non-hardened derivation, it is possible to accomplish this goal, yet that it contains many security risks, and the private key in the master key pair could be figured out (making non-hardened derivation as I've seen it, an unacceptable solution, unless you know of a way to make this process safe).

Is there any way to prove that derived keys could only have come from one master key pair, without exposing that master key pair's private key? Is there a safe way to do this with non-hardened key derivation? Is there a way to do this with zero knowledge proofs (they would have to be non-interactive)? Assume that it would not be feasible for the master to simply create and sign a document listing keys they've derived (new keys could be derived at any moment, and there could theoretically be too many keys derived to list within message size constraints). You may also assume that any algorithm that can accomplish this goal can be used (i.e. not necessarily just RSA).

This is for sure an abstract and vague question, so please guide me on what more information you need or how I can amend this question. Thanks.

Answer 1

There needs to be a way to prove that any one of those keys is derived from the master key. In this scenario, the private and the public keys of all of the derived keys can be considered common knowledge and can be used in that verification process.

The following seems to mach that requirement (as I understand it), and the additional one that private keys embed an identifier (that could be the Common Name or/and Certificate Serial Number of a certificate of the derived private key).

• The master key is for a deterministic signature scheme with total message recovery with no place for a side-channel (that is: verification of a signature does not require the message, which is recovered as part of the signature verification; and it is impossible for anyone, including holding the master private key, to exhibit two different valid signatures for the same message).
• Derived keys are for an (e.g. signature) scheme with the properties that:
  • a private key can be any signature per the master key scheme;
  • the public key is a public function of the private key;
  • it's impossible to turn a private key into a different private key yielding signatures that verify against the unmodified derived public key.

The master key signature scheme can be RSA-4096 per ISO/IEC 9796-2 mode 3, SHA-512 hash for signature and MGF1, trailer field option 1, non-alternative signature, which embeds any message up to 446-byte in a 512-byte signature.
_{We enforce that at least one bit is zero in the high-order 66 bits of the 4096-bit master key public modulus (though not the highest order bit), so that the signature codes an integer in range $[2,2^{4095}-2^{4029})$, making it suitable as private key for the scheme below.}

The derived key signature scheme can be Schnorr signature (per Claus-Peter Schnorr, Efficient Signature Generation by Smart Cards, in Journal of cryptology, 1991) with SHA-512 hash (and missing details), in the 4096-bit MODP group of RFC 2526.

The 4096-bit MODP group has internal law the integer multiplication modulo prime $p=2^{4096}-2^{4032}+2^{64}\left(\lfloor2^{3966}\pi\rfloor+240904\right)-1$. It is generated by $\alpha=2$, hence is precisely the set of all $2^k\bmod p$ for integer $k$. It has order the (Sophie Germain) prime $q=(p-1)/2$. Private key $s$ is any integer in $[0,q)$, expressed as 512 bytes. Public key is $v=2^{q-s}\bmod p$, expressed as 512 bytes.

To generate a derived key pair, we sign an identifier with the master private key, yielding the derived private key; and from that compute the derived public key. The two are paired by a public relation ($v=2^{q-s}\bmod p$ in Schnoor signature) hence the derived public key can't be changed without changing the private key. Security properties of the master signature scheme protect against forged private keys. There can't be two derived keys with the same identifier, even if the master private key was misused.

any way to prove that derived keys could only have come from one master key pair, without exposing that master key pair's private key?

To check a derived key pair, we verify its public key against its private key (which is easy with Schnorr signature), check that the alleged private key verifies as a signature against the master public key, and get the identifier in the process (which perhaps can be checked against an alleged public key certificate).