Security Against Covert Adversaries: Efficient Protocols for Realistic Adversaries
Yonatan Aumann, Yehuda Lindell
J Cryptology 2010 [pdf] [bibtex]
A model of covert adversaries is defined, which lies between the standard semi-honest and malicious models. A covert adversary is allowed to deviate from the prescribed protocol but does not wish to be caught. Informally, the "success condition" for a covert adversary is cheating without detection.
A protocols providing covert security is parameterized by a deterrence factor {$\epsilon$}, guaranteeing that a cheating adversary will be detected by the honest parties with probability at least {$\epsilon$}. Note that covert security collapses to malicious security when {$\epsilon$} is overwhelming in the security parameter.
Three approaches to formally defining covert security are discussed:
- Failed-simulation: Consider an adversary that makes the real and ideal views (in the sense of semi-honest security) distinguishable with probability {$\Delta$}. Intuitively, higher values of {$\Delta$} mean the adversary is "cheating more." We require that the honest parties detect cheating with probability at least {$\epsilon \cdot \Delta$}.
- Explicit-cheat: The ideal functionality is augmented in the following way. An ideal adversary can send a special "cheat" command to the ideal functionality. Upon receiving such a command, the ideal functionality hands full control of itself to the adversary, but with probability {$\epsilon$} also informs the honest parties. Note that in either case (cheating detected or undetected), the adversary has full control over the functionality, and in particular sees the honest parties' inputs.
- Strong explicit-cheat: This formulation is similar to above, except that the adversary gets control of the functionality only if the cheating is undetected (i.e., in the probability {$1-\epsilon$} event that the functionality does not notify the honest parties). Hence, when an adversary is caught cheating, the honest parties are guaranteed that no information was leaked.
A simple covert 2-party protocol is described as well. It is based on the cut-and-choose approach applied to Yao's garbled circuit protocol. The sender sends {$\ell$} garbled circuits, of which a random {$\ell-1$} are checked. The remaining circuit is used for evaluation. Since only one circuit is evaluated, there is no need for input consistency checks, making this protocol considerably simpler than cut-and-choose approaches for malicious security. Furthermore, instead of computing {$f(x_1, x_2)$}, the parties compute {$f'(x_1, x_{2,1}, \ldots, x_{2,m}) = f(x_1, \bigoplus_i x_{2,i})$}, in which the receiver's true input {$x_2$} is split into {$m$} shares. This protocol achieves covert deterrence factor of {$\epsilon = (1- 1/\ell) (1- 2^{-m+1})$}, of the strong explicit cheat variety.
Categories:
- Home page
- All papers, by:
- .. category
- .. author names
- .. publication date
- .. recently added
- .. recently updated
- Glossary
- About
- Just getting started in MPC?
- Guidelines
- Todo List
Search Papers
Bibliography Categories