Document Open Access Logo

On Oblivious Amplification of Coin-Tossing Protocols

Authors Nir Bitansky, Nathan Geier

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2020.30.pdf
  • Filesize: 484 kB
  • 13 pages

Document Identifiers

Author Details

Nir Bitansky
  • Tel Aviv University, Israel
Nathan Geier
  • Tel Aviv University, Israel

Funding

This work was supported in part by ISF grant 18/484, and by Len Blavatnik and the Blavatnik Family Foundation.
  • Bitansky, Nir: Supported by the Alon Young Faculty Fellowship.

Acknowledgements

We thank Itay Sason for helpful discussions.

Cite AsGet BibTex

Nir Bitansky and Nathan Geier. On Oblivious Amplification of Coin-Tossing Protocols. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 30:1-30:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ITCS.2020.30

Abstract

We consider the problem of amplifying two-party coin-tossing protocols: given a protocol where it is possible to bias the common output by at most ρ, we aim to obtain a new protocol where the output can be biased by at most ρ* < ρ. We rule out the existence of a natural type of amplifiers called oblivious amplifiers for every ρ* < ρ. Such amplifiers ignore the way that the underlying ρ-bias protocol works and can only invoke an oracle that provides ρ-bias bits. We provide two proofs of this impossibility. The first is by a reduction to the impossibility of deterministic randomness extraction from Santha-Vazirani sources. The second is a direct proof that is more general and also rules outs certain types of asymmetric amplification. In addition, it gives yet another proof for the Santha-Vazirani impossibility.

Subject Classification

ACM Subject Classification
  • Theory of computation → Cryptographic protocols
  • Theory of computation → Oracles and decision trees
Keywords
  • Coin Tossing
  • Amplification
  • Lower Bound
  • Santha Vazirani

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Per Austrin, Kai-Min Chung, Mohammad Mahmoody, Rafael Pass, and Karn Seth. On the Impossibility of Cryptography with Tamperable Randomness. Algorithmica, 79(4):1052-1101, 2017. URL: https://doi.org/10.1007/s00453-016-0219-7.
  2. Itay Berman, Iftach Haitner, and Aris Tentes. Coin Flipping of Any Constant Bias Implies One-Way Functions. J. ACM, 65(3):14:1-14:95, 2018. URL: https://doi.org/10.1145/2979676.
  3. Manuel Blum. Coin Flipping by Telephone. In Allen Gersho, editor, Advances in Cryptology: A Report on CRYPTO 81, CRYPTO 81, IEEE Workshop on Communications Security, Santa Barbara, California, USA, August 24-26, 1981., pages 11-15. U. C. Santa Barbara, Dept. of Elec. and Computer Eng., ECE Report No 82-04, 1981. Google Scholar
  4. Ivan Damgård, Joe Kilian, and Louis Salvail. On the (Im)possibility of Basing Oblivious Transfer and Bit Commitment on Weakened Security Assumptions. In Jacques Stern, editor, Advances in Cryptology - EUROCRYPT '99, International Conference on the Theory and Application of Cryptographic Techniques, Prague, Czech Republic, May 2-6, 1999, Proceeding, volume 1592 of Lecture Notes in Computer Science, pages 56-73. Springer, 1999. URL: https://doi.org/10.1007/3-540-48910-X_5.
  5. Cynthia Dwork, Moni Naor, and Omer Reingold. Immunizing Encryption Schemes from Decryption Errors. In Christian Cachin and Jan Camenisch, editors, Advances in Cryptology - EUROCRYPT 2004, International Conference on the Theory and Applications of Cryptographic Techniques, Interlaken, Switzerland, May 2-6, 2004, Proceedings, volume 3027 of Lecture Notes in Computer Science, pages 342-360. Springer, 2004. URL: https://doi.org/10.1007/978-3-540-24676-3_21.
  6. Iftach Haitner. A Parallel Repetition Theorem for Any Interactive Argument. SIAM J. Comput., 42(6):2487-2501, 2013. URL: https://doi.org/10.1137/100810630.
  7. Iftach Haitner and Eran Omri. Coin Flipping with Constant Bias Implies One-Way Functions. SIAM J. Comput., 43(2):389-409, 2014. URL: https://doi.org/10.1137/120887631.
  8. Shai Halevi and Tal Rabin. Degradation and Amplification of Computational Hardness. In Ran Canetti, editor, Theory of Cryptography, Fifth Theory of Cryptography Conference, TCC 2008, New York, USA, March 19-21, 2008., volume 4948 of Lecture Notes in Computer Science, pages 626-643. Springer, 2008. URL: https://doi.org/10.1007/978-3-540-78524-8_34.
  9. Johan Håstad, Russell Impagliazzo, Leonid A. Levin, and Michael Luby. A Pseudorandom Generator from any One-way Function. SIAM J. Comput., 28(4):1364-1396, 1999. URL: https://doi.org/10.1137/S0097539793244708.
  10. Russell Impagliazzo and Michael Luby. One-way Functions are Essential for Complexity Based Cryptography (Extended Abstract). In 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October - 1 November 1989, pages 230-235. IEEE Computer Society, 1989. URL: https://doi.org/10.1109/SFCS.1989.63483.
  11. Huijia Lin and Stefano Tessaro. Amplification of Chosen-Ciphertext Security. In Thomas Johansson and Phong Q. Nguyen, editors, Advances in Cryptology - EUROCRYPT 2013, 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, May 26-30, 2013. Proceedings, volume 7881 of Lecture Notes in Computer Science, pages 503-519. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-38348-9_30.
  12. Hemanta K. Maji, Manoj Prabhakaran, and Amit Sahai. On the Computational Complexity of Coin Flipping. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pages 613-622. IEEE Computer Society, 2010. URL: https://doi.org/10.1109/FOCS.2010.64.
  13. Moni Naor. Bit Commitment Using Pseudorandomness. J. Cryptology, 4(2):151-158, 1991. URL: https://doi.org/10.1007/BF00196774.
  14. Omer Reingold, Salil Vadhan, and Avi Wigderson. A note on extracting randomness from Santha-Vazirani sources. Unpublished manuscript, 2004. Google Scholar
  15. Miklos Santha and Umesh V. Vazirani. Generating Quasi-random Sequences from Semi-random Sources. J. Comput. Syst. Sci., 33(1):75-87, 1986. URL: https://doi.org/10.1016/0022-0000(86)90044-9.
  16. Jürg Wullschleger. Oblivious-transfer amplification. PhD thesis, Universität Zürich, 2008. Google Scholar
  17. Andrew Chi-Chih Yao. Theory and Applications of Trapdoor Functions (Extended Abstract). In 23rd Annual Symposium on Foundations of Computer Science, Chicago, Illinois, USA, 3-5 November 1982, pages 80-91. IEEE Computer Society, 1982. URL: https://doi.org/10.1109/SFCS.1982.45.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact