Coin flipping of any constant bias implies one-way functions

DOI10.1145/2591796.2591845MaRDI QIDQ5259574zbMATH OpenOpenAlexFDO

Authors Itay Berman, Iftach Haitner, Aris Tentes

Publication date 26 June 2015

Published in Proceedings of the forty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2591796.2591845

zbMATH Keywords

one-way functionscoin-flipping protocolsminimal hardness assumptions

Mathematics Subject Classification ID

Cryptography (94A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Coin flipping with constant bias implies one-way functions
• Coin Flipping with Constant Bias Implies One-Way Functions
• Coin flipping of \textit{any} constant bias implies one-way functions
• Black-box use of one-way functions is useless for optimal fair coin-tossing
• From biased coin to any discrete distribution
• Can optimally-fair coin tossing be based on one-way functions?
• Biasing Boolean functions and collective coin-flipping protocols over arbitrary product distributions
• Von Neumann's biased coin revisited
• An Infinitely-Often One-Way Function Based on an Average-Case Assumption
• An infinitely-often one-way function based on an average-case assumption

Cites work

• scientific article; zbMATH DE number 5485440 (Why is no real title available?)
• scientific article; zbMATH DE number 5485574 (Why is no real title available?)
• Advances in Cryptology – CRYPTO 2004
• Answering \(n^{2+o(1)}\) counting queries with differential privacy is hard
• Bounds on the sample complexity for private learning and private data release
• Characterizing the sample complexity of private learners
• Collusion-secure fingerprinting for digital data
• Differential privacy and the fat-shattering dimension of linear queries
• Efficient algorithms for privately releasing marginals via convex relaxations
• Faster algorithms for privately releasing marginals
• Faster private release of marginals on small databases
• Interactive privacy via the median mechanism
• Iterative Constructions and Private Data Release
• Lower bounds in differential privacy
• New Efficient Attacks on Statistical Disclosure Control Mechanisms
• On the complexity of differentially private data release, efficient algorithms and hardness results
• On the geometry of differential privacy
• Our Data, Ourselves: Privacy Via Distributed Noise Generation
• Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
• The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
• Theory of Cryptography

Cited in

(6)

• Coin Flipping with Constant Bias Implies One-Way Functions
• Almost-optimally fair multiparty coin-tossing with nearly three-quarters malicious
• Coin flipping with constant bias implies one-way functions
• Coin flipping of \textit{any} constant bias implies one-way functions
• Almost-optimally fair multiparty coin-tossing with nearly three-quarters malicious
• An optimally fair coin toss

Describes a project that uses

Uses Software

• SuLQ

This page was built for publication: Coin flipping of any constant bias implies one-way functions

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