Adaptive Security of Practical Garbling Schemes

Zahra Jafargholi, Sabine Oechsner

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

A garbling scheme enables one to garble a circuit C and an input x in a way that C(x) can be evaluated, but nothing else is revealed. Since the first construction by Yao, tremendous practical efficiency improvements for selectively secure garbling schemes --where the adversary is forced to choose both input and circuit to be garbled at the same time-- were proposed. However, in the more realistic setting of adaptive security where an adversary can choose the input adaptively based on the garbled circuit little is known about practical efficiency improvements. In this work, we initiate the study of practical garbling schemes that are both more efficient than Yao's construction and adaptively secure. We provide insights into characteristics of these schemes and highlight the limitations of current techniques for proving adaptive security in this regime. Furthermore, we present an adaptively secure garbling scheme that garbles backslashmathsf XORXORgates with 2 and backslashmathsf ANDANDgates with 3 ciphertexts per gate, thus providing the first practical garbling scheme for NC1 circuits with adaptive security based on PRFs whose garbled circuit size is smaller than that of Yao's construction.
Original languageEnglish
Title of host publicationProgress in Cryptology -- INDOCRYPT 2020
EditorsKarthikeyan Bhargavan, Elisabeth Oswald, Manoj Prabhakaran
Place of PublicationCham
PublisherSpringer International Publishing
Number of pages22
ISBN (Electronic)978-3-030-65277-7
ISBN (Print)978-3-030-65276-0
Publication statusPublished - 8 Dec 2020
Event21st International Conference on Cryptology in India - Virtual
Duration: 13 Dec 202016 Dec 2020

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference21st International Conference on Cryptology in India
Abbreviated titleIndocrypt 2020
Internet address


Dive into the research topics of 'Adaptive Security of Practical Garbling Schemes'. Together they form a unique fingerprint.

Cite this