Show simple item record

dc.contributor.author
Kamath, Chethan
dc.contributor.author
Klein, Karen
dc.contributor.author
Pietrzak, Krzysztof
dc.contributor.editor
Nissim, Kobbi
dc.contributor.editor
Waters, Brent
dc.date.accessioned
2021-11-09T07:48:13Z
dc.date.available
2021-11-08T15:57:43Z
dc.date.available
2021-11-09T07:48:13Z
dc.date.issued
2021
dc.identifier.isbn
978-3-030-90452-4
en_US
dc.identifier.isbn
978-3-030-90453-1
en_US
dc.identifier.issn
0302-9743
dc.identifier.issn
1611-3349
dc.identifier.other
10.1007/978-3-030-90453-1_17
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/514353
dc.description.abstract
We show that Yao’s garbling scheme is adaptively indistinguishable for the class of Boolean circuits of size S and treewidth w with only a S^O(w) loss in security. For instance, circuits with constant treewidth are as a result adaptively indistinguishable with only a polynomial loss. This (partially) complements a negative result of Applebaum et al. (Crypto 2013), which showed (assuming one-way functions) that Yao’s garbling scheme cannot be adaptively simulatable. As main technical contributions, we introduce a new pebble game that abstracts out our security reduction and then present a pebbling strategy for this game where the number of pebbles used is roughly O(δwlog(S)), δ being the fan-out of the circuit. The design of the strategy relies on separators, a graph-theoretic notion with connections to circuit complexity.
en_US
dc.language.iso
en
en_US
dc.publisher
Springer
en_US
dc.subject
adaptive security
en_US
dc.subject
garbled circuits
en_US
dc.title
On Treewidth, Separators and Yao’s Garbling
en_US
dc.type
Conference Paper
dc.date.published
2021-11-04
ethz.book.title
Theory of Cryptography
en_US
ethz.journal.title
Lecture Notes in Computer Science
ethz.journal.volume
13043
en_US
ethz.journal.abbreviated
LNCS
ethz.pages.start
486
en_US
ethz.pages.end
517
en_US
ethz.event
19th International Conference on Theory of Cryptography (TCC 2021)
en_US
ethz.event.location
Raleigh, NC, USA
en_US
ethz.event.date
November 8-11, 2021
en_US
ethz.grant
Preparing Cryptography for Modern Applications
en_US
ethz.identifier.wos
ethz.publication.place
Cham
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::09693 - Hofheinz, Dennis / Hofheinz, Dennis
en_US
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::09693 - Hofheinz, Dennis / Hofheinz, Dennis
en_US
ethz.grant.agreementno
724307
ethz.grant.agreementno
724307
ethz.grant.fundername
EC
ethz.grant.fundername
EC
ethz.grant.funderDoi
10.13039/501100000780
ethz.grant.funderDoi
10.13039/501100000780
ethz.grant.program
H2020
ethz.grant.program
H2020
ethz.date.deposited
2021-11-08T15:57:49Z
ethz.source
FORM
ethz.eth
yes
en_US
ethz.availability
Metadata only
en_US
ethz.rosetta.installDate
2021-11-09T07:48:24Z
ethz.rosetta.lastUpdated
2022-03-29T15:54:39Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=On%20Treewidth,%20Separators%20and%20Yao%E2%80%99s%20Garbling&rft.jtitle=Lecture%20Notes%20in%20Computer%20Science&rft.date=2021&rft.volume=13043&rft.spage=486&rft.epage=517&rft.issn=0302-9743&1611-3349&rft.au=Kamath,%20Chethan&Klein,%20Karen&Pietrzak,%20Krzysztof&rft.isbn=978-3-030-90452-4&978-3-030-90453-1&rft.genre=proceeding&rft_id=info:doi/10.1007/978-3-030-90453-1_17&rft.btitle=Theory%20of%20Cryptography
 Search print copy at ETH Library

Files in this item

FilesSizeFormatOpen in viewer

There are no files associated with this item.

Publication type

Show simple item record