Paper 2023/673

Tracing Quantum State Distinguishers via Backtracking

Mark Zhandry, NTT Research
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.