Cryptology ePrint Archive: Report 2020/544

SNI-in-the-head: Protecting MPC-in-the-head Protocols against Side-channel Analysis

Okan Seker and Sebastian Berndt and Thomas Eisenbarth

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.

Category / Keywords: cryptographic protocols / MPC-in-the-head, Zero Knowledge, Strong Non-Interference

Date: received 9 May 2020

Contact author: okan seker at uni-luebeck de, s berndt@uni-luebeck de, thomas eisenbarth@uni-luebeck de

Available format(s): PDF | BibTeX Citation

Version: 20200515:094312 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]