2 Search Results for "Farshim, Pooya"

Document
DOI: 10.4230/LIPIcs.FUN.2022.2
A Practical Algorithm for Chess Unwinnability

Authors: Miguel Ambrona

Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)

Abstract
The FIDE Laws of Chess establish that if a player runs out of time during a game, they lose unless there exists no sequence of legal moves that ends in a checkmate by their opponent, in which case the game is drawn. The problem of determining whether or not a given chess position is unwinnable for a certain player has been considered intractable by the community and, consequently, chess servers do not apply the above rule rigorously, thus unfairly classifying many games. We propose, to the best of our knowledge, the first algorithm for chess unwinnability that is sound, complete and efficient for practical use. We also develop a prototype implementation and evaluate it over the entire Lichess Database (containing more than 3 billion games), successfully identifying all unfairly classified games in the database.
Cite as

Miguel Ambrona. A Practical Algorithm for Chess Unwinnability. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 2:1-2:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{ambrona:LIPIcs.FUN.2022.2,
  author =	{Ambrona, Miguel},
  title =	{{A Practical Algorithm for Chess Unwinnability}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{2:1--2:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-232-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{226},
  editor =	{Fraigniaud, Pierre and Uno, Yushi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.2},
  URN =		{urn:nbn:de:0030-drops-159721},
  doi =		{10.4230/LIPIcs.FUN.2022.2},
  annote =	{Keywords: chess, helpmate, unwinnability, timeout, dead position}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2021.47
Black-Box Uselessness: Composing Separations in Cryptography

Authors: Geoffroy Couteau, Pooya Farshim, and Mohammad Mahmoody

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract
Black-box separations have been successfully used to identify the limits of a powerful set of tools in cryptography, namely those of black-box reductions. They allow proving that a large set of techniques are not capable of basing one primitive 𝒫 on another 𝒬. Such separations, however, do not say anything about the power of the combination of primitives 𝒬₁,𝒬₂ for constructing 𝒫, even if 𝒫 cannot be based on 𝒬₁ or 𝒬₂ alone. By introducing and formalizing the notion of black-box uselessness, we develop a framework that allows us to make such conclusions. At an informal level, we call primitive 𝒬 black-box useless (BBU) for 𝒫 if 𝒬 cannot help constructing 𝒫 in a black-box way, even in the presence of another primitive 𝒵. This is formalized by saying that 𝒬 is BBU for 𝒫 if for any auxiliary primitive 𝒵, whenever there exists a black-box construction of 𝒫 from (𝒬,𝒵), then there must already also exist a black-box construction of 𝒫 from 𝒵 alone. We also formalize various other notions of black-box uselessness, and consider in particular the setting of efficient black-box constructions when the number of queries to 𝒬 is below a threshold. Impagliazzo and Rudich (STOC'89) initiated the study of black-box separations by separating key agreement from one-way functions. We prove a number of initial results in this direction, which indicate that one-way functions are perhaps also black-box useless for key agreement. In particular, we show that OWFs are black-box useless in any construction of key agreement in either of the following settings: (1) the key agreement has perfect correctness and one of the parties calls the OWF a constant number of times; (2) the key agreement consists of a single round of interaction (as in Merkle-type protocols). We conjecture that OWFs are indeed black-box useless for general key agreement. We also show that certain techniques for proving black-box separations can be lifted to the uselessness regime. In particular, we show that the lower bounds of Canetti, Kalai, and Paneth (TCC'15) as well as Garg, Mahmoody, and Mohammed (Crypto'17 & TCC'17) for assumptions behind indistinguishability obfuscation (IO) can be extended to derive black-box uselessness of a variety of primitives for obtaining (approximately correct) IO. These results follow the so-called "compiling out" technique, which we prove to imply black-box uselessness. Eventually, we study the complementary landscape of black-box uselessness, namely black-box helpfulness. We put forth the conjecture that one-way functions are black-box helpful for building collision-resistant hash functions. We define two natural relaxations of this conjecture, and prove that both of these conjectures are implied by a natural conjecture regarding random permutations equipped with a collision finder oracle, as defined by Simon (Eurocrypt'98). This conjecture may also be of interest in other contexts, such as amplification of hardness.
Cite as

Geoffroy Couteau, Pooya Farshim, and Mohammad Mahmoody. Black-Box Uselessness: Composing Separations in Cryptography. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 47:1-47:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{couteau_et_al:LIPIcs.ITCS.2021.47,
  author =	{Couteau, Geoffroy and Farshim, Pooya and Mahmoody, Mohammad},
  title =	{{Black-Box Uselessness: Composing Separations in Cryptography}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{47:1--47:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.47},
  URN =		{urn:nbn:de:0030-drops-135869},
  doi =		{10.4230/LIPIcs.ITCS.2021.47},
  annote =	{Keywords: Black-Box Reductions, Separations, One-Way Functions, Key Agreement}
}
  • Refine by Author
  • 1 Ambrona, Miguel
  • 1 Couteau, Geoffroy
  • 1 Farshim, Pooya
  • 1 Mahmoody, Mohammad

  • Refine by Classification
  • 1 Software and its engineering → Software libraries and repositories
  • 1 Theory of computation → Computational complexity and cryptography
  • 1 Theory of computation → Design and analysis of algorithms

  • Refine by Keyword
  • 1 Black-Box Reductions
  • 1 Key Agreement
  • 1 One-Way Functions
  • 1 Separations
  • 1 chess
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2021
  • 1 2022

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