Paper 2023/1832
A Note On the Universality of Black-box MKtP Solvers
Abstract
The relationships between various meta-complexity problems are not well understood in the worst-case regime, including whether the search version is harder than the decision version, whether the hardness scales with the ``threshold", and how the hardness of different meta complexity problems relate to one another, and to the task of function inversion.
In this note, we present resolutions to some of these questions with respect to the \emph{black-box} analog of these problems. In more detail, let
Metadata
- Available format(s)
-
PDF
- Publication info
- Published elsewhere. ECCC
- Contact author(s)
-
noammaz @ gmail com
rafaelp @ tau ac il - History
- 2023-12-01: approved
- 2023-11-29: received
- See all versions
- Short URL
- https://ia.cr/2023/1832
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/1832, author = {Noam Mazor and Rafael Pass}, title = {A Note On the Universality of Black-box {MKtP} Solvers}, howpublished = {Cryptology {ePrint} Archive, Paper 2023/1832}, year = {2023}, url = {https://eprint.iacr.org/2023/1832} }