Cryptographic Groups and Ideal Models Overview
Explore AGMOS, ideal models, and criticisms in the realm of cryptographic groups. Understand the significance of oblivious sampling and spurious knowledge assumptions in cryptographic design.
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
AGMOS: Algebraic Group Model with Oblivious Sampling Helger Lipmaa Roberto Parisella Janno Siim
Cryptographic Groups Bracket notation for additive groups ? = ? , ? ?: ? = ? 1 (= ? ?), ? 1 , Hardness assumptions 1. ? 1,? is hard (DL assumption) 2. ? ? 1,?,? is hard (CDH assumption) 3. ? 1,?,?2, ,??is hard (?-PDL assumption) 2
Ideal models for Cryptographic Groups ? [?] GGM: generic group model [?] [?] Perfect unstructured group. Group elements are perfect encryptions of the exponent. 3
GGM Criticisms Un-instantiability results Does not capture group-specific algorithms Reductions can always program group elements, with random known exponents
Ideal Models for Cryptographic Groups [?, ,?] AGM: algebraic group model [FKL18] [?] ?,?,? [?] = ? ? + ? + ?[?] Adversaries provide a linear representation of their outputs, with respect to the group element they received on input 5
AGM Advantages Capture some known group-specific algorithms Proofs by reductions and Criticisms Un-instantiability result. Unclear relation between GGM and AGM Knowledge assumptions secure in AGM but not in the standard model.
Oblivious Sampling Sample group elements without knowing their DL. ? ?, ? superpolynomial min-entropy ??? ? = [?] DL on ???(?) is as hard as DL. Pr ??? ? = ? Example: encodings on elliptic curves ? ?,? ? 1 ,? ] 0
Spurious Knowledge Assumptions: example Extractor 1 ? ? 1 ? Used by reductions Hold in AGM (and GGM) Not hold in the standard model: 1. ? $ ? 2. ? = ???(?) If DL holds, no extractor can compute ?
Spurious Knowledge Assumptions: KZG 1,?,?2, ,?? ?(?) ? 1,?,?2, ,?? ?0,?1, ,?? ?(?) = ???? PLONK, Lunar: SNARKs with security proof based on this assumption
AGMOS: AGM with Oblivious Sampling Non-programmable oracle [?, ,?] ?,? ? ,s 1. ? $ ? 2. ? = ?(?) [?] ?,?,? ,?:? = ? ? + ? + ? ? + ?[?] Reduction does not know ?
Example: CDH AGMOS adversary ?,? $ ? [1,?,?] ?? ,?? ? ??,?? 1. ?? $ ?? 2. ?? = ?(??) ??,?? ? ,?,?,?, ? Adversary wins if ? = ? ? Algebraic adversary ? = ? 1 + ? ? + ?[?] + ????
Example: CDH holds in AGMOS Implicit verification polynomial ? ?,?,? = ? + ?? + ?? + ???? XY If adversary breaks CDH then ? ?,?, ? = 0 ? = ? ? ? = ? 1 + ? ? + ?[?] + ???? Case 1: ? ?,?,? 0 impossible Case2 : ? ?,?,? 0, but ? ?,?,? 0 successful reduction to DL Case 3: ? ?,?,? 0 Successful reduction to new TOFR assumption
,? -Tensor Oracle FindRep Assumption For a family of functions and a family of distributions ? the ( ,?)- TOFR assumption holds if for each PPT ? ?? ,?? ? ??,?? 1. ?? $ ?? 2. ?? = ?(??) ??,?? ? Pr ?01 + ????= 0 0
Thanks for your attention Check the full version on e-print https://eprint.iacr.org/2023/1504 Questions?
Cryptanalysis of TOFR A necessary condition for security in GGM ? is a family of distributions with superpolynomial min-entropy Relation to simpler and well-studied Find-Rep assumption TOFR security proof is independent from the model definition and proof framework And Open Problems Necessary and sufficient conditions on ,? for security of ,? - TOFR. Precise relation between AGM and AGMOS
