Quote from: hhanh00 on December 05, 2014, 06:36:49 PM

In other words, the online device transfers the digest and pubkey to the signer. The signer returns (r, s) where k follow RFC 6979. The online device builds the transaction and the user checks that the inputs/outputs are what he expects.
Can something still go wrong?

Yes. k can be deterministic, but it has to be unknown, otherwise you can extract the private key d from (r, s). In RFC6979, the choice of k depends on the private key d, it (hopefully) cannot be reproduced without it.

tl;dr thread summary:

gmaxwell's proposal based on blind Schnorr signatures prevents that by replacing the r component of a signature with a different value r' which depends on two random choices, only one of which is made by the offline wallet itself. r is still generated in the process, but not published into the blockchain.
Problems:
-- The original r has to be kept secret.
-- Schorr signatures are not compatible with ECDSA, so this solution requires a change of the Bitcoin protocol.

In my proposal using ZK proofs, the offline wallet outputs a proof p together with the signature (r, s), where p proves the following statement: (Q is the public key, m the message.)

Code:

There exist integer numbers d, x, k such that: Q=dG AND k=H(m||d) AND (r, x) = kG.

Since the formula has only existentially quantified variables, it is an NP statement and we know that there exist ZK proofs for it. Since the wallet knows the witnesses d and k, it has all the knowledge necessary to generate such a proof efficiently.
Problems:
-- How to make sure that the wallet does now leak secrets through the proof, as most ZK proofs require lots of random choices by both parties (prover and verifier).
-- Alternatively the proof has to be kept secret like the original r in the blind Schnorr signature scheme.
-- How to make the proof efficient enough for practical applications, especially the part k = H(m||d) for a complicated cryptographic hash function H.