Does there exist any asymmetric cryptosystem that has the following properties:

If I know somebody's public key PBK_1 and my own key pair (PVK_2,PBK_2), I can construct a new public key PBK_3 such that:

 enc(M,PBK_3) = enc(enc(M,PBK_1),PBK_2)

and PBK_3 has the same space and time cost as PBK_1 and PBK_2, or at least doesn't suffer linear blow-up? Obviously if I can use twice the space and time, I can define PBK_3 = (PBK_1,PBK_2) and so forth.

and (I think this is implied by the above but I'll mention it explicitly) that the plaintext and ciphertext are the same size.

My quick survey of cryptosystems reveals no good candidates. The Niederreiter cryptosystem looks like it could compose public keys, except that they are rectangular matrices n x (n-k) instead of square. RSA looks like it could physically represent the composed key, but offers no way to find it without factoring PBK_1. Others either expanded the ciphertext or couldn't compose keys at all.

  • $\begingroup$ ECC allows key derivation for most curves, see Bitcoin hierarchical deterministic wallets for one example. There's also ways to combine separate keys with these curves. Also see various threshold encryption schemes, ring signatures and more. Not sure about availability of implementations $\endgroup$ – Natanael May 28 at 14:15
  • $\begingroup$ Thanks for the answer. Maybe I'm just not seeing it, but none of these leads seemed to do this with asymmetric cryptosystems. The way to use ECC as a cryptosystem seemed to be to use it for key agreement and then switch to a symmetric key system. Hierarchical deterministic wallets seemed to just generate wallet keys from a tree of hash functions. Ring signatures, at least the construction that I found, chained some text thru multiple applications of a symmetric encryption system. $\endgroup$ – Tom B May 30 at 15:06
  • $\begingroup$ While following the ECC lead, I did come across systems that do the converse, proxy re-encryption. For instance nucypher.com/proxy-re-encryption and spar.isi.jhu.edu/~mgreen/prl Proxy re-encryption wants to chain the decryption side, and therefore needs the secret key. Nucypher got around this by secret-sharing shards of something derived from the private key. If I had known proxy re-encryption existed I would have titled this question differently. $\endgroup$ – Tom B May 30 at 15:16

Your Answer

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

Browse other questions tagged or ask your own question.