Suppose that we have three authorities which each of them generate one secret/public key for Alice. It means that Alice has three secret keys and three related public keys. Suppose that Alice combines these three secret keys in a way with any kind of function and generate a new secret key (forth secret key), can he generate the related forth public key by any function or not? Is there any relationship between these two functions?

  • $\begingroup$ What do you want the fourth key to do? Can Alice generate a fourth key? Sure, she'll just generate a new keypair, ignoring the first three keys. Do you want the fourth key to have any relation to the first three? $\endgroup$ – DreamConspiracy Dec 12 '18 at 17:35
  • $\begingroup$ How do you guarantee that this fourth key is valid? For example, if I have public/private RSA keys (e1, d1, n1), (e2, d2, n2) and (e3, d3, n3), the key (e1+e2+e3, d1+d2+d3, n1+n2+n3) is probably not a valid RSA public/private key. $\endgroup$ – Eugene Styer Dec 12 '18 at 17:40
  • $\begingroup$ @DreamConspiracy I want to have a robust system. Suppose that an attacker hack on of the authorities, it cannot find Alice's key without hacking other two authorities. Does it make sense? $\endgroup$ – tesoke Dec 12 '18 at 17:56
  • $\begingroup$ @ Eugene Styer So can we change the question? What if three authorities generate three keys in a way that adding those three key be RSA key. Is it applicable? $\endgroup$ – tesoke Dec 12 '18 at 18:00
  • $\begingroup$ If the sole requirement is that knowledge of only two of the authorities is insufficient to recover Alice's fourth private key, why is this not a valid answer: Alice selects some randomness, and then runs the standard public/private key pair generation algorithm, and uses that as the fourth key. Because none of the authorities know the randomness Alice picked, hacking into the authorties tell the adversary nothing. Again, is there a specific reason why this isn't a valid solution? (This was DreamConspiracy's original question) $\endgroup$ – poncho Dec 12 '18 at 19:12

What's asked is possible, both for public-key encryption and signature schemes.

One option can be a concatenation of the keys, with delimiters allowing separation of concatenated keys (by the same function for public and private keys), with

  • for encryption, cascaded encryption in order of the public keys
  • for decryption, cascaded decryption in reverse order of the private keys
  • for signature (with appendix), concatenation of the signatures in the order of the private keys, with delimiters allowing separation of the signatures
  • for signature verification, verification of all the signatures in the order of the public keys (and success iff all the signatures check).

More in details, restricting to public-key encryption: we start from some hybrid public-key encryption scheme, easily implemented with wrapper scripts on top of GPG. Encryption accepts any plaintext file and a public key (as a text file starting with -----BEGIN PGP PUBLIC KEY BLOCK----- restricted to a single such block), and outputs a ciphertext file. Decryption accepts a ciphertext file and the matching private key (as a text file starting with -----BEGIN PGP PRIVATE KEY BLOCK----- restricted to a single such block), and outputs the original plaintext.

We define the question's functions building new keys to both be concatenation: the "fourth secret key" is the file obtained by concatenation of the first three secret keys (with some EOLs as separator), same for the public keys.

We modify the encryption script to parse its public key input and, for each public key found in that, encrypt the plaintext (for the first key) or the previous encryption result (for the next ones, if any). It outputs the final ciphertext obtained.

We modify the decryption script in the same way, except that it processes multiple private keys starting from the last one in the private key input file.

The modified encryption and decryption scripts still works just as the original when fed a single public or private key. And when using the fourth public and private keys as obtained by the concatenation functions, they are able to encrypt and decrypt.

It can be proven that if GPG is secure, then the new scheme obtained is.

  • $\begingroup$ @ fgrieu Can you give me a simple example to this. Sorry, I am a beginner in cryptography and need more help. Thanks. $\endgroup$ – tesoke Dec 12 '18 at 18:08

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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