Elliptic curve cryptography and key sharing

Question

I want to know if it is possible in Elliptic curve cryptography to have 2 parties holding a part of the private key. The idea is to encrypt (for DSA) data with the 2 sub keys without any of the party getting hold of the original private key.

For example:

• Issue a private key
• Split somehow the private key into 2 sub private keys
• Encrypt data with the first key
• Encrypt with the second key
• The end result should be like if data was encrypted with the original private key

Is this thing possible? Ideally the 2 sub keys should be the size of the original private key and should not leak any information.

Thanks

edit: Sorry for not being clear, when speaking about encryption it was meant for DSA

Answer 1

With asymmetric cryptography, you normally encrypt with the public key, not the private key; with the private key, you decrypt. Moreover, asymmetric encryption is usually randomized, so it can be hard to tell that you get "the same result" than what you would have with a single private key, since you can actually get a whole range of values (which would decrypt to the same message, though). Maybe you want to speak about signatures ?

In any case, there are a lot of possible protocols for multiparty computations (that's the term for that kind of things). See this site for a lot of links. In your case, I suppose that you have two parties who need to use a private key so that their combined actions are equivalent in some sense to what could be achieved with a single secret value, that neither knows. Protocols which achieve that depend on the exact extent of the knowledge and action of both parties:

• Are the two key holders considered to be potential active attackers, or only passive ? I.e. do we want to protect the secrecy of the scheme if one of the parties begins to send incorrect, carefully crafted messages to the other ?
• What is the level of control that the key holders have on the input data ? Can they modify it in some way to reveal information about the the other key half ?
• Should each party be able to ascertain that the other party played the protocol faithfully ?
• Should such a proof be discloseable to a third-party without revealing anything about the processed data or the keys ? (This is the kind of proof that is very important in, for instance, e-voting protocols.)
• What can the key holders be allowed to do ? E.g., if they can encrypt, is it OK if they can also decrypt (assuming they collaborate to the task) ?

As an illustrative example, suppose that you have an elliptic curve E with prime order n. Parties A and B knows secret keys a and b respectively; both keys are chosen uniformly in the 1..n-1 range. Suppose that you can map some input message m into a curve point M. Then A may "encrypt" the message by multiplying M with a; similarly, B multiplies points by b. If both A and B process the message in due order:

• A receives M and outputs aM.
• B receives aM and outputs (ba)M.

The final result is then equal to (ab)M, the result of the "encryption" of M by the key ab (product is modulo n), that neither A or B knows. It can be shown that A cannot learn ab regardless of what he sends to B; and the same applies to B if B is the villain. Of course, if A and B reveal their private keys to each other, then they can compute ab.

(This is an elliptic curve variant of the Pohlig-Hellman cipher -- not to be confused with the other Pohlig-Hellman algorithm. It is also known as SRA.)

Answer 2

Is there a reason that encrypting with two public keys does not solve your problem? This then requires two parties to each decrypt the content in order to gain access. An alternate approach would be to symmetrically encrypt the payload, split the key in half, encrypt each half with a user's public key. Each user would then have to decrypt their half of the key for that message and share it with the other for the message to be decrypted.

Answer 3

Generally an asymmetric encryption will use the public key to encrypt and private to decrypt the data. I dunno what purpose u want here to encrypt the data with private. Eventhough if u require , u generate the ECC key pairs and u can use the shamir secret algorithm to split the keys as M and N parts.whenever you ant to encrypt the daa using private key u can combine the key and do it.

Answer 4

I can not see how your question relates to ecc, or asymetric encryption at all, but a simple solution for the task of "splitting" a key is to use two separate keys in the first place.

More specifically, for the symmetric encryption: produce 2 keys and consider the pair as what you call the "private key" and the individual keys as the "sub keys". (Notice that these words do have a different meaning when actually talking about asymmetric cryptography.)

For the asymmetric version do as for the symmetric one, just create two key pairs, encrypt with both public keys sequentially and you will need both private keys to decrypt.

About the individual size: it depends on the specific encryption algorithm weather and to which amount encrypting twice with a key of half the length will be less secure than encrypting once with the long key. (See e.g. 3DES )