Paper 2023/673
Tracing Quantum State Distinguishers via Backtracking
Abstract
We show the following results: - The post-quantum equivalence of indistinguishability obfuscation and differing inputs obfuscation in the restricted setting where the outputs differ on at most a polynomial number of points. Our result handles the case where the auxiliary input may contain a quantum state; previous results could only handle classical auxiliary input. - Bounded collusion traitor tracing from general public key encryption, where the decoder is allowed to contain a quantum state. The parameters of the scheme grow polynomially in the collusion bound. - Collusion-resistant traitor tracing with constant-size ciphertexts from general public key encryption, again for quantum state decoders. The public key and secret keys grow polynomially in the number of users. - Traitor tracing with embedded identities in the keys, again for quantum state decoders, under a variety of different assumptions with different parameter size trade-offs. Traitor tracing and differing inputs obfuscation with quantum decoders / auxiliary input arises naturally when considering the post-quantum security of these primitives. We obtain our results by abstracting out a core algorithmic model, which we call the Back One Step (BOS) model. We prove a general theorem, reducing many quantum results including ours to designing classical algorithms in the BOS model. We then provide simple algorithms for the particular instances studied in this work.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- A major revision of an IACR publication in CRYPTO 2023
- Keywords
- quantumtraitor tracingobfuscation
- Contact author(s)
- mzhandry @ gmail com
- History
- 2023-05-11: approved
- 2023-05-11: received
- See all versions
- Short URL
- https://ia.cr/2023/673
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/673, author = {Mark Zhandry}, title = {Tracing Quantum State Distinguishers via Backtracking}, howpublished = {Cryptology {ePrint} Archive, Paper 2023/673}, year = {2023}, url = {https://eprint.iacr.org/2023/673} }