Hierarchy for classes of garbling schemes (Q2820752)

Garbled circuits were introduced by \textit{A. Yao} [How to generate and exchange secrets, IEEE 27th Ann. Symp. FOCS 1986, 162--167 (1986)] as a technique for secure multiparty computation, providing a way to securely evaluating a function \(f\), on argument \(x\). Bellare, Hoang and Rogaway formalized the notion of garbling scheme and the security notions of privacy, obliviousness and authenticity, both in the \textit{static} case [In: Proc. ACM Computer and Communications Security (CCS 2012), ACM, 784--796 (2012)] and in the \textit{adaptive} one \textit{M. Bellare}, \textit{V. T. Hoang} and \textit{P. Rogaway} [Asiacrypt 2012, Lect. Notes Comput. Sci. 7658, 134--153 (2012; Zbl 1292.94027)]. Other security notions and reusable garbled circuits were later proposed by other authors.NEWLINENEWLINEThe present paper proposes new security classes of garbling schemes, allowing ``garbled circuits that provide at least some level of reusability while still being practical to construct'', as well as a hierarchy of those classes, including the previous ones.NEWLINENEWLINE Section II gathers the concepts and terminology relatives to garbling schemes and Sections III and IV describe the security classes of the static and adaptive garbling schemes.NEWLINENEWLINEThe core Section V states and proves relations between security classes of adaptive schemes building up the hierarchy of those classes. For instance if \(C_l\), is a class of adaptive schemes, with \(l\), denoting how many times the adversary is allowed to use the same scheme, Theorem 1 proves that \(C_{l+1}\subsetneqq C_l\), (unless both classes are empty). Finally Section VI provides an interpretation of the hierarchy in terms of directed graph Cartesian product.