{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T22:54:22Z","timestamp":1781650462571,"version":"3.54.5"},"reference-count":114,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2016,10,4]],"date-time":"2016-10-04T00:00:00Z","timestamp":1475539200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,12]]},"DOI":"10.1007\/s00453-016-0221-0","type":"journal-article","created":{"date-parts":[[2016,10,4]],"date-time":"2016-10-04T19:13:09Z","timestamp":1475608389000},"page":"1102-1160","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":59,"title":["Scalable Zero Knowledge Via Cycles of Elliptic Curves"],"prefix":"10.1007","volume":"79","author":[{"given":"Eli","family":"Ben-Sasson","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3029-2353","authenticated-orcid":false,"given":"Alessandro","family":"Chiesa","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eran","family":"Tromer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Madars","family":"Virza","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,10,4]]},"reference":[{"key":"221_CR1","doi-asserted-by":"crossref","unstructured":"Lyubashevsky, V., Micciancio, D., Peikert, C., Rosen, A.: SWIFFT: a modest proposal for FFT hashing. In: Proceedings of the 15th International Workshop on Fast Software Encryption, FSE \u201908, pp. 54\u201372 (2008)","DOI":"10.1007\/978-3-540-71039-4_4"},{"key":"221_CR2","doi-asserted-by":"crossref","unstructured":"Ajtai, M.: Generating hard instances of lattice problems. In: Proceedings of the 28th Annual ACM Symposium on the Theory of Computing, STOC\u00a0\u201996, pp. 99\u2013108 (1996)","DOI":"10.1145\/237814.237838"},{"key":"221_CR3","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1090\/S0025-5718-1993-1199989-X","volume":"61","author":"AOL Atkin","year":"1993","unstructured":"Atkin, A.O.L., Morain, F.: Elliptic curves and primality proving. Math. Comput. 61, 29\u201368 (1993)","journal-title":"Math. Comput."},{"key":"221_CR4","doi-asserted-by":"crossref","unstructured":"Angluin, D., Valiant, L.G.: Fast probabilistic algorithms for hamiltonian circuits and matchings. In: Proceedings on 9th Annual ACM Symposium on Theory of Computing, STOC\u00a0\u201977, pp. 30\u201341 (1977)","DOI":"10.1145\/800105.803393"},{"key":"221_CR5","doi-asserted-by":"crossref","unstructured":"Boneh, D., Boyen, X.: Secure identity based encryption without random oracles. In: Proceedings of the 24th Annual International Cryptology Conference, CRYPTO\u00a0\u201904, pp. 443\u2013459 (2004)","DOI":"10.1007\/978-3-540-28628-8_27"},{"key":"221_CR6","doi-asserted-by":"crossref","unstructured":"Backes, M., Barbosa, M., Fiore, D., Reischuk, R.M.: ADSNARK: nearly practical and privacy-preserving proofs on authenticated data. In Proceedings of the 36th IEEE Symposium on Security and Privacy, S&P\u00a0\u201915, pp. 271\u2013286 (2015)","DOI":"10.1109\/SP.2015.24"},{"key":"221_CR7","doi-asserted-by":"crossref","unstructured":"Bitansky, N., Canetti, R., Chiesa, A., Tromer, E.: From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again. In: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS\u00a0\u201912, pp. 326\u2013349 (2012)","DOI":"10.1145\/2090236.2090263"},{"key":"221_CR8","doi-asserted-by":"crossref","unstructured":"Bitansky, N., Canetti, R., Chiesa, A., Tromer, E.: Recursive composition and bootstrapping for SNARKs and proof-carrying data. In: Proceedings of the 45th ACM Symposium on the Theory of Computing, STOC\u00a0\u201913, pp. 111\u2013120 (2013)","DOI":"10.1145\/2488608.2488623"},{"key":"221_CR9","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Chiesa, A., Genkin, D., Tromer, E., Virza, M.: SNARKs for C: verifying program executions succinctly and in zero knowledge. In Proceedings of the 33rd Annual International Cryptology Conference, CRYPTO\u00a0\u201913, pp. 90\u2013108 (2013)","DOI":"10.1007\/978-3-642-40084-1_6"},{"key":"221_CR10","unstructured":"Ben-Sasson, E., Chiesa, A., Genkin, D., Tromer, E., Virza, M.: TinyRAM architecture specification v2.00, 2013. http:\/\/scipr-lab.org\/tinyram"},{"key":"221_CR11","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Chiesa, A., Garman, C., Green, M., Miers, I., Tromer, E., Virza, M.: Zerocash: decentralized anonymous payments from Bitcoin. In: Proceedings of the 2014 IEEE Symposium on Security and Privacy, SP\u00a0\u201914, pp. 459\u2013474 (2014)","DOI":"10.1109\/SP.2014.36"},{"key":"221_CR12","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Chiesa, A., Genkin, D., Tromer, E.: Fast reductions from RAMs to delegatable succinct constraint satisfaction problems. In: Proceedings of the 4th Innovations in Theoretical Computer Science Conference, ITCS\u00a0\u201913, pp. 401\u2013414 (2013)","DOI":"10.1145\/2422436.2422481"},{"key":"221_CR13","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Chiesa, A., Genkin, D., Tromer, E.: On the concrete efficiency of probabilistically-checkable proofs. In: Proceedings of the 45th ACM Symposium on the Theory of Computing, STOC\u00a0\u201913, pp. 585\u2013594 (2013)","DOI":"10.1145\/2488608.2488681"},{"key":"221_CR14","doi-asserted-by":"crossref","unstructured":"Bitansky, N., Chiesa, A., Ishai, Y., Ostrovsky, R., Paneth, O.: Succinct non-interactive arguments via linear interactive proofs. In: Proceedings of the 10th Theory of Cryptography Conference, TCC\u00a0\u201913, pp. 315\u2013333 (2013)","DOI":"10.1007\/978-3-642-36594-2_18"},{"key":"221_CR15","doi-asserted-by":"crossref","unstructured":"Bitansky, N., Canetti, R., Paneth, O.: How to construct extractable one-way functions against uniform adversaries. Cryptology ePrint Archive, report 2013\/468 (2013)","DOI":"10.1145\/2591796.2591859"},{"key":"221_CR16","unstructured":"Bitansky, N., Canetti, R., Paneth, O., Rosen, A.: Indistinguishability obfuscation vs. auxiliary-input extractable functions: One must fall. Cryptology ePrint Archive, report 2013\/641 (2013)"},{"key":"221_CR17","unstructured":"Ben-Sasson, E., Chiesa, A., Tromer, E., Virza, M.: Succinct non-interactive zero knowledge for a von Neumann architecture. In: Proceedings of the 23rd USENIX Security Symposium, Security\u00a0\u201914, pp. 781\u2013796 (2014). http:\/\/eprint.iacr.org\/2013\/879"},{"issue":"6","key":"221_CR18","doi-asserted-by":"crossref","first-page":"1084","DOI":"10.1137\/0220068","volume":"20","author":"M Blum","year":"1991","unstructured":"Blum, M., De Santis, A., Micali, S., Persiano, G.: Non-interactive zero-knowledge. SIAM J. Comput. 20(6), 1084\u20131118 (1991)","journal-title":"SIAM J. Comput."},{"key":"221_CR19","doi-asserted-by":"crossref","unstructured":"Blum, M., Evans, W., Gemmell, P., Kannan, S., Naor, M.: Checking the correctness of memories. In: Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, FOCS\u00a0\u201991, pp. 90\u201399 (1991)","DOI":"10.1109\/SFCS.1991.185352"},{"key":"221_CR20","doi-asserted-by":"crossref","unstructured":"Babai, L., Fortnow, L., Levin, L.A., Szegedy, M.: Checking computations in polylogarithmic time. In: Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, STOC\u00a0\u201991, pp. 21\u201332 (1991)","DOI":"10.1145\/103418.103428"},{"key":"221_CR21","doi-asserted-by":"crossref","unstructured":"Blum, M., Feldman, P., Micali, S.: Non-interactive zero-knowledge and its applications. In: Proceedings of the 20th Annual ACM Symposium on Theory of Computing, STOC \u201988, pp. 103\u2013112 (1988)","DOI":"10.1145\/62212.62222"},{"key":"221_CR22","doi-asserted-by":"crossref","unstructured":"Braun, B., Feldman, A.J., Ren, Z., Setty, S., Blumberg, A.J., Walfish, M.: Verifying computations with state. In: Proceedings of the 25th ACM Symposium on Operating Systems Principles, SOSP \u201913, pp. 341\u2013357 (2013)","DOI":"10.1145\/2517349.2522733"},{"key":"221_CR23","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Goldreich, O., Harsha, P., Sudan, M., Vadhan, S.: Short PCPs verifiable in polylogarithmic time. In: Proceedings of the 20th Annual IEEE Conference on Computational Complexity, CCC\u00a0\u201905, pp. 120\u2013134 (2005)","DOI":"10.1109\/CCC.2005.27"},{"issue":"3","key":"221_CR24","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1007\/s10623-006-9033-6","volume":"42","author":"PS Barreto","year":"2007","unstructured":"Barreto, P.S., Galbraith, S.D., \u00d3 h\u00c9igeartaigh, C., Scott, M.: Efficient pairing computation on supersingular abelian varieties. Des. Codes Cryptogr. 42(3), 239\u2013271 (2007)","journal-title":"Des. Codes Cryptogr."},{"key":"221_CR25","doi-asserted-by":"crossref","unstructured":"Barreto, P.S.L.M., Kim, H.Y., Lynn, B., Scott, M.: Efficient algorithms for pairing-based cryptosystems. In: Proceedings of the 22Nd Annual International Cryptology Conference, CRYPTO \u201902, pp. 354\u2013368 (2002)","DOI":"10.1007\/3-540-45708-9_23"},{"key":"221_CR26","doi-asserted-by":"crossref","unstructured":"Brakerski, Z., Langlois, A., Peikert, C., Regev, O., Stehl\u00e9, D.: Classical hardness of learning with errors. In: Proceedings of the 45th Annual ACM Symposium on Symposium on Theory of Computing, STOC \u201913, pp. 575\u2013584 (2013)","DOI":"10.1145\/2488608.2488680"},{"key":"221_CR27","doi-asserted-by":"crossref","unstructured":"Barreto, P.S.L.M., Lynn, B., Scott, M.: Constructing elliptic curves with prescribed embedding degrees. In:Proceedings of the 3rd International Conference on Security in Communication Networks, SCN \u201902, pp. 257\u2013267 (2003)","DOI":"10.1007\/3-540-36413-7_19"},{"issue":"4","key":"221_CR28","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1007\/s00145-004-0311-z","volume":"17","author":"PSLM Barreto","year":"2004","unstructured":"Barreto, P.S.L.M., Lynn, B., Scott, M.: Efficient implementation of pairing-based cryptosystems. J. Cryptol. 17(4), 321\u2013334 (2004)","journal-title":"J. Cryptol."},{"key":"221_CR29","doi-asserted-by":"crossref","unstructured":"Benger, N., Scott, M.: Constructing tower extensions of finite fields for implementation of pairing-based cryptography. In: Proceedings of the 3rd International Conference on Arithmetic of Finite Fields, WAIFI \u201910, pp. 180\u2013195 (2010)","DOI":"10.1007\/978-3-642-13797-6_13"},{"key":"221_CR30","doi-asserted-by":"crossref","unstructured":"Boneh, D., Segev, G., Waters, B.: Targeted malleability: Homomorphic encryption for restricted computations. In: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS\u00a0\u201912, pp. 350\u2013366 (2012)","DOI":"10.1145\/2090236.2090264"},{"issue":"1","key":"221_CR31","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/s10623-004-3808-4","volume":"37","author":"F Brezing","year":"2005","unstructured":"Brezing, F., Weng, A.: Elliptic curves suitable for pairing based cryptography. Des. Codes Cryptpogr. 37(1), 133\u2013141 (2005)","journal-title":"Des. Codes Cryptpogr."},{"key":"221_CR32","volume-title":"Handbook of Elliptic and Hyperelliptic Curve Cryptography","author":"H Cohen","year":"2012","unstructured":"Cohen, H., Frey, G., Avanzi, R., Doche, C., Lange, T., Nguyen, K., Vercauteren, F.: Handbook of Elliptic and Hyperelliptic Curve Cryptography, 2nd edn. Chapman & Hall\/CRC, Boca Raton (2012)","edition":"2"},{"key":"221_CR33","doi-asserted-by":"crossref","unstructured":"Costello, C., Fournet, C., Howell, J., Kohlweiss, M., Kreuter, B., Naehrig, M., Parno, B., Zahur, S.: Geppetto: versatile verifiable computation. In: Proceedings of the 36th IEEE Symposium on Security and Privacy, S&P\u00a0\u201915, pp. 253\u2013270 (2015)","DOI":"10.1109\/SP.2015.23"},{"key":"221_CR34","doi-asserted-by":"crossref","unstructured":"Cormode, G., Mitzenmacher, M., Thaler, J.: Practical verified computation with streaming interactive proofs. In: Proceedings of the 4th Symposium on Innovations in Theoretical Computer Science, ITCS\u00a0\u201912, pp. 90\u2013112 (2012)","DOI":"10.1145\/2090236.2090245"},{"key":"221_CR35","unstructured":"Cocks, C., Pinch, R.G.E.: Identity-based cryptosystems based on the weil pairing. Unpublished manuscript (2001)"},{"key":"221_CR36","doi-asserted-by":"crossref","unstructured":"Cook, S.A., Reckhow, R.A.: Time-bounded random access machines. In: Proceedings of the 4th Annual ACM Symposium on Theory of Computing, STOC\u00a0\u201972, pp. 73\u201380 (1972)","DOI":"10.1145\/800152.804898"},{"key":"221_CR37","doi-asserted-by":"crossref","unstructured":"Canetti, R., Riva, B., Rothblum, G.N.: Practical delegation of computation using multiple servers. In: Proceedings of the 18th ACM Conference on Computer and Communications Security, CCS \u201911, pp. 445\u2013454 (2011)","DOI":"10.1145\/2046707.2046759"},{"key":"221_CR38","unstructured":"Chiesa, A., Tromer, E.: Proof-carrying data and hearsay arguments from signature cards. In: Proceedings of the 1st Symposium on Innovations in Computer Science, ICS\u00a0\u201910, pp. 310\u2013331 (2010)"},{"issue":"2","key":"221_CR39","first-page":"40","volume":"19","author":"A Chiesa","year":"2012","unstructured":"Chiesa, A., Tromer, E.: Proof-carrying data: secure computation on untrusted platforms (high-level description). Next Wave Natl. Secur. Agency\u2019s Rev. Emerg. Technol. 19(2), 40\u201346 (2012)","journal-title":"Next Wave Natl. Secur. Agency\u2019s Rev. Emerg. Technol."},{"key":"221_CR40","unstructured":"Chong, S., Tromer, E., Vaughan, J.A.: Enforcing language semantics using proof-carrying data. Cryptology ePrint Archive, Report 2013\/513 (2013)"},{"key":"221_CR41","doi-asserted-by":"crossref","unstructured":"Chiesa, A., Tromer, E., Virza, M.: Cluster computing in zero knowledge. In: Proceedings of the 34th Annual International Conference on Theory and Application of Cryptographic Techniques, EUROCRYPT\u00a0\u201915, pp. 371\u2013403 (2015)","DOI":"10.1007\/978-3-662-46803-6_13"},{"issue":"2","key":"221_CR42","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/s00145-004-0219-7","volume":"18","author":"R Dupont","year":"2005","unstructured":"Dupont, R., Enge, A., Morain, F.: Building curves with arbitrary small MOV degree over finite prime fields. J. Cryptol. 18(2), 79\u201389 (2005)","journal-title":"J. Cryptol."},{"key":"221_CR43","doi-asserted-by":"crossref","unstructured":"Danezis, G., Fournet, C., Groth, J., Kohlweiss, M.: Square span programs with applications to succinct NIZK arguments. In: Proceedings of the 20th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT\u00a0\u201914, pp. 532\u2013550 (2014)","DOI":"10.1007\/978-3-662-45611-8_28"},{"key":"221_CR44","doi-asserted-by":"crossref","unstructured":"Enge, A., Sutherland, A.V.: Class invariants by the CRT method. In: Proceedings of the 9th International Symposium on Algorithmic Number Theory, ANTS \u201910, pp. 142\u2013156 (2010)","DOI":"10.1007\/978-3-642-14518-6_14"},{"issue":"5","key":"221_CR45","doi-asserted-by":"crossref","first-page":"1717","DOI":"10.1109\/18.771254","volume":"45","author":"G Frey","year":"2006","unstructured":"Frey, G., M\u00fcller, M., R\u00fcck, H.-G.: The Tate pairing and the discrete logarithm applied to elliptic curve cryptosystems. IEEE Trans. Inf. Theory 45(5), 1717\u20131719 (2006)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"206","key":"221_CR46","first-page":"865","volume":"62","author":"G Frey","year":"1994","unstructured":"Frey, G., R\u00fcck, H.-G.: A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves. Math. Comput. 62(206), 865\u2013874 (1994)","journal-title":"Math. Comput."},{"key":"221_CR47","doi-asserted-by":"crossref","unstructured":"Fiat, A., Shamir, A.: How to prove yourself: practical solutions to identification and signature problems. In: Proceedings of the 6th Annual International Cryptology Conference, CRYPTO\u00a0\u201987, pp. 186\u2013194 (1987)","DOI":"10.1007\/3-540-47721-7_12"},{"issue":"2","key":"221_CR48","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1007\/s00145-009-9048-z","volume":"23","author":"D Freeman","year":"2010","unstructured":"Freeman, D., Scott, M., Teske, E.: A taxonomy of pairing-friendly elliptic curves. J. Cryptol. 23(2), 224\u2013280 (2010)","journal-title":"J. Cryptol."},{"key":"221_CR49","doi-asserted-by":"crossref","unstructured":"Gennaro, R.: Multi-trapdoor commitments and their applications to proofs of knowledge secure under concurrent man-in-the-middle attacks. In: Proceedings of the 24th Annual International Cryptology Conference, CRYPTO\u00a0\u201904, pp. 220\u2013236 (2004)","DOI":"10.1007\/978-3-540-28628-8_14"},{"key":"221_CR50","unstructured":"Goldreich, O., Goldwasser, S., Halevi, S.: Collision-free hashing from lattice problems. Technical report, 1996. ECCC TR95-042"},{"key":"221_CR51","doi-asserted-by":"crossref","unstructured":"Garg, S., Gentry, C., Halevi, S.: Candidate multilinear maps from ideal lattices. In: Proceedings of the 32nd Annual International Conference on Theory and Application of Cryptographic Techniques, EUROCRYPT \u201913, pp. 1\u201317 (2013)","DOI":"10.1007\/978-3-642-38348-9_1"},{"key":"221_CR52","doi-asserted-by":"crossref","unstructured":"Gennaro, R., Gentry, C., Parno, B., Raykova, M.: Quadratic span programs and succinct NIZKs without PCPs. In: Proceedings of the 32nd Annual International Conference on Theory and Application of Cryptographic Techniques, EUROCRYPT\u00a0\u201913, pp. 626\u2013645 (2013)","DOI":"10.1007\/978-3-642-38348-9_37"},{"key":"221_CR53","doi-asserted-by":"crossref","unstructured":"Galbraith, S.D., Harrison, K., Soldera, D.: Implementing the Tate pairing. In: Proceedings of the 5th International Symposium on Algorithmic Number Theory, ANTS \u201902, pp. 324\u2013337 (2002)","DOI":"10.1007\/3-540-45455-1_26"},{"key":"221_CR54","doi-asserted-by":"crossref","unstructured":"Gopalan, P., Lovett, S., Shpilka, A.: On the complexity of boolean functions in different characteristics. In: Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC \u201909, pp. 173\u2013183 (2009)","DOI":"10.1109\/CCC.2009.14"},{"key":"221_CR55","doi-asserted-by":"crossref","unstructured":"Groth, J.: Short pairing-based non-interactive zero-knowledge arguments. In: Proceedings of the 16th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT \u201910, pp. 321\u2013340 (2010)","DOI":"10.1007\/978-3-642-17373-8_19"},{"key":"221_CR56","unstructured":"Granger, R., Smart, N.: On computing products of pairings. Cryptology ePrint Archive, report 2006\/172 (2006)"},{"key":"221_CR57","doi-asserted-by":"crossref","unstructured":"Granger, R., Scott, M.: Faster squaring in the cyclotomic subgroup of sixth degree extensions. In: Proceedings of the 13th international conference on Practice and Theory in Public Key Cryptography, PKC\u201910, pp. 209\u2013223 (2010)","DOI":"10.1007\/978-3-642-13013-7_13"},{"key":"221_CR58","doi-asserted-by":"crossref","unstructured":"Gassend, B., Suh, G.E., Clarke, D.E., van Dijk, M., Devadas, S.: Caches and hash trees for efficient memory integrity verification. In: Proceedings of the 9th International Symposium on High-Performance Computer Architecture, HPCA \u201903, pp. 295\u2013306 (2003)","DOI":"10.1109\/HPCA.2003.1183547"},{"key":"221_CR59","unstructured":"Goh, E.-J., Shacham, H., Modadugu, N., Boneh, D.: SiRiUS: securing remote untrusted storage. In: Proceedings of the Network and Distributed System Security Symposium, NDSS\u00a0\u201903 (2003)"},{"key":"221_CR60","doi-asserted-by":"crossref","unstructured":"Gentry, C., Wichs, D.: Separating succinct non-interactive arguments from all falsifiable assumptions. In: Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, STOC\u00a0\u201911, pp. 99\u2013108 (2011)","DOI":"10.1145\/1993636.1993651"},{"issue":"10","key":"221_CR61","doi-asserted-by":"crossref","first-page":"4595","DOI":"10.1109\/TIT.2006.881709","volume":"52","author":"F Hess","year":"2006","unstructured":"Hess, F., Smart, N.P., Vercauteren, F.: The Eta pairing revisited. IEEE Trans. Inf. Theory 52(10), 4595\u20134602 (2006)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"3","key":"221_CR62","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1007\/s001459900042","volume":"11","author":"A Joux","year":"1998","unstructured":"Joux, A., Jacques, S.: Lattice reduction: a toolbox for the cryptanalyst. J. Cryptol. 11(3), 161\u2013185 (1998)","journal-title":"J. Cryptol."},{"issue":"6","key":"221_CR63","doi-asserted-by":"crossref","first-page":"4033","DOI":"10.1109\/TIT.2013.2240763","volume":"59","author":"T Kim","year":"2013","unstructured":"Kim, T., Kim, S., Cheon, J.H.: On the final exponentiation in Tate pairing computations. IEEE Trans. Inf. Theory 59(6), 4033\u20134041 (2013)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"221_CR64","unstructured":"Kosba, A.E., Papadopoulos, D., Papamanthou, C., Sayed, M.F., Shi, E., Triandopoulos, N.: TRUESET: faster verifiable set computations. In: Proceedings of the 23rd USENIX Security Symposium, USENIX Security\u00a0\u201914, pp. 765\u2013780 (2014)"},{"key":"221_CR65","unstructured":"Kallahalla, M., Riedel, E., Swaminathan, R., Wang, Q., Fu, K.: Plutus: scalable secure file sharing on untrusted storage. In: Proceedings of the 2003 Conference on File and Storage Technologies, FAST\u00a0\u201903 (2003)"},{"key":"221_CR66","doi-asserted-by":"crossref","unstructured":"Karabina, K., Teske, E.: On prime-order elliptic curves with embedding degrees $$k=$$ k = 3, 4, and 6. In: Proceedings of the 8th International Conference on Algorithmic Number Theory, ANTS-VIII \u201908, pp. 102\u2013117 (2008)","DOI":"10.1007\/978-3-540-79456-1_6"},{"key":"221_CR67","doi-asserted-by":"crossref","unstructured":"Lipmaa, H.: Progression-free sets and sublinear pairing-based non-interactive zero-knowledge arguments. In: Proceedings of the 9th Theory of Cryptography Conference on Theory of Cryptography, TCC\u00a0\u201912, pp. 169\u2013189 (2012)","DOI":"10.1007\/978-3-642-28914-9_10"},{"key":"221_CR68","doi-asserted-by":"crossref","unstructured":"Lipmaa, H.: Succinct non-interactive zero knowledge arguments from span programs and linear error-correcting codes. In: Proceedings of the 19th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT\u00a0\u201913, pp. 41\u201360 (2013)","DOI":"10.1007\/978-3-642-42033-7_3"},{"key":"221_CR69","doi-asserted-by":"crossref","unstructured":"Lipmaa, H.: Efficient NIZK arguments via parallel verification of Bene\u0161 networks. In: Proceedings of the 9th International Conference on Security and Cryptography for Networks, SCN \u201914, pp. 416\u2013434 (2014)","DOI":"10.1007\/978-3-319-10879-7_24"},{"key":"221_CR70","doi-asserted-by":"crossref","unstructured":"Lyubashevsky, V., Micciancio, D.: Generalized compact knapsacks are collision resistant. In: Proceedings of the 33rd International Conference on Automata, Languages and Programming, ICALP \u201906, pp. 144\u2013155 (2006)","DOI":"10.1007\/11787006_13"},{"key":"221_CR71","doi-asserted-by":"crossref","unstructured":"Lauter, K., Montgomery, P.L., Naehrig, M.: An analysis of affine coordinates for pairing computation. In: Proceedings of the 4th International Conference on Pairing-Based Cryptography, Pairing \u201910, pp. 1\u201320 (2010)","DOI":"10.1007\/978-3-642-17455-1_1"},{"key":"221_CR72","doi-asserted-by":"crossref","unstructured":"Lyubashevsky, V., Micciancio, D., Peikert, C., Rosen, A.: SWIFFT: a modest proposal for FFT hashing. In: Proceedings of the 15th International Workshop on Fast Software Encryption, FSE \u201908, pp. 54\u201372 (2008)","DOI":"10.1007\/978-3-540-71039-4_4"},{"key":"221_CR73","volume-title":"Finite Fields","author":"R Lidl","year":"1997","unstructured":"Lidl, R., Niederreiter, H.: Finite Fields, 2nd edn. Cambridge University Press, Cambridge (1997)","edition":"2"},{"key":"221_CR74","doi-asserted-by":"crossref","unstructured":"Micali, S.: Computationally sound proofs. SIAM J. Comput. 30(4):1253\u20131298, 2000. Preliminary version appeared in FOCS\u00a0\u201994","DOI":"10.1137\/S0097539795284959"},{"issue":"5","key":"221_CR75","first-page":"1234","volume":"84","author":"A Miyaji","year":"2001","unstructured":"Miyaji, A., Nakabayashi, M., Takano, S.: New explicit conditions of elliptic curve traces for FR-reduction. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 84(5), 1234\u20131243 (2001)","journal-title":"IEICE Trans. Fundam. Electron. Commun. Comput. Sci."},{"key":"221_CR76","doi-asserted-by":"crossref","unstructured":"Menezes, A., Okamoto, T., Vanstone, S.: Reducing elliptic curve logarithms to logarithms in a finite field. In: Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, STOC \u201991, pp. 80\u201389 (1991)","DOI":"10.1145\/103418.103434"},{"key":"221_CR77","doi-asserted-by":"crossref","unstructured":"Mazi\u00e8res, D., Shasha, D.: Don\u2019t trust your file server. In: Proceedings of the 8th Workshop on Hot Topics in Operating Systems, HotOS \u201901, pp. 113\u2013118 (2001)","DOI":"10.1109\/HOTOS.2001.990070"},{"key":"221_CR78","unstructured":"Maheshwari, U., Vingralek, R., Shapiro, W.: How to build a trusted database system on untrusted storage. In: Proceedings of the 4th Conference on Symposium on Operating System Design and Implementation, OSDI \u201900, pp. 10\u201310 (2000)"},{"key":"221_CR79","doi-asserted-by":"crossref","unstructured":"Naor, M., Yung, M.: Universal one-way hash functions and their cryptographic applications. In: Proceedings of the 21st Annual ACM Symposium on Theory of Computing, STOC\u00a0\u201989, pp. 33\u201343 (1989)","DOI":"10.1145\/73007.73011"},{"key":"221_CR80","doi-asserted-by":"crossref","unstructured":"Naor, M., Yung, M.: Public-key cryptosystems provably secure against chosen ciphertext attacks. In: Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, STOC \u201990, pp. 427\u2013437 (1990)","DOI":"10.1145\/100216.100273"},{"key":"221_CR81","doi-asserted-by":"crossref","unstructured":"Odlyzko, A.M.: Discrete logarithms in finite fields and their cryptographic significance. In: Proceedings of the 3rd Annual International Conference on Theory and Application of Cryptographic Techniques, EUROCRYPT\u00a0\u201985, pp. 224\u2013314 (1985)","DOI":"10.1007\/3-540-39757-4_20"},{"key":"221_CR82","doi-asserted-by":"crossref","unstructured":"Parno, B., Gentry, C., Howell, J., Raykova, M.: Pinocchio: Nearly practical verifiable computation. In: Proceedings of the 34th IEEE Symposium on Security and Privacy, Oakland\u00a0\u201913, pp. 238\u2013252 (2013)","DOI":"10.1109\/SP.2013.47"},{"issue":"1","key":"221_CR83","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1109\/TIT.1978.1055817","volume":"24","author":"S Pohlig","year":"1978","unstructured":"Pohlig, S., Hellman, M.: An improved algorithm for computing logarithms over $$gf(p)$$ g f ( p ) and its cryptographic significance. J. IEEE Trans. Inf. Theory 24(1), 106\u2013110 (1978)","journal-title":"J. IEEE Trans. Inf. Theory"},{"issue":"143","key":"221_CR84","first-page":"918","volume":"32","author":"JM Pollard","year":"1978","unstructured":"Pollard, J.M.: Monte Carlo methods for index computation (mod p). Math. Comput. 32(143), 918\u2013924 (1978)","journal-title":"Math. Comput."},{"key":"221_CR85","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1007\/s001450010010","volume":"13","author":"JM Pollard","year":"2000","unstructured":"Pollard, J.M.: Kangaroos, monopoly and discrete logarithms. J. Cryptol. 13, 437\u2013447 (2000)","journal-title":"J. Cryptol."},{"key":"221_CR86","doi-asserted-by":"crossref","unstructured":"Peikert, C., Rosen, A.: Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices. In: Proceedings of the 3rd Conference on Theory of Cryptography, TCC \u201906, pp. 145\u2013166 (2006)","DOI":"10.1007\/11681878_8"},{"issue":"4","key":"221_CR87","first-page":"333","volume":"41","author":"AA Razborov","year":"1987","unstructured":"Razborov, A.A.: Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Math. Notes Acad. Sci. USSR 41(4), 333\u2013338 (1987)","journal-title":"Math. Notes Acad. Sci. USSR"},{"key":"221_CR88","doi-asserted-by":"crossref","unstructured":"Rompel, J.: One-way functions are necessary and sufficient for secure signatures. In: Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, STOC\u00a0\u201990, pp. 387\u2013394 (1990)","DOI":"10.1145\/100216.100269"},{"issue":"1","key":"221_CR89","first-page":"81","volume":"47","author":"T Satoh","year":"1998","unstructured":"Satoh, T., Araki, K.: Fermat quotients and the polynomial time discrete log algorithm for anomalous elliptic curves. Comment. Math. Univ. Sancti Pauli 47(1), 81\u201392 (1998)","journal-title":"Comment. Math. Univ. Sancti Pauli"},{"issue":"2","key":"221_CR90","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/s10623-005-0538-1","volume":"38","author":"M Scott","year":"2006","unstructured":"Scott, M., Barreto, P.S.: Generating more MNT elliptic curves. Des. Codes Cryptogr. 38(2), 209\u2013217 (2006)","journal-title":"Des. Codes Cryptogr."},{"key":"221_CR91","doi-asserted-by":"crossref","unstructured":"Scott, M., Benger, N., Charlemagne, M., Dominguez Perez, L.J., Kachisa, E.J.: On the final exponentiation for calculating pairings on ordinary elliptic curves. In: Proceedings of the 3rd International Conference Palo Alto on Pairing-Based Cryptography, Pairing \u201909, pp. 78\u201388 (2009)","DOI":"10.1007\/978-3-642-03298-1_6"},{"key":"221_CR92","doi-asserted-by":"crossref","unstructured":"Setty, S., Braun, B., Vu, V., Blumberg, A.J., Parno, B., Walfish, M.: Resolving the conflict between generality and plausibility in verified computation. In: Proceedings of the 8th EuoroSys Conference, EuroSys\u00a0\u201913, pp. 71\u201384 (2013)","DOI":"10.1145\/2465351.2465359"},{"key":"221_CR93","unstructured":"Setty, S., Blumberg, A.J., Walfish, M.: Toward practical and unconditional verification of remote computations. In: Proceedings of the 13th USENIX Conference on Hot Topics in Operating Systems, HotOS\u00a0\u201911, pp. 29\u201329 (2011)"},{"key":"221_CR94","doi-asserted-by":"crossref","unstructured":"Scott, M.: Computing the Tate pairing. In: Proceedings of the The Cryptographers\u2019 Track at the RSA Conference 2005, CT-RSA \u201905, pp. 293\u2013304 (2005)","DOI":"10.1007\/978-3-540-30574-3_20"},{"key":"221_CR95","unstructured":"Scott, M.: Implementing cryptographic pairings. In: Proceedings of the 1st First International Conference on Pairing-Based Cryptography, Pairing \u201907, pp. 177\u2013196 (2007)"},{"issue":"221","key":"221_CR96","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1090\/S0025-5718-98-00887-4","volume":"67","author":"IA Semaev","year":"1998","unstructured":"Semaev, I.A.: Evaluation of discrete logarithms in a group of p-torsion points of an elliptic curve in characteristic p. Math. Comput. 67(221), 353\u2013356 (1998)","journal-title":"Math. Comput."},{"key":"221_CR97","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1090\/pspum\/020\/0316385","volume":"20","author":"D Shanks","year":"1971","unstructured":"Shanks, D.: Class number, a theory of factorization, and genera. Symp. Pure Math. 20, 415\u2013440 (1971)","journal-title":"Symp. Pure Math."},{"key":"221_CR98","doi-asserted-by":"crossref","DOI":"10.1007\/978-0-387-09494-6","volume-title":"The Arithmetic of Elliptic Curves","author":"JH Silverman","year":"2009","unstructured":"Silverman, J.H.: The Arithmetic of Elliptic Curves, 2nd edn. Springer, Berlin (2009)","edition":"2"},{"issue":"3","key":"221_CR99","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1007\/s001459900052","volume":"12","author":"NP Smart","year":"1999","unstructured":"Smart, N.P.: The discrete logarithm problem on elliptic curves of trace one. J. Cryptol. 12(3), 193\u2013196 (1999)","journal-title":"J. Cryptol."},{"key":"221_CR100","unstructured":"Setty, S., McPherson, M., Blumberg, A.J., Walfish, M.: Making argument systems for outsourced computation practical (sometimes). In: Proceedings of the 2012 Network and Distributed System Security Symposium, NDSS\u00a0\u201912 (2012)"},{"key":"221_CR101","doi-asserted-by":"crossref","unstructured":"Smolensky, R.: Algebraic methods in the theory of lower bounds for boolean circuit complexity. In: Proceedings of the 19th Annual ACM Symposium on Theory of Computing, STOC \u201987, pp. 77\u201382 (1987)","DOI":"10.1145\/28395.28404"},{"key":"221_CR102","unstructured":"Solinas, J.A.: Id-based digital signature algorithms. http:\/\/cacr.uwaterloo.ca\/conferences\/2003\/ecc2003\/solinas.pdf (2003)"},{"issue":"3","key":"221_CR103","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1080\/10586458.2011.565253","volume":"20","author":"JH Silverman","year":"2011","unstructured":"Silverman, J.H., Stange, K.E.: Amicable pairs and aliquot cycles for elliptic curves. Exp. Math. 20(3), 329\u2013357 (2011)","journal-title":"Exp. Math."},{"issue":"273","key":"221_CR104","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1090\/S0025-5718-2010-02373-7","volume":"80","author":"AV Sutherland","year":"2011","unstructured":"Sutherland, A.V.: Computing Hilbert class polynomials with the Chinese remainder theorem. Math. Comput. 80(273), 501\u2013538 (2011)","journal-title":"Math. Comput."},{"key":"221_CR105","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1112\/S1461157012001015","volume":"15","author":"AV Sutherland","year":"2012","unstructured":"Sutherland, A.V.: Accelerating the CM method. LMS J. Comput. Math. 15, 172\u2013204 (2012)","journal-title":"LMS J. Comput. Math."},{"key":"221_CR106","unstructured":"Setty, S., Vu, V., Panpalia, N., Braun, B., Blumberg, A.J., Walfish, M.: Taking proof-based verified computation a few steps closer to practicality. In: Proceedings of the 21st USENIX Security Symposium, Security\u00a0\u201912, pp. 253\u2013268 (2012)"},{"key":"221_CR107","doi-asserted-by":"crossref","unstructured":"Thaler, J.: Time-optimal interactive proofs for circuit evaluation. In: Proceedings of the 33rd Annual International Cryptology Conference, CRYPTO \u201913, pp. 71\u201389 (2013)","DOI":"10.1007\/978-3-642-40084-1_5"},{"key":"221_CR108","unstructured":"Thaler, J., Roberts, M., Mitzenmacher, M., Pfister, H.: Verifiable computation with massively parallel interactive proofs. CoRR, abs\/1202.1350 (2012)"},{"key":"221_CR109","doi-asserted-by":"crossref","unstructured":"Valiant, P.: Incrementally verifiable computation or proofs of knowledge imply time\/space efficiency. In: Proceedings of the 5th Theory of Cryptography Conference, TCC\u00a0\u201908, pp. 1\u201318 (2008)","DOI":"10.1007\/978-3-540-78524-8_1"},{"issue":"1","key":"221_CR110","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1109\/TIT.2009.2034881","volume":"56","author":"F Vercauteren","year":"2010","unstructured":"Vercauteren, F.: Optimal pairings. IEEE Trans. Inf. Theory 56(1), 455\u2013461 (2010)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"1","key":"221_CR111","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/PL00003816","volume":"12","author":"PC Oorschot van","year":"1999","unstructured":"van Oorschot, P.C., Wiener, M.J.: Parallel collision search with cryptanalytic applications. J. Cryptol. 12(1), 1\u201328 (1999)","journal-title":"J. Cryptol."},{"key":"221_CR112","doi-asserted-by":"crossref","DOI":"10.1201\/9781420071474","volume-title":"Elliptic Curves: Number Theory and Cryptography","author":"LC Washington","year":"2008","unstructured":"Washington, L.C.: Elliptic Curves: Number Theory and Cryptography, 2nd edn. Chapman & Hall\/CRC, Boca Raton (2008)","edition":"2"},{"key":"221_CR113","doi-asserted-by":"crossref","unstructured":"Wahby, R.S., Setty, S., Ren, Z., Blumberg, A.J., Walfish, M.: Efficient RAM and control flow in verifiable outsourced computation. In: Proceedings of the 22nd Network and Distributed System Security Symposium, NDSS\u00a0\u201915 (2015)","DOI":"10.14722\/ndss.2015.23097"},{"key":"221_CR114","doi-asserted-by":"crossref","unstructured":"Zhang, Y., Papamanthou, C., Katz, J.: Alitheia: Towards practical verifiable graph processing. In: Proceedings of the 21st ACM Conference on Computer and Communications Security, CCS \u201914, pp. 856\u2013867 (2014)","DOI":"10.1145\/2660267.2660354"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0221-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0221-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0221-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,10]],"date-time":"2025-06-10T22:53:47Z","timestamp":1749596027000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0221-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,10,4]]},"references-count":114,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,12]]}},"alternative-id":["221"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0221-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,10,4]]}}}