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.
Category / Keywords: foundations / generic group model, multilinear maps, graded encoding schemes, automated cryptographic proofs Original Publication (in the same form): IACR-CRYPTO-2014 Date: received 13 Jun 2014 Contact author: benedikt schmidt at imdea org Available format(s): PDF | BibTeX Citation Version: 20140615:112122 (All versions of this report) Short URL: ia.cr/2014/458