Abstract: MPC-in-the-head based protocols have recently gained much popularity and are at the brink of seeing widespread usage. With widespread use come the spectres of implementation issues and implementation attacks. Side-channel attacks are a serious threat to the security of implementations of secure cryptographic protocols due to unintended leakage of sensitive information. We show that implementations of protocols constructed by the MPC-in-the-head paradigm are vulnerable to such attacks. As a case study, we choose the ZKBoo-protocol of Giacomelli, Madsen, and Orlandi (USENIX 2016) and show that even a single leaked value is sufficient to break the security of the protocol. To show that this attack is not just a theoretical vulnerability, we apply differential power analysis to show the vulnerabilities of the device.
In order to remedy this situation, we extend and generalize the ZKBoo-protocol by making use of the notion of strong non-interference of Barthe et al. (CCS 2016). To apply this notion to ZKBoo, we construct novel versions of strongly non-interfering gadgets that balance the randomness across the different branches evenly. Finally, we show that each circuit can be decomposed into branches using only these balanced strongly non-interfering gadgets. This allows us to construct a version of ZKBoo, called $(n+1)$-ZKBoo secure against side-channel attacks with very limited overhead in both signature-size and running time. Furthermore, $(n+1)$-ZKBoo is scalable to the desired security against adversarial probes. We experimentally confirm that the attacks successful against ZKBoo no longer work on $(n+1)$-ZKBoo.