{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,17]],"date-time":"2025-12-17T08:45:14Z","timestamp":1765961114617},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2018,12,18]],"date-time":"2018-12-18T00:00:00Z","timestamp":1545091200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptol"],"published-print":{"date-parts":[[2019,4]]},"DOI":"10.1007\/s00145-018-9302-3","type":"journal-article","created":{"date-parts":[[2018,12,18]],"date-time":"2018-12-18T15:41:15Z","timestamp":1545147675000},"page":"324-360","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Automated Analysis of Cryptographic Assumptions in Generic Group Models"],"prefix":"10.1007","volume":"32","author":[{"given":"Gilles","family":"Barthe","sequence":"first","affiliation":[]},{"given":"Edvard","family":"Fagerholm","sequence":"additional","affiliation":[]},{"given":"Dario","family":"Fiore","sequence":"additional","affiliation":[]},{"given":"John","family":"Mitchell","sequence":"additional","affiliation":[]},{"given":"Andre","family":"Scedrov","sequence":"additional","affiliation":[]},{"given":"Benedikt","family":"Schmidt","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,12,18]]},"reference":[{"issue":"3","key":"9302_CR1","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1007\/s00145-007-0203-0","volume":"20","author":"M Abadi","year":"2007","unstructured":"M.\u00a0Abadi, P.\u00a0Rogaway, Reconciling two views of cryptography (the computational soundness of formal encryption). J. Cryptol.\n                           20(3):395 (2007).","journal-title":"J. Cryptol."},{"key":"9302_CR2","doi-asserted-by":"crossref","unstructured":"M.\u00a0Abdalla, D.\u00a0Pointcheval, Interactive Diffie\u2013Hellman assumptions with applications to password-based authentication, in A.\u00a0Patrick, M.\u00a0Yung, editors, FC 2005, vol. 3570 of LNCS (Springer, 2005), pp. 341\u2013356","DOI":"10.1007\/11507840_31"},{"key":"9302_CR3","doi-asserted-by":"crossref","unstructured":"G.\u00a0Ateniese, J.\u00a0Camenisch, B.\u00a0de\u00a0Medeiros, Untraceable RFID tags via insubvertible encryption, in V.\u00a0Atluri, C.\u00a0Meadows, A.\u00a0Juels, editors, ACM CCS 05 (ACM Press, 2005), pp. 92\u2013101","DOI":"10.1145\/1102120.1102134"},{"key":"9302_CR4","doi-asserted-by":"crossref","unstructured":"C.\u00a0E.\u00a0Z. Baltico, D.\u00a0Catalano, D.\u00a0Fiore, R.\u00a0Gay, Practical functional encryption for quadratic functions with applications to predicate encryption, in Advances in Cryptology\u2014CRYPTO 2017 (2017).","DOI":"10.1007\/978-3-319-63688-7_3"},{"key":"9302_CR5","doi-asserted-by":"crossref","unstructured":"G.\u00a0Barthe, J.\u00a0Cederquist, S.\u00a0Tarento, A machine-checked formalization of the generic model and the random oracle model, in Automated Reasoning\u2014Second International Joint Conference, IJCAR 2004, Cork, Ireland, July 4\u20138, 2004, Proceedings, pp. 385\u2013399 (2004)","DOI":"10.1007\/978-3-540-25984-8_29"},{"key":"9302_CR6","doi-asserted-by":"crossref","unstructured":"G.\u00a0Barthe, E.\u00a0Fagerholm, D.\u00a0Fiore, A.\u00a0Scedrov, B.\u00a0Schmidt, M.\u00a0Tibouchi, Strongly-optimal structure preserving signatures from type ii pairings: Synthesis and lower bounds, in J.\u00a0Katz, editor, Public-Key Cryptography\u2014PKC 2015, vol. 9020 of LNCS (Springer, Berlin, 2015), pp. 355\u2013376","DOI":"10.1007\/978-3-662-46447-2_16"},{"key":"9302_CR7","unstructured":"G.\u00a0Barthe, S.\u00a0Tarento, A machine-checked formalization of the random oracle model, in Types for Proofs and Programs, International Workshop, TYPES 2004, Jouy-en-Josas, France, December 15\u201318, 2004, Revised Selected Papers (2004), pp. 33\u201349"},{"key":"9302_CR8","doi-asserted-by":"crossref","unstructured":"K.\u00a0Benson, H.\u00a0Shacham, B.\u00a0Waters, The k-BDH assumption family: Bilinear map cryptography from progressively weaker assumptions, in E.\u00a0Dawson, editor, CT-RSA\u00a02013, vol. 7779 of LNCS, (Springer, Feb.\u00a0\/\u00a0Mar. 2013), pp. 310\u2013325","DOI":"10.1007\/978-3-642-36095-4_20"},{"key":"9302_CR9","doi-asserted-by":"crossref","unstructured":"B.\u00a0Blanchet. Security protocol verification: Symbolic and computational models, in POST 2012, vol. 7215 of Lecture Notes in Computer Science (Springer, Heidelberg, 2012), pp. 3\u201329","DOI":"10.1007\/978-3-642-28641-4_2"},{"key":"9302_CR10","doi-asserted-by":"crossref","unstructured":"A.\u00a0Boldyreva, C.\u00a0Gentry, A.\u00a0O\u2019Neill, D.\u00a0H. Yum, Ordered multisignatures and identity-based sequential aggregate signatures, with applications to secure routing, in P.\u00a0Ning, S.\u00a0D.\u00a0C. di Vimercati, P.\u00a0F. Syverson, editors, ACM CCS 07 (ACM Press, 2007), pp. 276\u2013285","DOI":"10.1145\/1315245.1315280"},{"key":"9302_CR11","doi-asserted-by":"crossref","unstructured":"A.\u00a0Boldyreva, C.\u00a0Gentry, A.\u00a0O\u2019Neill, D.\u00a0H. Yum, Ordered multisignatures and identity-based sequential aggregate signatures, with applications to secure routing. Cryptology ePrint Archive, Report 2007\/438, revised 21 Feb 2010 (2007)","DOI":"10.1145\/1315245.1315280"},{"key":"9302_CR12","doi-asserted-by":"crossref","unstructured":"D.\u00a0Boneh, X.\u00a0Boyen. Short signatures without random oracles. In C.\u00a0Cachin, J.\u00a0Camenisch, editors, EUROCRYPT\u00a02004, vol. 3027 of LNCS (Springer, 2004), pp. 56\u201373","DOI":"10.1007\/978-3-540-24676-3_4"},{"key":"9302_CR13","doi-asserted-by":"crossref","unstructured":"D.\u00a0Boneh, X.\u00a0Boyen, E.-J. Goh. Hierarchical identity based encryption with constant size ciphertext, in R.\u00a0Cramer, editor, EUROCRYPT\u00a02005, vol. 3494 of LNCS (Springer, 2005), pp. 440\u2013456","DOI":"10.1007\/11426639_26"},{"key":"9302_CR14","doi-asserted-by":"crossref","unstructured":"D.\u00a0Boneh, X.\u00a0Boyen, E.-J. Goh. Hierarchical identity based encryption with constant size ciphertext. Cryptology ePrint Archive, Report 2005\/015 (2005)","DOI":"10.1007\/11426639_26"},{"key":"9302_CR15","doi-asserted-by":"crossref","unstructured":"D.\u00a0Boneh, M.\u00a0K. Franklin, Identity-based encryption from the Weil pairing, in J.\u00a0Kilian, editor, CRYPTO\u00a02001, vol. 2139 of LNCS (Springer, 2001), pp. 213\u2013229","DOI":"10.1007\/3-540-44647-8_13"},{"key":"9302_CR16","doi-asserted-by":"crossref","unstructured":"D.\u00a0Boneh, C.\u00a0Gentry, B.\u00a0Waters. Collusion resistant broadcast encryption with short ciphertexts and private keys, in V.\u00a0Shoup, editor, CRYPTO\u00a02005, vol. 3621 of LNCS (Springer, 2005), pp. 258\u2013275","DOI":"10.1007\/11535218_16"},{"key":"9302_CR17","doi-asserted-by":"crossref","unstructured":"D.\u00a0Boneh, E.-J. Goh, K.\u00a0Nissim, Evaluating 2-DNF formulas on ciphertexts, in J.\u00a0Kilian, editor, TCC\u00a02005, vol. 3378 of LNCS (Springer, 2005), pp. 325\u2013341","DOI":"10.1007\/978-3-540-30576-7_18"},{"key":"9302_CR18","doi-asserted-by":"crossref","unstructured":"X.\u00a0Boyen. The uber-assumption family (invited talk), in S.\u00a0D. Galbraith, K.\u00a0G. Paterson, editors, PAIRING 2008, vol. 5209 of LNCS (Springer, 2008), pp. 39\u201356","DOI":"10.1007\/978-3-540-85538-5_3"},{"key":"9302_CR19","doi-asserted-by":"crossref","unstructured":"E.\u00a0Bresson, Y.\u00a0Lakhnech, L.\u00a0Mazar\u00e9, B.\u00a0Warinschi, A generalization of DDH with applications to protocol analysis and computational soundness, in A.\u00a0Menezes, editor, CRYPTO\u00a02007, vol. 4622 of LNCS (Springer, 2007), pp. 482\u2013499","DOI":"10.1007\/978-3-540-74143-5_27"},{"key":"9302_CR20","doi-asserted-by":"crossref","unstructured":"H.\u00a0Cohen, A course in computational algebraic number theory, vol. 138 of Graduate Texts in Mathematics (Springer, Berlin, 1993)","DOI":"10.1007\/978-3-662-02945-9"},{"key":"9302_CR21","doi-asserted-by":"crossref","unstructured":"L.\u00a0De\u00a0Moura, N.\u00a0Bj\u00f8rner, Z: An efficient smt solver, in Tools and Algorithms for the Construction and Analysis of Systems (Springer, 2008), pp. 337\u2013340","DOI":"10.1007\/978-3-540-78800-3_24"},{"key":"9302_CR22","doi-asserted-by":"crossref","unstructured":"A.\u00a0Escala, G.\u00a0Herold, E.\u00a0Kiltz, C.\u00a0R\u00e0fols, J.\u00a0Villar. An algebraic framework for Diffie\u2013Hellman assumptions, in R.\u00a0Canetti, J.\u00a0A. Garay, editors, CRYPTO\u00a02013, Part II, vol. 8043 of LNCS (Springer, 2013), pp. 129\u2013147","DOI":"10.1007\/978-3-642-40084-1_8"},{"key":"9302_CR23","doi-asserted-by":"crossref","unstructured":"D.\u00a0M. Freeman, Converting pairing-based cryptosystems from composite-order groups to prime-order groups, in H.\u00a0Gilbert, editor, EUROCRYPT\u00a02010, vol. 6110 of LNCS (Springer, 2010), pp. 44\u201361","DOI":"10.1007\/978-3-642-13190-5_3"},{"key":"9302_CR24","doi-asserted-by":"crossref","unstructured":"S.\u00a0Garg, C.\u00a0Gentry, A.\u00a0Sahai, B.\u00a0Waters. Witness encryption and its applications, in D.\u00a0Boneh, T.\u00a0Roughgarden, J.\u00a0Feigenbaum, editors, 45th ACM STOC (ACM Press, 2013), pp. 467\u2013476","DOI":"10.1145\/2488608.2488667"},{"key":"9302_CR25","doi-asserted-by":"crossref","unstructured":"K.\u00a0Gj\u00f8steen, \u00d8.\u00a0Thuen. Password-based signatures, in Public Key Infrastructures, Services and Applications (Springer, 2012), pp. 17\u201333","DOI":"10.1007\/978-3-642-29804-2_2"},{"key":"9302_CR26","unstructured":"S.\u00a0Halevi, A plausible approach to computer-aided cryptographic proofs. Cryptology ePrint Archive, Report 2005\/181 (2005)"},{"key":"9302_CR27","doi-asserted-by":"crossref","unstructured":"C.\u00a0Hanser, D.\u00a0Slamanig, Structure-preserving signatures on equivalence classes and their application to anonymous credentials, in P.\u00a0Sarkar, T.\u00a0Iwata, editors, Advances in Cryptology\u2014ASIACRYPT 2014, vol. 8873 of Lecture Notes in Computer Science (Springer, Berlin, 2014), pp. 491\u2013511","DOI":"10.1007\/978-3-662-45611-8_26"},{"key":"9302_CR28","doi-asserted-by":"crossref","unstructured":"C.\u00a0Hanser, D.\u00a0Slamanig. Structure-preserving signatures on equivalence classes and their application to anonymous credentials, in P.\u00a0Sarkar, T.\u00a0Iwata, editors, Advances in Cryptology\u2014ASIACRYPT 2014, vol. 8873 of Lecture Notes in Computer Science (Springer, Berlin, 2014), pp. 491\u2013511","DOI":"10.1007\/978-3-662-45611-8_26"},{"key":"9302_CR29","doi-asserted-by":"crossref","unstructured":"S.\u00a0Hohenberger, A.\u00a0Sahai, B.\u00a0Waters, Full domain hash from (leveled) multilinear maps and identity-based aggregate signatures, in R.\u00a0Canetti, J.\u00a0A. Garay, editors, CRYPTO\u00a02013, Part I, vol. 8042 of LNCS (Springer, 2013), pp. 494\u2013512","DOI":"10.1007\/978-3-642-40041-4_27"},{"key":"9302_CR30","doi-asserted-by":"crossref","unstructured":"J.\u00a0Y. Hwang, D.\u00a0H. Lee, M.\u00a0Yung, Universal forgery of the identity-based sequential aggregate signature scheme, in W.\u00a0Li, W.\u00a0Susilo, U.\u00a0K. Tupakula, R.\u00a0Safavi-Naini, V.\u00a0Varadharajan, editors, ASIACCS 09 (ACM Press, 2009), pp. 157\u2013160","DOI":"10.1145\/1533057.1533080"},{"key":"9302_CR31","doi-asserted-by":"crossref","unstructured":"T.\u00a0Jager, A.\u00a0Rupp, The semi-generic group model and applications to pairing-based cryptography, in M.\u00a0Abe, editor, ASIACRYPT\u00a02010, vol. 6477 of LNCS (Springer, 2010), pp. 539\u2013556","DOI":"10.1007\/978-3-642-17373-8_31"},{"key":"9302_CR32","doi-asserted-by":"crossref","unstructured":"T.\u00a0Jager, J.\u00a0Schwenk, On the equivalence of generic group models, in J.\u00a0Baek, F.\u00a0Bao, K.\u00a0Chen, X.\u00a0Lai, editors, ProvSec 2008, vol. 5324 of LNCS (Springer, 2008), pp. 200\u2013209","DOI":"10.1007\/978-3-540-88733-1_14"},{"key":"9302_CR33","doi-asserted-by":"crossref","unstructured":"D.\u00a0Jovanovi\u0107, L.\u00a0De\u00a0Moura, Solving non-linear arithmetic, in Automated Reasoning(Springer, 2012), pp. 339\u2013354","DOI":"10.1007\/978-3-642-31365-3_27"},{"key":"9302_CR34","doi-asserted-by":"crossref","unstructured":"J.\u00a0Katz, A.\u00a0Sahai, B.\u00a0Waters, Predicate encryption supporting disjunctions, polynomial equations, and inner products, in N.\u00a0P. Smart, editor, EUROCRYPT\u00a02008, vol. 4965 of LNCS (Springer, 2008), pp. 146\u2013162","DOI":"10.1007\/978-3-540-78967-3_9"},{"key":"9302_CR35","doi-asserted-by":"crossref","unstructured":"J.\u00a0Katz, A.\u00a0Sahai, B.\u00a0Waters, Predicate encryption supporting disjunctions, polynomial equations, and inner products. Journal of Cryptology, 26(2), 191\u2013224 (2013)","DOI":"10.1007\/s00145-012-9119-4"},{"key":"9302_CR36","doi-asserted-by":"crossref","unstructured":"A.\u00a0Lysyanskaya, R.\u00a0L. Rivest, A.\u00a0Sahai, S.\u00a0Wolf, Pseudonym systems, in H.\u00a0M. Heys, C.\u00a0M. Adams, editors, SAC 1999, vol. 1758 of LNCS (Springer, 1999), pp 184\u2013199","DOI":"10.1007\/3-540-46513-8_14"},{"key":"9302_CR37","first-page":"279","volume":"191","author":"JV Matijasevic","year":"1970","unstructured":"J.\u00a0V. Matijasevic, Enumerable sets are diophantine. Dokl. Akad. Nauk SSSR, 191, 279\u2013282 (1970)","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"9302_CR38","doi-asserted-by":"crossref","unstructured":"U.\u00a0M. Maurer, Abstract models of computation in cryptography (invited paper), in N.\u00a0P. Smart, editor, 10th IMA International Conference on Cryptography and Coding, vol. 3796 of LNCS (Springer, 2005), pp. 1\u201312","DOI":"10.1007\/11586821_1"},{"key":"9302_CR39","doi-asserted-by":"crossref","unstructured":"U.\u00a0M. Maurer, S.\u00a0Wolf. Diffie\u2013Hellman oracles, in N.\u00a0Koblitz, editor, CRYPTO\u201996, vol. 1109 of LNCS (Springer, 1996), pp. 268\u2013282","DOI":"10.1007\/3-540-68697-5_21"},{"key":"9302_CR40","doi-asserted-by":"crossref","unstructured":"M.\u00a0Naor, On cryptographic assumptions and challenges (invited talk), in D.\u00a0Boneh, editor, CRYPTO\u00a02003, vol. 2729 of LNCS (Springer, 2003), pp. 96\u2013109","DOI":"10.1007\/978-3-540-45146-4_6"},{"issue":"2","key":"9302_CR41","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/BF02113297","volume":"55","author":"VI Nechaev","year":"1994","unstructured":"V.\u00a0I. Nechaev, Complexity of a determinate algorithm for the discrete logarithm. Mathematical Notes, 55(2), 165\u2013172 (1994)","journal-title":"Mathematical Notes"},{"key":"9302_CR42","doi-asserted-by":"crossref","unstructured":"T.\u00a0Okamoto, K.\u00a0Takashima, Fully secure functional encryption with general relations from the decisional linear assumption, in T.\u00a0Rabin, editor, CRYPTO\u00a02010, vol. 6223 of LNCS (Springer, 2010), pp. 191\u2013208","DOI":"10.1007\/978-3-642-14623-7_11"},{"issue":"2","key":"9302_CR43","doi-asserted-by":"publisher","first-page":"179","DOI":"10.4064\/fm-47-2-179-204","volume":"47","author":"A Robinson","year":"1959","unstructured":"A.\u00a0Robinson, Solution of a problem of tarski. Fundamenta Mathematicae, 47(2), 179\u2013204 (1959)","journal-title":"Fundamenta Mathematicae"},{"key":"9302_CR44","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"JT Schwartz","year":"1980","unstructured":"J.\u00a0T. Schwartz, Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM, 27, 701\u2013717 (1980)","journal-title":"J. ACM"},{"key":"9302_CR45","unstructured":"H.\u00a0Shacham, A cramer-shoup encryption scheme from the linear assumption and from progressively weaker linear variants. Cryptology ePrint Archive, Report 2007\/074 (2007). \n                    http:\/\/eprint.iacr.org\/2007\/074\n                    \n                  ."},{"key":"9302_CR46","doi-asserted-by":"crossref","unstructured":"V.\u00a0Shoup, Lower bounds for discrete logarithms and related problems, in W.\u00a0Fumy, editor, EUROCRYPT\u201997, vol. 1233 of LNCS (Springer, 1997), pp. 256\u2013266","DOI":"10.1007\/3-540-69053-0_18"},{"key":"9302_CR47","unstructured":"W.\u00a0Stein et\u00a0al. Sage Mathematics Software (Version 5.12). The Sage Development Team (2013) \n                    http:\/\/www.sagemath.org"},{"key":"9302_CR48","doi-asserted-by":"crossref","unstructured":"M.\u00a0Szydlo, A note on chosen-basis decisional Diffie\u2013Hellman assumptions, in Financial Cryptography and Data Security (Springer, 2006), pp. 166\u2013170","DOI":"10.1007\/11889663_14"},{"key":"9302_CR49","doi-asserted-by":"crossref","unstructured":"R.\u00a0Zippel, Probabilistic algorithms for sparse polynomials, in E.\u00a0W. Ng, editor, EUROSM \u201979, vol.\u00a072 of Lecture Notes in Computer Science (Springer, 1979), pp. 216\u2013226","DOI":"10.1007\/3-540-09519-5_73"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00145-018-9302-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-018-9302-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-018-9302-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T08:11:08Z","timestamp":1586333468000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00145-018-9302-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,12,18]]},"references-count":49,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,4]]}},"alternative-id":["9302"],"URL":"https:\/\/doi.org\/10.1007\/s00145-018-9302-3","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,12,18]]},"assertion":[{"value":"28 July 2015","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 July 2018","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 December 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}