Putting the Online Phase on a Diet: Covert Security from Short MACs

Sebastian Faust; Carmit Hazay; David Kretzler; Benjamin Schlosser

Paper 2023/052

Putting the Online Phase on a Diet: Covert Security from Short MACs

Sebastian Faust

, Technical University of Darmstadt

Carmit Hazay

, Bar-Ilan University

David Kretzler

, Technical University of Darmstadt

Benjamin Schlosser

, Technical University of Darmstadt

Abstract

An important research direction in secure multi-party computation (MPC) is to improve the efficiency of the protocol. One idea that has recently received attention is to consider a slightly weaker security model than full malicious security -- the so-called setting of $\textit{covert security}$. In covert security, the adversary may cheat but only is detected with certain probability. Several works in covert security consider the offline/online approach, where during a costly offline phase correlated randomness is computed, which is consumed in a fast online phase. State-of-the-art protocols focus on improving the efficiency by using a covert offline phase, but ignore the online phase. In particular, the online phase is usually assumed to guarantee security against malicious adversaries. In this work, we take a fresh look at the offline/online paradigm in the covert security setting. Our main insight is that by weakening the security of the online phase from malicious to covert, we can gain significant efficiency improvements during the offline phase. Concretely, we demonstrate our technique by applying it to the online phase of the well-known TinyOT protocol (Nielsen et al., CRYPTO '12). The main observation is that by reducing the MAC length in the online phase of TinyOT to $t$ bits, we can guarantee covert security with a detection probability of $1- \frac{1}{2^t}$. Since the computation carried out by the offline phase depends on the MAC length, shorter MACs result in a more efficient offline phase and thus speed up the overall computation. Our evaluation shows that our approach reduces the communication complexity of the offline protocol by at least 35% for a detection rate up to $\frac{7}{8}$. In addition, we present a new generic composition result for analyzing the security of online/offline protocols in terms of concrete security.

Note: This is the full version of the paper of the same name published at CT-RSA 2023.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. CT-RSA 2023
Keywords: Multi-Party Computation (MPC)Covert Security Offline/Online Deterrence Composition
Contact author(s): sebastian faust @ tu-darmstadt de
carmit hazay @ biu ac il
david kretzler @ tu-darmstadt de
benjamin schlosser @ tu-darmstadt de
History: 2023-01-19: approved; 2023-01-16: received; See all versions
Short URL: https://ia.cr/2023/052
License: CC BY

BibTeX

@misc{cryptoeprint:2023/052,
      author = {Sebastian Faust and Carmit Hazay and David Kretzler and Benjamin Schlosser},
      title = {Putting the Online Phase on a Diet: Covert Security from Short {MACs}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/052},
      year = {2023},
      url = {https://eprint.iacr.org/2023/052}
}