On treewidth, separators and Yao's garbling
From MaRDI portal
Publication:2697873
DOI10.1007/978-3-030-90453-1_17OpenAlexW3196678725MaRDI QIDQ2697873
Karen Klein, Krzysztof Pietrzak, Chethan Kamath
Publication date: 13 April 2023
Full work available at URL: https://doi.org/10.1007/978-3-030-90453-1_17
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A generalization of Spira's theorem and circuits with small segregators or separators
- Satisfiability, branch-width and Tseitin tautologies
- A proof of security of Yao's protocol for two-party computation
- Finding good approximate vertex and edge partitions is NP-hard
- A partial k-arboretum of graphs with bounded treewidth
- Succinct garbling schemes from functional encryption through a local simulation paradigm
- Adaptively secure garbling with near optimal online complexity
- Be adaptive, avoid overcommitting
- Balancing bounded treewidth circuits
- Adaptively indistinguishable garbled circuits
- Limits on the adaptive security of Yao's garbling
- Adaptive security of practical garbling schemes
- Adaptively secure and succinct functional encryption: improving security and efficiency, simultaneously
- Efficient cryptographic schemes provably as secure as subset sum
- Adaptively Secure Garbled Circuits from One-Way Functions
- Encoding Functions with Constant Online Rate or How to Compress Garbled Circuits Keys
- Instantiating Random Oracles via UCEs
- Finding small balanced separators
- Adaptive Security of Yao’s Garbled Circuits
- A Note on Bennett’s Time-Space Tradeoff for Reversible Computation
- Improved approximation algorithms for minimum-weight vertex separators
- Graph minors. II. Algorithmic aspects of tree-width
- Time/Space Trade-Offs for Reversible Computation
- A Separator Theorem for Planar Graphs
- Applications of a Planar Separator Theorem
- Fast Approximate Graph Partitioning Algorithms
- The Parallel Evaluation of General Arithmetic Expressions
- Adaptively Secure Garbling with Applications to One-Time Programs and Secure Outsourcing
- Parameterized and Exact Computation
- Fully Key-Homomorphic Encryption, Arithmetic Circuit ABE and Compact Garbled Circuits
- NC-algorithms for graphs with small treewidth
