Revisiting Waters: Tighter Adaptive IBEs and VRFs Analysis
Discover the groundbreaking contributions in adaptive IBEs and VRFs, including tighter proofs and partitioning-based reductions. Dive into the decisional security model with unique oracle initiations and explore the new advancements in achieving sublinear proof sizes.
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
Tighter Adaptive IBEs and VRFs: Revisiting Waters Artificial Abort Kei Kimura Kyushu Univresity Goichiro Hanaoka AIST Shuichi Katsumata AIST and PQShield Kaoru Takemure AIST and PQShield Shota Yamada AIST
Our Contributions New Analysis for Partitioning based proof Tighter Proof 2
Our Contributions New Analysis for Partitioning based proof Tighter Proof Improve reduction loss of Waters IBE[Wat05] and ABB IBE[ABB10] Propose new partitioning function for ABB IBE achieving tighter reduction Propose first VRF achieving sublinear vk and proof sizes under the standard d-LIN assumption 2
Partitioning-based Reduction 3
Decisional Security Model with Oracle ??? Init: Generates ???,??? Adversary ? Challenger ? 4
Decisional Security Model with Oracle ??? Init: Generates ???,??? Oracle Query ?? Adversary ? Challenger ? 4
Decisional Security Model with Oracle ??? Init: Generates ???,??? Oracle Query Answer using ??? ?? ???? Adversary ? Challenger ? 4
Decisional Security Model with Oracle ??? Init: Generates ???,??? ? times Oracle Query Answer using ??? ?? ???? Adversary ? Challenger ? 4
Decisional Security Model with Oracle ??? Init: Generates ???,??? ? times Oracle Query Answer using ??? ?? ???? Adversary ? ? Challenger ? Challenge Query 4
Decisional Security Model with Oracle ??? Init: Generates ???,??? ? times Oracle Query Answer using ??? ?? ???? ? {0,1} Generates ? ???? from ? Adversary ? ? Challenger ? ? ???? Challenge Query 4
Decisional Security Model with Oracle ??? Init: Generates ???,??? ? times Oracle Query Answer using ??? ?? ???? ? {0,1} Generates ? ???? from ? Adversary ? ? Challenger ? ? ???? Challenge Query ? ? wins if ? = ? 4
Decisional Security Model with Oracle ??? Init: Generates ???,??? ? times Oracle Query Answer using ??? ?? ???? ? {0,1} Generates ? ???? from ? Adversary ? ? Challenger ? ? ???? Challenge Query Prob. ?? ??= ?? 1 ? ? wins if ? = ? 2 4
Partitioning Technique Space of ? is divided into two sets ?0 and ?1 by using a function ?:? {0,1} Query Space ? 5
Partitioning Technique Space of ? is divided into two sets ?0 and ?1 by using a function ?:? {0,1} Query Space ? ?0= ? ? ? = 0 ?1= {?|? ? = 1} 5
Partitioning Technique Space of ? is divided into two sets ?0 and ?1 by using a function ?:? {0,1} Query Space ? ? times ?? If ? ?? = 0, can simulate ???? ?0= ? ? ? = 0 ? ? ???? ?1= {?|? ? = 1} 5
Partitioning Technique Space of ? is divided into two sets ?0 and ?1 by using a function ?:? {0,1} Query Space ? ? times ?? If ? ?? = 0, can simulate ???? ?0= ? ? ? = 0 If ? ? = 1, can embed the problem instance ? ? ???? ?1= {?|? ? = 1} 5
Partitioning Technique Space of ? is divided into two sets ?0 and ?1 by using a function ?:? {0,1} Query Space ? ? times ?? If ? ?? = 0, can simulate ???? ?0= ? ? ? = 0 If ? ? = 1, can embed the problem instance ? ? ???? ?1= {?|? ? = 1} If abort, outputs a random bit 5
Partitioning Technique Space of ? is divided into two sets ?0 and ?1 by using a function ?:? {0,1} Query Space ? ? times ?? If ? ?? = 0, can simulate ???? ?0= ? ? ? = 0 If ? ? = 1, can embed the problem instance ? ? ???? ?1= {?|? ? = 1} Now can we complete the proof? No 5
Advantage of Reduction ? = (?1, ,??,? ) 1 2 1 ?? ? ? ? ??? + 1 ? ? ??? ?? ? ?? ???? 1 ? masks queries ? ? = 2 = 2 ? wins Not Abort Conditioned on ? 6
Advantage of Reduction ? = (?1, ,??,? ) 1 2 1 ? = ?? ? ? ? ??? + 1 ? ? ??? ?? ? ?? ???? 1 2 = 2 Winning prob. of in no-abort case Winning prob. of in abort case Conditioned on ? 7
Advantage of Reduction ? = (?1, ,??,? ) No abort Abort 1 2 1 ? = ?? ? ? ? ??? + 1 ? ? ?? ? ? ? ??? 1 2 = 2 1 2,1 Conditioned on ? 2, so ?? may be negligible! 7
Artificial Abort [Wat05] introduced the artificial abort technique ? Outputs ? Adversary ? 8
Artificial Abort [Wat05] introduced the artificial abort technique Sampling ? many times Estimate ? ? by Monte Carlo method Abort with pro. 1 ????/?(?) ? Lower bound of ?(?) Outputs ? Adversary ? 8
Artificial Abort [Wat05] introduced the artificial abort technique Sampling ? many times Estimate ? ? by Monte Carlo method Abort with pro. 1 ????/?(?) ? Lower bound of ?(?) Outputs ? Adversary ? Abort No abort Artificial Abort ?? ? ? ? ???? ??? + ? ? 1 ???? 1 2+ 1 ? ? 1 2 1 ? = ? ? ? ? 2 8
Artificial Abort [Wat05] introduced the artificial abort technique Sampling ? many times Estimate ? ? by Monte Carlo method Abort with pro. 1 ????/?(?) ? Lower bound of ?(?) Outputs ? Adversary ? Abort No abort Artificial Abort ?? ? ? ? ???? = ???? ?? ??? + ? ? 1 ???? 1 2+ 1 ? ? 1 2 1 ? = ? ? ? ? 2 Non-negligible 8
Artificial Abort [Wat05] introduced the artificial abort technique Expensive Computation Estimate ? ? by Monte Carlo method Abort with pro. 1 ????/?(?) ? Lower bound of ?(?) Outputs ? Adversary ? Abort No abort Artificial Abort ?? ? ? ? ???? = ???? ?? ??? + ? ? 1 ???? 1 2+ 1 ? ? 1 2 1 ? = ? ? ? ? 2 Non-negligible 8
Artificial Abort [Wat05] introduced the artificial abort technique Estimate ?(?) Abort with pro. 1 ????/?(?) ? Lower bound of ?(?) Is there another analysis which can achieve smaller reduction Outputs ? Adversary ? loss? Sim fail Not abort Artificial Abort ?? ? ? ? ???? = ???? ?? ??? + ? ? 1 ???? 1 2+ 1 ? ? 1 2 1 ? = ? ? ? ? 2 Non-negligible 9
Finer Grained Analysis ? Outputs ? Adversary ? 11
Finer Grained Analysis ? ? ? ? 1 ? Compute ?(?) s.t. Abort with pro. 1 ????/ ?(?) ? Outputs ? Adversary ? 11
Finer Grained Analysis ? ? ? ? 1 ? Compute ?(?) s.t. Abort with pro. 1 ????/ ?(?) ? Outputs ? Adversary ? Artificial Abort Abort No abort ?? ? ? ? ???? ??? + ? ? 1 ???? 1 2+ 1 ? ? 1 2 1 ? = ? ? ? ? 2 11
Finer Grained Analysis ? ? ? ? 1 ? Compute ?(?) s.t. Abort with pro. 1 ????/ ?(?) ? Outputs ? Adversary ? Artificial Abort Abort No abort ?? ? ? ? ???? ???? ?? 2? ??? + ? ? 1 ???? 1 2+ 1 ? ? 1 2 1 ? = ? ? ? ? 2 11
Finer Grained Analysis ? ? ? ? 1 ? Compute ?(?) s.t. Abort with pro. 1 ????/ ?(?) ? Outputs ? Adversary ? Artificial Abort Abort No abort ?? ? ? ? ???? ???? ?? 2? ??? + ? ? 1 ???? 1 2+ 1 ? ? 1 2 1 ? = ? ? ? ? 2 If ? ???, has non-negligible advantage ???? ??/3 11
How to Get ? ?? 3 < ???? ?? ? ? ? ? 1 <?? ? ? ? ? 3 3 12
How to Get ? ?? 3 < ???? ?? ? ? ? ? 1 <?? ? ? ? ? 3 3 Approximation Error 12
How to Get ? ?? 3 < ???? ?? ? ? ? ? 1 <?? ? ? ? ? 3 3 Approximation Error Let ? : ? ? = 0 and ?(?): ? ?? = 0 12
How to Get ? ?? 3 < ???? ?? ? ? ? ? 1 <?? ? ? ? ? 3 3 Approximation Error Let ? : ? ? = 0 and ?(?): ? ?? = 0 From union bound Previous Improvement [BR09]: Pr ? ?Pr ? ?? ? ? Pr ? 12
How to Get ? ?? 3 < ???? ?? ? ? ? ? 1 <?? ? ? ? ? 3 3 Approximation Error Let ? : ? ? = 0 and ?(?): ? ?? = 0 From union bound Previous Improvement [BR09]: Pr ? ?Pr ? ?? ? ? Pr ? ?(?) 12
How to Get ? ?? 3 < ???? ?? ? ? ? ? 1 <?? ? ? ? ? 3 3 Approximation Error Let ? : ? ? = 0 and ?(?): ? ?? = 0 From union bound Previous Improvement [BR09]: ?Pr ? ?? ?(?) ? ? ?(?) Approximation Error!! 13
How to Get ? ?? 3 < ???? ?? ? ? ? ? 1 <?? ? ? ? ? 3 3 Approximation Error Let ? : ? ? = 0 and ?(?): ? ?? = 0 From Bonferroni s Inequality This work: Pr ? ?Pr ? ?? ? ? Pr ? ?Pr ? ?? ? ?Pr[? ?? ?(?)] + 14
How to Get ? ?? 3 < ???? ?? ? ? ? ? 1 <?? ? ? ? ? 3 3 Approximation Error Let ? : ? ? = 0 and ?(?): ? ?? = 0 From Bonferroni s Inequality This work: Pr ? ?Pr ? ?? ? ? Pr ? ?Pr ? ?? ? ?Pr[? ?? ?(?)] + ?(?) 14
How to Get ? ?? 3 < ???? ?? ? ? ? ? 1 <?? ? ? ? ? 3 3 Approximation Error Let ? : ? ? = 0 and ?(?): ? ?? = 0 This work: ? ?Pr[? ?? ?(?)] ?(?) ? ? ?(?) + Approximation Error!! 15
How to Get ? ?? 3 Approximation Error ? ?Pr[? ?? ?(?)] ?(?) ? ? ?(?) + 16
How to Get ? ?? 3 Approximation Error ? ?Pr[? ?? ?(?)] ?(?) ? ? ?(?) + We show this term is less than ???? ?? 3 16
How to Get ? ?? 3 Approximation Error ? ?Pr[? ?? ?(?)] ?(?) ? ? ?(?) + We show this term is less than ???? ?? 3 For Waters IBE, we can set parameters so that ????= ?( ??/?) 16
How to Get ? ?? 3 Approximation Error ? ?Pr[? ?? ?(?)] ?(?) ? ? ?(?) + We show this term is less than ???? ?? 3 For Waters IBE, we can set parameters so that ????= ?( ??/?) [BR09] sets ????= ?(??/?) 16
How to Get ? ?? 3 Approximation Error ? ?Pr[? ?? ?(?)] ?(?) ? ? ?(?) + Can we compute efficiently? We show this term is less than ???? ?? 3 For Waters IBE, we can set parameters so that ????= ?( ??/?) [BR09] sets ????= ?(??/?) 16
How to Get ? ?? 3 Approximation Error ? ?Pr[? ?? ?(?)] ?(?) ? ? ?(?) + Can we compute efficiently? We show this term is less than ???? ?? 3 Yes!! Waters IBE: ABB IBE, VRF: d-wise independent hash For Waters IBE, we can set parameters so that ????= ?( ??/?) Generating functions [BR09] sets ????= ?(??/?) 16
How to Get ? ?? 3 Approximation Error ? ?Pr[? ?? ?(?)] ?(?) ? ? ?(?) + Can we compute efficiently? We show this term is less than ???? ?? 3 Yes!! Waters IBE: ABB IBE, VRF: d-wise independent hash For Waters IBE, we can set parameters so that ????= ?( ??/?) Generating functions [BR09] sets ????= ?(??/?) We can improve reduction loss!! 16
Thank you for your attention! https://eprint.iacr.org/2024/1481
