I need to design a system where there is a secure device (a.k.a. HW wallet), with the following functionality:
- Deterministic key generation for key parameters (speaking simply: key ID).
- Never expose/compromise secret keys.
- Participate in signing schemes, such as Schnorr, Bulletproof.
- Support multisignatures.
- Should have simple design, limited memory capabilites, etc.
Now, all our cryptographic schemes follow more-or-less the same ritual: Prover generates a nonce, exposes its image, receives a challenge, and then exposes the pre-image, which is in fact a blinded secret key. And, of course, we're using the Random Oracle Model (a.k.a. Fiat–Shamir heuristic) to generate challenges.
In order to guarantee (2), there is an assumption that the Prover must never answer to different challenges for the same nonce. And this is absolutely vital!
When used in a standard signature protocol, there is no problem. Once the nonce is generated and revealed - the challenge can also be generated in a deterministic way by the wallet itself. So that the whole signing process is atomic.
For multisignatures, however, this is not the case. There are 2 (or more in case of Bulletproof) iterations, where first all the nonce-dependent images are revealed by all the parties, aggregated, and then during the next iteration the preimages should be revealed.
And this is the problem actually. Ideally I'd like the HW wallet to be stateless, just generate everything when needed in a deterministic way. But, as we see, in a multisignatures challenges just can't be calculated from visible data, hence the HW wallet may easily be cheated. Also the multi-signature ritual may be time consuming, during which I'd like the HW to be able to operate normally.
The best solution I could think about is adding some amount of memory slots dedicated to mutlisignatures. The caller would allocate the slot number for each multisignature in progress (in case there are several such). It would generate a unique nonce (i.e. not deterministic from the being-signed message). Then to finalize the signature the caller would supply the challenge and the slot number, and the HW wallet would reveal the expected preimage and then immediately erase the contents of this slot.
So this seems to solve the problem, but, naturally, has disadvantages. The device with state is obviously more complex, which isn't good for security. Limited number of ongoing signatures isn't an advantage either. The device should have a writable non-volatile memory, which is presumable an attack target, and so on.
So, my question is: are there alternatives, which assume stateless HW wallet? Is there a ritual where we can convince it that we don't use different challenges for the same nonce, perhaps in expense of more iterations?