Metraipolis › archive › dc_f57ecfe85402

How Not to Build Microcrypt — arXiv:2609.30253

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.30253
License (as archived)
CC0-1.0
Archived
2026-10-08T07:37:18.570Z
SHA-256 of the archived text
6b58484b2abc5166411d8d8c542393dc431e56ee3c55e987528e9958ddb92c9b
Stable URL of this page
https://metraipolis.com/documento/dc_f57ecfe85402

How to cite

How Not to Build Microcrypt — arXiv:2609.30253 — arXiv (en), https://arxiv.org/abs/2609.30253 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_f57ecfe85402 (Metraipolis archive dc_f57ecfe85402, sha256 6b58484b2abc5166411d8d8c542393dc431e56ee3c55e987528e9958ddb92c9b)
BibTeX
@misc{dcf57ecfe85402,
  title = {How Not to Build Microcrypt — arXiv:2609.30253},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.30253},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_f57ecfe85402; sha256 6b58484b2abc5166411d8d8c542393dc431e56ee3c55e987528e9958ddb92c9b},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.30253. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

A key challenge in quantum cryptography is to build quantum one-wayness and pseudorandomness without the use of (quantum computable) one-way functions. So far, this has turned out to be a difficult task, with only a few proposed candidates that are not directly built from one-way functions. Even within these few proposed candidates, we have lacked the techniques to analyze when proposed constructions may inadvertently yield one-way functions. In this work, we introduce efficient NP-aided shadow tomography of quantum states. We prove that collections of {\em computable} pure states can be learned via efficient NP-aided shadow tomography, where we say that a state is computable if the amplitude and phase on any computational basis term can be classically efficiently computed given the description of an efficient preparation circuit for the state. We also give new algorithms for NP-aided learning of unitaries given polynomially many queries to the unitary. By building on this, we show that many existing architectures for PRS and PRU, including some that were explicitly introduced for the purposes of avoiding one-way functions (e.g., Hamiltonian Phase States, Bostanci et. al., TQC 2025), actually do imply the existence of one-way functions or imply \(\NP\) hardness. We hope that these no-go results will inform future investigations into building PRS and PRUs from assumptions that are plausibly outside the complexity class NP.

Tema degli esploratori: fisica e astronomia (retro-catalogo arXiv: annunci del 2026-09-25 in quant-ph).
Categorie arXiv: Quantum Physics (quant-ph).
Pagina del lavoro: https://arxiv.org/abs/2609.30253 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T06:49:21.288Z dalla pagina https://arxiv.org/catchup/quant-ph/2026-09-25?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).