BEGIN:VCALENDAR PRODID:-//AddEvent Inc//AddEvent.com v1.7//EN VERSION:2.0 BEGIN:VTIMEZONE TZID:America/New_York BEGIN:STANDARD DTSTART:20261101T010000 RRULE:FREQ=YEARLY;BYDAY=1SU;BYMONTH=11 TZOFFSETFROM:-0400 TZOFFSETTO:-0500 TZNAME:EST END:STANDARD BEGIN:DAYLIGHT DTSTART:20260308T030000 RRULE:FREQ=YEARLY;BYDAY=2SU;BYMONTH=3 TZOFFSETFROM:-0500 TZOFFSETTO:-0400 TZNAME:EDT END:DAYLIGHT END:VTIMEZONE BEGIN:VEVENT DESCRIPTION:Lower Bounds for Preprocessing Attacks on Quantum Cryptography\nFangqi Dong | Princeton\nWe prove near-optimal lower bounds for preprocessing attacks on quantum cryptography in the random oracle model. Specifically\, we show that a T-query adversary with S qubits of non-uniform advice can recover a random key k from the n-qubit binary phase state |ψk⟩∝∑xR(k\,x)|x⟩ with probability at most O(T2+ST√N) for N=2n. In contrast\, the best known bound for post-quantum one-way functions is O(T2+STN)\, with a trivial attack at S=N. This demonstrates a new advantage of quantum cryptography over classical cryptography: n qubits of communication suffice for security against preprocessing attacks with space up to N2 rather than N. Our methodology is simple: express the optimal preprocessing attack as the operator norm of a random matrix\, and bound this value in expectation over the random oracle via the trace-moment method. These trace moments have a natural interpretation using compressed oracles [Zhandry\, Crypto 2019]\, which we then analyze. This can be viewed as a simplification and generalization of the approach of Liu [Eurocrypt 2023] for proving the security of post-quantum cryptography against preprocessing attacks. We also prove the following results: (1) We tighten Liu's analysis of post-quantum PRGs in QROM\, achieving a distinguishing advantage bound of O(T2N+STN‾‾‾√). (2) For unitary synthesis\, we extend the one-query lower bound of Lombardi-Ma-Wright [STOC 2024] to hold against adversaries that can make one arbitrary function query along with polynomially many (adaptive) queries to the random oracle\, either before or after the function query. This also interprets the original LMW24 result in terms of compressed oracles. (3) Finally\, we prove a tight O(S√N) bound for the pseudorandomness of random binary phase states against space S distinguishers.\n\n• QNC 1201\n• Online on ZoomMeeting ID: 912 8146 6256 \nPasscode: 494237\n\n X-ALT-DESC;FMTTYPE=text/html:Lower Bounds for Preprocessing Attacks on Quantum Cryptography
Fangqi Dong | Princeton
We prove near-optimal lower bounds for preprocessing attacks on quantum cryptography in the random oracle model. Specifically, we show that a T-query adversary with S qubits of non-uniform advice can recover a random key k from the n-qubit binary phase state |ψk⟩∝∑xR(k,x)|x⟩ with probability at most O(T2+ST√N) for N=2n. In contrast, the best known bound for post-quantum one-way functions is O(T2+STN), with a trivial attack at S=N. This demonstrates a new advantage of quantum cryptography over classical cryptography: n qubits of communication suffice for security against preprocessing attacks with space up to N2 rather than N. Our methodology is simple: express the optimal preprocessing attack as the operator norm of a random matrix, and bound this value in expectation over the random oracle via the trace-moment method. These trace moments have a natural interpretation using compressed oracles [Zhandry, Crypto 2019], which we then analyze. This can be viewed as a simplification and generalization of the approach of Liu [Eurocrypt 2023] for proving the security of post-quantum cryptography against preprocessing attacks. We also prove the following results: (1) We tighten Liu's analysis of post-quantum PRGs in QROM, achieving a distinguishing advantage bound of O(T2N+STN‾‾‾√). (2) For unitary synthesis, we extend the one-query lower bound of Lombardi-Ma-Wright [STOC 2024] to hold against adversaries that can make one arbitrary function query along with polynomially many (adaptive) queries to the random oracle, either before or after the function query. This also interprets the original LMW24 result in terms of compressed oracles. (3) Finally, we prove a tight O(S√N) bound for the pseudorandomness of random binary phase states against space S distinguishers.
UID:a93f0f6988964ee5a118db0b60587020addeventcom SUMMARY:IQC Math and CS seminar featuring Fangqi Dong DTSTART;TZID=America/New_York:20261126T130000 DTEND;TZID=America/New_York:20261126T140000 DTSTAMP:20261102T232156Z TRANSP:OPAQUE STATUS:CONFIRMED SEQUENCE:0 LOCATION:QNC 1201 X-MICROSOFT-CDO-BUSYSTATUS:BUSY BEGIN:VALARM TRIGGER:-PT30M ACTION:DISPLAY DESCRIPTION:Reminder END:VALARM END:VEVENT END:VCALENDAR