Paper 2014/458

Automated Analysis of Cryptographic Assumptions in Generic Group Models

Gilles Barthe, Edvard Fagerholm, Dario Fiore, John Mitchell, Andre Scedrov, and Benedikt Schmidt

Abstract

We initiate the study of principled, automated, methods for analyzing hardness assumptions in generic group models, following the approach of symbolic cryptography. We start by defining a broad class of generic and symbolic group models for different settings---symmetric or asymmetric (leveled) k-linear groups---and by proving "computational soundness" theorems for the symbolic models. Based on this result, we formulate a very general master theorem that formally relates the hardness of a (possibly interactive) assumption in these models to solving problems in polynomial algebra. Then, we systematically analyze these problems. We identify different classes of assumptions and obtain decidability and undecidability results. Then, we develop and implement automated procedures for verifying the conditions of master theorems, and thus the validity of hardness assumptions in generic group models. The concrete outcome of this work is an automated tool which takes as input the statement of an assumption, and outputs either a proof of its generic hardness or shows an algebraic attack against the assumption.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published by the IACR in CRYPTO 2014
Keywords
generic group modelmultilinear mapsgraded encoding schemesautomated cryptographic proofs
Contact author(s)
benedikt schmidt @ imdea org
History
2014-06-15: received
Short URL
https://ia.cr/2014/458
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/458,
      author = {Gilles Barthe and Edvard Fagerholm and Dario Fiore and John Mitchell and Andre Scedrov and Benedikt Schmidt},
      title = {Automated Analysis of Cryptographic Assumptions in Generic Group Models},
      howpublished = {Cryptology ePrint Archive, Paper 2014/458},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/458}},
      url = {https://eprint.iacr.org/2014/458}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.