In another thread people are discussing the problems with unauditable implementations of ECDSA (

https://bitcointalk.org/index.php?topic=883793.0). Everyone assumes a non-interactive signing method. If you allow interaction, then the solution seems to be easy.

A year ago, when I designed the Firmcoin (

Firmcoin.com), I proposed an implementation of a ECDSA signer which uses a random k, but uses a fair coin-flipping kind of protocol to create a k that is private but auditable. In other words, the device and the software in the PC cooperate to create a k value that such that the following properties hold :

1. k is uniformly random and covert-channel-free if the PC software is not backdoored and the device is backdoored

2. k is is uniformly random and covert-channel-free if the PC software is backdoored and the device is not backdoored

3. The PC software cannot obtain the private key.

The full protocol is described here:

http://firmcoin.com/?p=52 But I'm copying it here:

The signing of a transaction using the private key is a special two-party protocol. A ECDSA signature consist of the tuple (r,s). All known subliminal channels in ECDSA consist of hiding some information in r. s is computed deterministically from d_A, z and r (except from a single bit, which is the sign of y_1). Our protocol guarantees that r is indeed random.

This is the standard ECDSA signing protocol:

1. The signer calculates e = HASH(m), where HASH is a cryptographic hash function, such as SHA-1.

2. Let z be the L_n leftmost bits of e, where L_n is the bit length of the group order n.

3. The signer selects a random integer k from [1, n-1].

4. The signer calculates the curve point (x_1, y_1) = k * G.

5. The signer calculates r = x_1 (mod n). If r = 0, go back to step 3.

6. The signer calculates s = k^{-1}(z + r d_A) (mod n). If s = 0, go back to step 3.

7. The signature is the pair (r, s) which is sent to the user.

This is our protocol (the user is the PC software the user trusts)

1-2. These steps are similar to the standard protocol.

3. The signer selects a random integer u from [1, n-1].

3.1. The signer calculates Q=u * G.

3.2. The signer calculates h=HASH(Q). This is a commitment to Q.

3.3. The signer sends h to the user.

3.4. The user selects a random integer t from [1, n-1].

3.5. The user sends t to the signer.

3.6. The signer verifies t is [1, n-1]. The signer sends Q to the user.

3.7. The user verifies that HASH(Q)=h. If not equal, then the signer is cheating.

3.8. The signer calculates k = t * u.

4-7. These steps are similar as the standard protocol.

8. The user calculates the curve point (x_2, y_2) = t * Q.

9. The user verifies that r = x_2 (mod n). If not equal, then the signer is cheating.

This protocol guarantees that the r value is chosen uniformly random from the set of x-coordinates of curve points, and at the same time guarantees that the user cannot arbitrarily force this value.

It must be noted that the protocol should not be repeated unlimited times if it fails. If failure occurs after step 3.5, and not before step 6, because of the signer not responding properly (either providing and invalid message or by not responding at all), then a new iteration of the protocol may allow the signer to leak some information. If the signer fails n times before finishing the protocol properly, then a side channel that hides approximately log2(n) bits may have been tried. For an 256-bit ECDSA private key, we would not recommend executing the protocol more than 16 times if is continuously fails, limiting the amount of information leakage to 4 private bits.

If you find a vulnerability with this protocol please let me know. Also if anyone wants to do a formal analysis of it that would be awesome. As far as I have studied it, it relies on the same crypto assumptions of ECDSA.

Best regards,

Sergio.