Fixing Cracks in the ROM: Unruh07, DGK17, CDGS17 Research Insights
Explore the research on fixing cracks in the ROM by Unruh, DGK, and CDGS in the context of non-uniform attacks. Learn how security bounds are improved against various attackers in the ROM environment, offering solutions to protect against practical threats in cryptographic systems.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Non Non- -uniformity, quantum advice, uniformity, quantum advice, and quantum random oracle and quantum random oracle Eurocrypt 2023 Qipeng Liu Simons Institute for the Theory of Computing https://eprint.iacr.org/2022/1384 presented by Takashi Yamakawa
(Informal) Grovers search can not be sped up, (Informal) Grover s search can not be sped up, even with quantum advice even with quantum advice (Informal) Salting defeats non (Informal) Salting defeats non- -uniform attacks, even with quantum advice even with quantum advice uniform attacks,
Cryptographic Hash A function ? that outputs a digest (of ? bits, ? = 2?) Public, known to everyone Satisfy desired properties for different crypto applications Collision Resistance One-wayness/Proof of work Other ideal properties message ? digest
Random Oracle Methodology Bellare-Rogaway 93 ?: ? ? is a uniformly random function Random oracle methodology (heuristics): For most of ``natural applications of hash functions ?? OWFs: ? ?(?) security in practice ? security in the ROM PRGs: 1 2+? ? for the best possible instantiation of ? CRHFs: ?2 ``Plus for ROM: simple proofs, precise bounds ?
Cracks in the ROM Unruh07, DGK17, CDGS17 Unruh07, DGK17, CDGS17 Mismatch between ROM and practical attacks (with preprocessing) ROM Practical Attacks ?2 ? CRHF 1 (by hardcode a collision) 1/3 ? ? ?2? ?2 ?? ?+ OWF (rainbow table) [Hellman 80, Oechslin 03]
Fixing Cracks Unruh07, DGK17, CDGS17 Unruh07, DGK17, CDGS17 Can we save the beautiful ROM from non- uniform attacks? YES! Unruh Guo Katz Coretti Steinberger Dodis
Fixing Cracks Unruh07, DGK17, CDGS17 Unruh07, DGK17, CDGS17 ROM: ?: ? [?] (Two-stage) non-uniform attackers ?1,?2 ?1 is unbounded produces bounded (oracle-dependent) advice ? ? ?1 ?(?, ) is bounded Parameters ?,? Cracks fixed! Security bounds in the ROM, against (?,?) attackers ?2 ? ? ?2
Fixing Cracks Unruh07, DGK17, CDGS17 Unruh07, DGK17, CDGS17 CDGS17: salting ``generically defeats preprocessing attacks Salting is needed Non-uniform security in the ROM Practical Attacks 1 CRHF 1 (by hardcode a collision) 1/3 ?? ? ?2? ?2 ?? ?+ OWF (rainbow table) [Hellman 80, Oechslin 03] Barriers for filling the gap, [Corrigan-Gibbs, Kogan 18]
01101 01101 0100 01101 01001 01000 01101 11111 11101 010011 11101 01111
Non-Uniform Quantum Attacks NABT15, CG NABT15, CGL LQ20, GL Q20, GLL LZ20 Z20 ?: ? [?] (Two-stage) non-uniform attackers ?1,?2 ?1 produces bounded (oracle-dependent) advice ? Classical or quantum advice ? is unbounded ? ?1 ? |? (?, ) is bounded (? queries) ?2 |? ?2 01001
Non-Uniform Security Upper bound (algorithms) Upper bound (algorithms) OWFs: With S bits of advice ?, being the rainbow table, Run the rainbow table algorithm with ? Or, run the Grover s search without advice ?+?2? ?2+?2 Advantage is ?? ? Does advice help quantum algorithms? Rainbow table Grover s
Non-Uniform Security NABT15, CG NABT15, CGL LQ20, GL Q20, GLL LZ20 Z20 CGLQ20 classical advice ?? + ?2 ? CGLQ20 quantum advice 1/3 OWFs ?? + ?2 ? 1/3 1/19 PRGs ?? ?+?2 ?5? ? +?4?2 1 2+ 1 2+ ? ? Salting defeats preprocessing ``somewhat defeats preprocessing
Does quantum quantum advice really help?
Our Results Our Results
Non-Uniform Security CGLQ20 classical advice ?? + ?2 ? CGLQ20 This Work quantum advice ?? + ?2 ? quantum advice 1/3 OWFs ?? + ?2 ? 1/3 1/19 1/3 PRGs ?? ?+?2 ?? ?+?2 ?5? ? +?4?2 1 2+ 1 2+ 1 2+ ? ? ? Salting defeats preprocessing ``somewhat defeats preprocessing defeats preprocessing
Main Ideas ? ? ?(??) ? ? Inspired by [MW05] Non-uniform for the multi-instance game: Given non-uniform (classical advice ?) ? w.p. ?, For each ? [?]: Run ???,? ?? Alternating measurement game: Challenger has ? (a quantum state) over system ? Appends +? ?|? to ? For each ? [?]: If ? is odd, measures ?? on ( 0, 1) If ? is even, measures ?? on (IsU0,IsU1) Adversary wins iff ?1= ?? 1= ??= 0 achieves a probability ?? Does not work when ? is quantum! Outputting ?? may destroy ?.
Takeaways Takeaways (informal) For many natural security games based on hash functions, BQP/poly and BQP/qpoly adversaries achieve the same power (generically) Salting defeats any preprocessing attacks For a certain contrived game and ? = 0, quantum advice is exponentially better. Based on a recent work by [Yamakawa, Zhandry22]
Subsequent Work Subsequent Work Does quantum advice have more power than classical advice? BQP/poly BQP/qpoly? [Aaronson, Kuperberg07]: Separation relative to quantum oracles Open: Separation relative to (quantumly-accessible) classical oracles? [Li, Liu, Pelecanos, Yamakawa23]: Separation relative to classically-accessibleclassical oracles Also separate QMA and QCMA Based on the contrived separation in the case of T=0 in this work.
Thank you! Thank you! https://eprint.iacr.org/2022/1384
