Lower and Upper Bounds on the Randomness Complexity of Private Computations of AND
From MaRDI portal
Publication:5857004
DOI10.1137/20M1314197zbMath1462.68073OpenAlexW2990594069MaRDI QIDQ5857004
Damien Vergnaud, Rafail Ostrovsky, Eyal Kushilevitz, Adrian Thillard, Emmanuel Prouff, Adi Rosén
Publication date: 30 March 2021
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/20m1314197
Cryptography (94A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Boolean functions (94D10) Communication complexity, information complexity (68Q11)
Related Items (2)
Random sources in private computation ⋮ Tight bounds on the randomness complexity of secure multiparty computation
Cites Work
- Unnamed Item
- Unnamed Item
- A full proof of the BGW protocol for perfectly secure multiparty computation
- A communication-privacy tradeoff for modular addition
- Characterizing linear size circuits in terms of privacy
- Extracting randomness: A survey and new constructions
- STACS 2003. 20th annual symposium of theoretical aspects on computer science, Berlin, Germany, February 27 -- March 1, 2003. Proceedings
- Randomness complexity of private computation
- On the Communication Required for Unconditionally Secure Multiplication
- Communication and Randomness Lower Bounds for Secure Computation
- A Theorem on Sensitivity and Applications in Private Computation
- Secure Multiparty Computation Goes Live
- Randomness in Private Computations
- A Randomness-Rounds Tradeoff in Private Computation
- Amortizing Randomness in Private Multiparty Computations
- $\Omega(\log n)$ Lower Bounds on the Amount of Randomness in 2-Private Computation
- Unconditionally Secure Computation with Reduced Interaction
- A Zero-One Law for Boolean Privacy
This page was built for publication: Lower and Upper Bounds on the Randomness Complexity of Private Computations of AND
