{"ID":2872386,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.09896","arxiv_id":"2509.09896","title":"Improved Quantum Lifting by Coherent Measure-and-Reprogram","abstract":"We give a tighter lifting theorem for security games in the quantum random oracle model. At the core of our main result lies a novel measure-and-reprogram framework that we call coherent reprogramming. This framework gives a tighter lifting theorem for query complexity problems, that only requires purely classical reasoning. As direct applications of our lifting theorem, we first provide a quantum direct product theorem in the average case - i.e., an enabling tool to determine the hardness of solving multi-instance security games. This allows us to derive in a straightforward manner the hardness of various security games, for example (i) the non-uniform hardness of salted games, (ii) the hardness of specific cryptographic tasks such as the multiple instance version of one-wayness and collision-resistance, and (iii) uniform or non-uniform hardness of many other games.","short_abstract":"We give a tighter lifting theorem for security games in the quantum random oracle model. At the core of our main result lies a novel measure-and-reprogram framework that we call coherent reprogramming. This framework gives a tighter lifting theorem for query complexity problems, that only requires purely classical reas...","url_abs":"https://arxiv.org/abs/2509.09896","url_pdf":"https://arxiv.org/pdf/2509.09896v1","authors":"[\"Alexandru Cojocaru\",\"Juan Garay\",\"Qipeng Liu\",\"Fang Song\"]","published":"2025-09-11T23:15:13Z","proceeding":"quant-ph","tasks":"[\"quant-ph\",\"cs.CC\",\"cs.CR\"]","methods":"[]","has_code":false}