On the number of random bits in totally private computation

DOI10.1007/3-540-60084-1_72MaRDI QIDQ4645176zbMATH OpenOpenAlexFDO

Authors Carlo Blundo, Alfredo De Santis, Giuseppe Persiano, Ugo Vaccaro

Publication date 10 January 2019

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-60084-1_72

zbMATH Keywords

Boolean functionprivate inputrandom inputrandom sourceShannon entropy

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Analysis of algorithms and problem complexity (68Q25) Measures of information, entropy (94A17) Cryptography (94A60)

Recommendations

• Randomness complexity of private computation
• scientific article; zbMATH DE number 1759657
• Random sources in private computation
• Randomness in Private Computations
• $\Omega(\log n)$ Lower Bounds on the Amount of Randomness in 2-Private Computation

Cites work

• A communication-privacy tradeoff for modular addition
• A Zero-One Law for Boolean Privacy
• Bounds on tradeoffs between randomness and communication complexity
• scientific article; zbMATH DE number 107482 (Why is no real title available?)
• scientific article; zbMATH DE number 3614066 (Why is no real title available?)
• scientific article; zbMATH DE number 1406796 (Why is no real title available?)
• On the structure of the privacy hierarchy
• Privacy and Communication Complexity
• Randomness in distribution protocols
• Randomness-optimal unique element isolation, with applications to perfect matching and related problems
• The privacy of dense symmetric functions

Cited in

(6)

• Randomness complexity of private computation
• scientific article; zbMATH DE number 1676657 (Why is no real title available?)
• A Theorem on Sensitivity and Applications in Private Computation
• Randomness in Private Computations
• scientific article; zbMATH DE number 1759657 (Why is no real title available?)
• Random sources in private computation

This page was built for publication: On the number of random bits in totally private computation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4645176)