4
$\begingroup$

Assume I have a private key, priv_k, a public key pub_key and a message, msg, along with its hash, hash. I can produce a ECDSA signature, S, of hash using priv_k, and verify the signature with pub_key, msg and S.

It is possible to split priv_k into shares, priv_share1, priv_share2, such that I can:

  1. sign hash with priv_share1 to produce a signature S_share1 and
  2. sign S_share1 with priv_share2 to produce signature, S, that is identical to the S generated with the whole priv_k ?

Or, alternatively, is it possible to:

  1. Sign hash with priv_share1 to produce a signature S_share1 and
  2. Sign hash with priv_share2 to produce a signature S_share2 and
  3. Somehow combine S_share1 and S_share2 to produce a signature, S that is identical to the S generated with the whole priv_k?

AFAIK what I'm asking isn't possible with Shamir Secret Sharing (SSS). One could produce shares of a private key with SSS, but in the recovery process the private key would be reconstructed to produce a signature.

What I'm looking for is a way to:

Generate a private key and split the private key into shares, then throw the private key away and never have it be reconstructed in its entirety ever again for producing signatures. Ideally the private key would not even be reconstitutable from priv_share1 and priv_share2, but maybe this is not possible. Valid signatures can only be produced successively, as in the first scenario, or separately, then combined, as in the second scenario.

So, the same scenarios described in a different way, taking into account how ECDSA works under the hood:

Sign a message hash the normal way with:

S ≡ q^-1 (hash + r * priv_key) (%p)

Are these scenarios possible?

priv_share1, priv_share2 = splitPrivateKey(priv_key)

scenario #1:

S_share1 ≡ q^-1 (hash + r * priv_share1)     (%p)
S_share2 ≡ q^-1 (S_share1 + r * priv_share2)     (%p)
(S_share2 == S) == True

OR

scenario #2:

priv_share1 ≡ q^-1 (hash + r * priv_share1)     (%p)
priv_share2 ≡ q^-1 (hash + r * priv_share2)     (%p)
someFunction(priv_share1, priv_share2) = S_split
(S_split == S) == True

my apologies if this is a naive question; I don't have a background in cryptography

EDIT: Actually a verifiable signature would be OK. The signature doesn't need to match exactly the signature when signing the whole key

$\endgroup$
4
  • 1
    $\begingroup$ The short answer is no. $\endgroup$
    – kelalaka
    Jan 9 at 7:24
  • 1
    $\begingroup$ This is a job for threshold signing schemes. For 2 parties, the most common one is the Lindell 17 protocol (eprint.iacr.org/2017/552). These protocols are a bit more involved than the protocol flow in the question and use several sub protocols. Nevertheless, they are practically used in the industry. So it's possible. $\endgroup$ Jan 9 at 8:00
  • $\begingroup$ Also these protocols use distributed key generation so the key is never reconstructed in a single location, which would be bad. Some caution: Tss protocols are notoriously hard to implement securely. So best to use a vetted implementation for real world usage (github.com/ZenGo-X/Gotham-city). Even then, vulnerablity are found. So, best run the thing by an expert before deployment. $\endgroup$ Jan 9 at 8:06
  • $\begingroup$ To better understand the question: there are two ways to answer here, depending on whom the question is interpreted. 1) The question is protocols achieving goals of secure multiparty computation, and the scenarios are only illustrative. 2) The question is about whether the exact scenarios are possible while achieving some notion of security. Based on the other notes in the question, I tend to think that 1) is relevant here. But it would be good to get some clarifications on what is going to be a helpful answer. Obviously, there might be other approaches that will still be informative! $\endgroup$ Jan 10 at 21:25

1 Answer 1

1
$\begingroup$

This is kind of complex so this would need to be dealt with cases.

(I would not use $\mod {n}$ ($n$ being order of group) everywhere neither congruence sign.

Notation: $+$ and $*$ signify normal addition and normal multiplication respectively while $+'$ and $.$ would signify point addition and scalar multiplication.

CASE 1: Scenario 1 as described in question

It is not possible to achieve because:

$s_1 = q^{-1}*(m + r*x_1)$ ... (1.i)

$s_2 = q^{-1}*(s_1 + r*x_2)$ ... (1.ii)

Expanding (1.ii):

$s_2 = q^{-1}*(q^{-1}*(m + r*x_1) + r*x_2)$

$s_2 = q^{-2}*(m + r*x_1) + q^{-1}*r*x_2$

As can be seen in equation above this is a dead end situation. You cannot construct $s_2 = s$ until you are provided with a additional information.

POF1: The additional information required would be about $q$ and since it is called empirical private key providing it to someone else would easily derive private key:

$x_1 = r^{-1}*(s*k - m)$

POF2: Additionally, if this could be achieved somehow without sharing about $q$ your scheme would be ruined in the following way:

$s_1 = q^{-1}_1*(m_1 + r_1*x_1)$

$s_2 = q^{-1}_1*(m_1 + r_1*x_2)$

$s_3 = q^{-1}_2*(m_2 + r_2*x_1)$

$s_4 = q^{-1}_2*(m_2 + r_2*x_1)$

By using method described here:

$x_1 = \frac{m_1r_2s_2s_3-m_1r_2s_1s_3-m_2r_1s_1s_4+m_2r_1s_1s_3}{r_1r_2(s_2s_3-s_1s_4)}$

So successive signing I think might not work.

CASE 2: Scenario 2 as in question

Again whatever you describe can be done in practice:

Let us assume private key, say $x$ was shared by just dividing key into, say $x_1$ and $x_2$, two parts without involvement of a standard sharing scheme (involving them would cause complexity here). Let message m be divided into two equal parts namely $m_h= m/2$ and :

$s_1 = q^{-1}*(m_h + r*x_1)$

$s_2 = q^{-1}*(m_h + r*x_2)$

$s = s_1 + s_2$

$s = q^{-1}*(m_h + m_h + r*(x_1 + x_2))$

$s = q^{-1}*(m + r*x)$

but is useless in real world because of earlier described POF1 and POF2.

CASE 3: Threshold signing

Well this should work for you. But threshold signing is altogether a different story. A good paper to read on them would be this

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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