6
$\begingroup$

I am looking at ways to blind an ECDSA signing key (and verification key respectively).

Looking at proposed solutions like the IETF KBSS draft, and the IETF ARKG draft it seems that the ECDSA key blinding requires a multiplicative blinding with a blinding value $b$ that cannot be controlled by an attacker (and I assume malicious user). Given an original key pair $(d, Q_d)$ the blinded key pair is computed as $(b \cdot d, b \cdot Q_d)$.

However, neither ARGK or KBSS details how this multiplication is to be achieved (secure hardware may limit access to the private key). In SECDSA, Verheul proposes an approach where a multiplication can be done without learning the private key as follows: enter image description here

The SCE-key and PIN-key represent two private keys with the former being hardware protected. Seemingly, the PIN-key could be replaced with a blind to create a blinded signing key ($\sigma \cdot u$) and a blinded public key ($\sigma \cdot uG$).

I understand how the proposed algorithm can generate a signature using the blinded private key that can be verified using the blinded public key. But the paper does not give any formal security proof. Is the above proposal secure if $\sigma$ cannot be chosen freely? Is anyone aware of similar approaches? Is the approach in Algorithm 6 novel in these sense that it can blind a private key without having to learn the value of the original private key?

Update: There seems to be similar techniques as the one presented above. Threshold ECDSA was discussed earlier in the 54874 post, and essentially presents ways to compute a signature using two different private keys as input. For instance, Lindell 2017 as well as MacKenzie & Reiter 2004 discuss a threshold signature ECDSA scheme that relies on an approach that is similar to the multiplicative blinding use case. Adopting their work to a setting where a single user controls both keys is easy and seems to be the exact same algorithm as algorithm 6 in the Verheul paper.

$\endgroup$

2 Answers 2

5
$\begingroup$

The security of the basic version of Split-ECDSA (SECDSA) is based on the security of 'raw ECDDSA signing', i.e. the way how signing is done in practice. Here the application calling the cryptographic library/hardware computes the hash and offers that to the cryptographic library/hardware to sign.

You can find further details here StackexchangeResponse.pdf. I will add this security argument in the SECDSA paper itself too.

$\endgroup$
5
  • $\begingroup$ It isn't often that a question directly leads to such a response and amendment to a paper. Thanks for responding in that kind of depth. I'm removing some niceties from the Q & A if you don't mind, that's just basic policy on Stack Exchange. $\endgroup$
    – Maarten Bodewes
    Commented Mar 14 at 18:13
  • $\begingroup$ Thank you very much Maarten for you kind words. (-; Actually, is is an addition to the paper not a adjustment. Eric $\endgroup$ Commented Mar 17 at 16:34
  • $\begingroup$ @EricVerheul Thanks a lot! My understanding of your response is that SECDSA is secure as long as the security of the SCE holds. I find the approach very interesting for blinded key signing. Could you confirm that the associated patent claims (in patents.google.com/patent/WO2022050833A1/en) do not cover the blinding key sign use case and/or that there is no other patent filed for the blinding key use case? $\endgroup$ Commented Mar 18 at 9:54
  • $\begingroup$ A second SECDSA patent application was filed specifically on SECDSA blinding as indicated here: linkedin.com/pulse/… $\endgroup$ Commented Mar 19 at 8:42
  • $\begingroup$ @EricVerheul Algorithm 6 seems very similar to threshold ECDSA / S-DSA signing. It is in fact the same multiplicative approach used, with the addition of securing the algorithm given that the two parties in prior work is not assumed to be the same entity as it is in SECDSA. How is SECDSA different (see post update for references)? $\endgroup$ Commented Mar 25 at 7:38
1
$\begingroup$

Since SECDSA may have a patent for the technique used for blinding (and I do not know the licensing terms or if the patent is valid given prior work on threshold ECDSA), I looked at some other discrete log based signature schemes. I will post the reply here for those interested in alternatives even if the post title focused on ECDSA.

Some, like EdDSA do not work due to how the signature is computed and verified. Others, like ElGamal and Schnorr seem to work. ElGamal is not SOG-IS approved so Schnorr may be interesting in cases where you need SOG-IS suites.

Schnorr seemingly supports both additive and multiplicative key blinding using a hardware-protected private key. The additive one is easier and the general approach is shown below:

User parts:

  1. A random blind $b \in \mathbb{Z}_p^*$
  2. Let $r=g^k$ where $k \in \mathbb{Z}_p^*$
  3. Let $e=H(r || M)$
  4. Let $s=k-xe$ where $x$ is the private key $x \in \mathbb{Z}_p^*$

The signature $(s,e)$ can be blinded outside the secure cryptographic environment as follows:

  1. Let $s_b = s - be$
  2. Let $y_b = g^x \cdot g^b = g^{x+b}$ be the blinded public key.

Verification:

  1. Let $r_v=g^{s_b} y_b^e = g^{k-xe-be} g^{(x+b)e}=g^k$
  2. Let $e_v = H(r_v || M)$.
  3. Blinded key signature is verified if $e_v = e$
$\endgroup$
3
  • $\begingroup$ But EdDSA basically corresponds to Schnorr signatures on Edwards curves so I assume key blinding should work the same way there or am I missing something? (btw. the hash function is missing for the first e calculation) $\endgroup$
    – cryptphil
    Commented Mar 19 at 14:40
  • $\begingroup$ The SECDSA benefit is that is can be based on any ECDSA hardware implementation of which there many available (iOS/Secure Enclave, Android/HBKorStrongbox, Linux-Windows/TPM), unlike for EdDSA or Schnorr etc. Secure Enclave only supports ECDSA signing and Android only RSA and ECDSA signing. $\endgroup$ Commented Mar 19 at 19:53
  • $\begingroup$ @cryptphil key blinding in EdDSA works the same way, but would require changes to existing secure hardware implementations given how the signature is computed. Schnorr however is supported with existing hardware and, I suspect, will gain a lot of HW support going forward. More interestingly, threshold signatures already seem to do the exact same thing as Algorithm 6 in the Verheul paper so I am a bit confused what the patent actually covers. $\endgroup$ Commented Mar 25 at 7:41

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.