Lower Bounds and Reductions in Geometric Search Problems
Explore lower bounds and reductions in geometric search problems, featuring the generic group model, GGM hardness, and transfer bounds via algebraic group models. Learn about extensions to preprocessing bounds and the technical overview of these concepts for problem-solving.
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
Generic-Group Lower Bounds via Reductions Between Geometric-Search Problems: With and Without Preprocessing Benedikt Auerbach, Charlotte Hoffmann, Guillermo Pascual-Perez Institute of Science and Technology Austria
Hardness of Assumptions in Groups ?? ? ? 2
The Generic Group Model ? ? 3
Shoups Generic Group Model [Sho97] ?:? 0,1 ? 1 ,?(?) ? ?? Maurer s Generic Group Model: No labels, abstract handles instead 4
GGM Hardness Lower Bounds Prove lower bounds on group operations required to solve a problem ?? Shoup s GGM can be extended to preprocessing bounds [CK17,CDG18] ?:? 0,1 ? ? ?? ? Transfer lower bounds between problems via reductions 5
Transfer bounds via Algebraic Group Model [FKL18] algebraic ?,??,?? Our Contribution ? Problem A Problem B New technique to transfer GGM lower bounds that is usable in Shoup's GGM; compatible with preprocessing bounds. GGM lower bound simple reductions need: any generic adversary is algebraic -- only formally proven in Maurer s GGM [FKL18, ZZK22, Zha22] not compatible with preprocessing bounds ?? ?,?,? ? = ?? + ?? + ? 6
Reduction via Geometric Search Problems preprocessing AGM GGM BF-GGM [CDG18] Problem A Problem B CDH geometric problems [Yun15] Geo-A Geo-DL Geo-B Geo-CDH information-theoretic lower bound 8
Geo-CDH ? ? 2 ?? ?,? $ ? (?,?) In Paper 4? 5? = 0? ? + 4 = 0? 3? + 2? + 8 = 0? define geometric versions of (Multi-Instance) Uber problems prove analogous lemma (in GGM and BF-GGM) can be used in future work 0 1 ? 2? ? 3 ? wins iff XY (2? ? 3) has ? as root. Lemma: Geo-CDH CDH GGM line queries used to consistently simulate GGM oracle output corresponds to target group element 9
Reduction via Geometric Search Problems GGM Problem B geometric problems Geo-A Geo-B information theoretic lower bound 10
Geo-A Geo-B Observation: Many AGM reductions have natural analogue for geometric problems. In Paper Reductions between geometric versions of ?DL Uber (similar to AGM reduction of [BFL20]) ?DL ?DHI (m, m)-MI-gap-DL (m, n)-MI-gap-CDH (similar to [AGK20]) 2DL BLS signatures (similar to [FKL18]) 11
Reduction via Geometric Search Problems GGM Problem B CDH geometric problems Geo-A Geo-DL Geo-B Geo-CDH information theoretic lower bound 12
Summary We present new technique to transfer (preprocessing) lower bounds in the GGM. We give new preprocessing lower bounds for several problems. Open problems: Adapt technique for decisional problems. Extend BF-GGM [CDG18] to decisional oracles and bilinear groups. Questions? 13
