Quote from: stv on December 05, 2014, 06:04:40 PM

But a new problem arises: How to implement the proof in a way that ensures that we don't create new side channels for leakage?

Any system that has sound zero knoweldge is going to have a random input. E.g. the CRS SNARK construction which is the only remotely practical implementation for NP available that I'm aware of is freely rerandomizable. Maybe a unique proof is possible if you give up soundness on the ZK but then a cryptographic break in the ZK system could make it leak your private key.

This complexity is part why I'd previously proposed the alternative where the online requesting device blind the signature request, then give the signing device a ZKP that the blinded message being signed is the message being signed... The result is the that the sidechannel is reduced to 1 bit (sign/don't sign) unless the requesting device and the offline device conspire. (also the aforementioned fact that it's much easier to verify a proof than create it)

From your writeup,

Quote

Another counter-measure would be to strictly not use any address more of-ten than once

This doesn't solve it: The key can be leaked in a single signature, and the attacker can race the user in the network; and 'future' keys, if they're known to the device can also be leaked at the same time using the techniques I've described.