{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,16]],"date-time":"2026-01-16T00:24:16Z","timestamp":1768523056868,"version":"3.49.0"},"publisher-location":"Cham","reference-count":36,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030519377","type":"print"},{"value":"9783030519384","type":"electronic"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-51938-4_11","type":"book-chapter","created":{"date-parts":[[2020,7,4]],"date-time":"2020-07-04T11:02:54Z","timestamp":1593860574000},"page":"214-235","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["A SAT-Based Approach for Index Calculus on Binary Elliptic Curves"],"prefix":"10.1007","author":[{"given":"Monika","family":"Trimoska","sequence":"first","affiliation":[]},{"given":"Sorina","family":"Ionica","sequence":"additional","affiliation":[]},{"given":"Gilles","family":"Dequen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,7,5]]},"reference":[{"key":"11_CR1","unstructured":"Audemard, G., Simon, L.: Predicting learnt clauses quality in modern SAT solvers. In: IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena, California, USA, 11\u201317 July 2009, pp. 399\u2013404 (2009)"},{"issue":"3","key":"11_CR2","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1515\/JMC.2009.009","volume":"3","author":"L Bettale","year":"2009","unstructured":"Bettale, L., Faug\u00e8re, J., Perret, L.: Hybrid approach for solving multivariate systems over finite fields. J. Math. Cryptol. 3(3), 177\u2013197 (2009). \nhttps:\/\/doi.org\/10.1515\/JMC.2009.009","journal-title":"J. Math. Cryptol."},{"key":"11_CR3","volume-title":"Handbook of Satisfiability, Frontiers in Artificial Intelligence and Applications","year":"2009","unstructured":"Biere, A., Heule, M., van Maaren, H., Walsh, T. (eds.): Handbook of Satisfiability, Frontiers in Artificial Intelligence and Applications, vol. 185. IOS Press, Amsterdam (2009)"},{"issue":"3\u20134","key":"11_CR4","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1006\/jsco.1996.0125","volume":"24","author":"W Bosma","year":"1997","unstructured":"Bosma, W., Cannon, J., Playoust, C.: The Magma algebra system. I. The user language. J. Symbolic Comput. 24(3\u20134), 235\u2013265 (1997). \nhttps:\/\/doi.org\/10.1006\/jsco.1996.0125","journal-title":"J. Symbolic Comput."},{"key":"11_CR5","unstructured":"Bouillaguet, C.: LibFES-lite (2016). \nhttps:\/\/github.com\/cbouilla\/libfes-lite"},{"key":"11_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/978-3-662-43414-7_11","volume-title":"Selected Areas in Cryptography \u2013 SAC 2013","author":"C Bouillaguet","year":"2014","unstructured":"Bouillaguet, C., Cheng, C.-M., Chou, T., Niederhagen, R., Yang, B.-Y.: Fast exhaustive search for quadratic systems in $$\\mathbb{F}_{2}$$ on FPGAs. In: Lange, T., Lauter, K., Lison\u011bk, P. (eds.) SAC 2013. LNCS, vol. 8282, pp. 205\u2013222. Springer, Heidelberg (2014). \nhttps:\/\/doi.org\/10.1007\/978-3-662-43414-7_11"},{"issue":"7","key":"11_CR7","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1145\/368273.368557","volume":"5","author":"M Davis","year":"1962","unstructured":"Davis, M., Logemann, G., Loveland, D.W.: A machine program for theorem-proving. Commun. ACM 5(7), 394\u2013397 (1962)","journal-title":"Commun. ACM"},{"issue":"1","key":"11_CR8","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1112\/S0010437X10005075","volume":"147","author":"C Diem","year":"2011","unstructured":"Diem, C.: On the discrete logarithm problem in elliptic curves. Compositio Mathematica 147(1), 75\u2013104 (2011). \nhttps:\/\/doi.org\/10.1112\/S0010437X10005075","journal-title":"Compositio Mathematica"},{"issue":"6","key":"11_CR9","doi-asserted-by":"publisher","first-page":"1281","DOI":"10.2140\/ant.2013.7.1281","volume":"7","author":"C Diem","year":"2013","unstructured":"Diem, C.: On the discrete logarithm problem in elliptic curves II. Algebra Number Theory 7(6), 1281\u20131323 (2013)","journal-title":"Algebra Number Theory"},{"key":"11_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1007\/978-3-642-55220-5_3","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2014","author":"J-C Faug\u00e8re","year":"2014","unstructured":"Faug\u00e8re, J.-C., Huot, L., Joux, A., Renault, G., Vitse, V.: Symmetrized summation polynomials: using small order torsion points to speed up elliptic curve index calculus. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 40\u201357. Springer, Heidelberg (2014). \nhttps:\/\/doi.org\/10.1007\/978-3-642-55220-5_3"},{"issue":"1\u20133","key":"11_CR11","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/S0022-4049(99)00005-5","volume":"139","author":"JC Faug\u00e8re","year":"1999","unstructured":"Faug\u00e8re, J.C.: A new efficient algorithm for computing Gr\u00f6bner basis (F4). J. Pure Appl. Algebra 139(1\u20133), 61\u201388 (1999)","journal-title":"J. Pure Appl. Algebra"},{"key":"11_CR12","unstructured":"Faug\u00e8re, J.C.: A new efficient algorithm for computing Gr\u00f6bner basis without reduction to zero (F5). In: Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation. ISSAC 2002, pp. 75\u201383. ACM, New York (2002). \nhttp:\/\/doi.acm.org\/10.1145\/780506.780516"},{"key":"11_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/978-3-642-29011-4_4","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2012","author":"J-C Faug\u00e8re","year":"2012","unstructured":"Faug\u00e8re, J.-C., Perret, L., Petit, C., Renault, G.: Improving the complexity of index calculus algorithms in elliptic curves over binary fields. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 27\u201344. Springer, Heidelberg (2012). \nhttps:\/\/doi.org\/10.1007\/978-3-642-29011-4_4"},{"key":"11_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1007\/978-3-319-13039-2_24","volume-title":"Progress in Cryptology \u2013 INDOCRYPT 2014","author":"SD Galbraith","year":"2014","unstructured":"Galbraith, S.D., Gebregiyorgis, S.W.: Summation polynomial algorithms for elliptic curves in characteristic two. In: Meier, W., Mukhopadhyay, D. (eds.) INDOCRYPT 2014. LNCS, vol. 8885, pp. 409\u2013427. Springer, Cham (2014). \nhttps:\/\/doi.org\/10.1007\/978-3-319-13039-2_24"},{"issue":"12","key":"11_CR15","doi-asserted-by":"publisher","first-page":"1690","DOI":"10.1016\/j.jsc.2008.08.005","volume":"44","author":"P Gaudry","year":"2009","unstructured":"Gaudry, P.: Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem. J. Symb. Comput. 44(12), 1690\u20131702 (2009). \nhttps:\/\/doi.org\/10.1016\/j.jsc.2008.08.005","journal-title":"J. Symb. Comput."},{"key":"11_CR16","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1016\/j.ipl.2018.07.001","volume":"139","author":"D G\u00e9rault","year":"2018","unstructured":"G\u00e9rault, D., Lafourcade, P., Minier, M., Solnon, C.: Revisiting AES related-key differential attacks with constraint programming. Inf. Process. Lett. 139, 24\u201329 (2018). \nhttps:\/\/doi.org\/10.1016\/j.ipl.2018.07.001","journal-title":"Inf. Process. Lett."},{"key":"11_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1007\/978-3-642-31424-7_31","volume-title":"Computer Aided Verification","author":"C-S Han","year":"2012","unstructured":"Han, C.-S., Jiang, J.-H.R.: When boolean satisfiability meets gaussian elimination in a simplex way. In: Madhusudan, P., Seshia, S.A. (eds.) CAV 2012. LNCS, vol. 7358, pp. 410\u2013426. Springer, Heidelberg (2012). \nhttps:\/\/doi.org\/10.1007\/978-3-642-31424-7_31"},{"key":"11_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1007\/978-3-642-29011-4_3","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2012","author":"A Joux","year":"2012","unstructured":"Joux, A., Vitse, V.: Cover and decomposition index calculus on elliptic curves made practical. Application to a previously unreachable curve over $$\\mathbb{F}_{p}^{6}$$. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 9\u201326. Springer, Heidelberg (2012). \nhttps:\/\/doi.org\/10.1007\/978-3-642-29011-4_3"},{"key":"11_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-319-76620-1_1","volume-title":"Number-Theoretic Methods in Cryptology","author":"A Joux","year":"2018","unstructured":"Joux, A., Vitse, V.: A crossbred algorithm for solving boolean polynomial systems. In: Kaczorowski, J., Pieprzyk, J., Pomyka\u0142a, J. (eds.) NuTMiC 2017. LNCS, vol. 10737, pp. 3\u201321. Springer, Cham (2018). \nhttps:\/\/doi.org\/10.1007\/978-3-319-76620-1_1"},{"key":"11_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/3-540-46766-1_22","volume-title":"Advances in Cryptology \u2014 CRYPTO \u201991","author":"N Koblitz","year":"1992","unstructured":"Koblitz, N.: CM-curves with good cryptographic properties. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 279\u2013287. Springer, Heidelberg (1992). \nhttps:\/\/doi.org\/10.1007\/3-540-46766-1_22"},{"key":"11_CR21","doi-asserted-by":"publisher","unstructured":"Laitinen, T., Junttila, T., Niemela, I.: Equivalence class based parity reasoning with DPLL(XOR). In: Czumaj, A (ed.) 2011 IEEE 23rd International Conference on Tools with Artificial Intelligence, pp. 649\u2013658, November 2011. \nhttps:\/\/doi.org\/10.1109\/ICTAI.2011.103","DOI":"10.1109\/ICTAI.2011.103"},{"key":"11_CR22","unstructured":"Laitinen, T., Junttila, T.A., Niemel\u00e4, I.: Conflict-driven XOR-clause learning (extended version). CoRR abs\/1407.6571 (2014). \nhttp:\/\/arxiv.org\/abs\/1407.6571"},{"key":"11_CR23","series-title":"Lecture Notes in Mathematics","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1007\/BFb0091537","volume-title":"The development of the number field sieve","author":"AK Lenstra","year":"1993","unstructured":"Lenstra, A.K., Lenstra, H.W., Manasse, M.S., Pollard, J.M.: The number field sieve. In: Lenstra, A.K., Lenstra, H.W. (eds.) The development of the number field sieve. LNM, vol. 1554, pp. 11\u201342. Springer, Heidelberg (1993). \nhttps:\/\/doi.org\/10.1007\/BFb0091537"},{"key":"11_CR24","doi-asserted-by":"publisher","unstructured":"Lokshtanov, D., Mikhailin, I., Paturi, R., Pudl\u00e1k, P.: Beating brute force for (quantified) satisfiability of circuits of bounded treewidth. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 2018, New Orleans, LA, USA, 7\u201310 January 2018, pp. 247\u2013261 (2018). \nhttps:\/\/doi.org\/10.1137\/1.9781611975031.18","DOI":"10.1137\/1.9781611975031.18"},{"issue":"1","key":"11_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/PL00003816","volume":"12","author":"PC van Oorschot","year":"1999","unstructured":"van Oorschot, P.C., Wiener, M.J.: Parallel collision search with cryptanalytic applications. J. Cryptol. 12(1), 1\u201328 (1999). \nhttps:\/\/doi.org\/10.1007\/PL00003816","journal-title":"J. Cryptol."},{"key":"11_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1007\/978-3-642-34961-4_28","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2012","author":"C Petit","year":"2012","unstructured":"Petit, C., Quisquater, J.-J.: On polynomial systems arising from a Weil descent. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 451\u2013466. Springer, Heidelberg (2012). \nhttps:\/\/doi.org\/10.1007\/978-3-642-34961-4_28"},{"key":"11_CR27","unstructured":"Semaev, I.A.: Summation polynomials and the discrete logarithm problem on elliptic curves. IACR Cryptology ePrint Archive 2004, 31 (2004). \nhttp:\/\/eprint.iacr.org\/2004\/031"},{"key":"11_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1007\/978-3-642-42001-6_7","volume-title":"Number Theory and Cryptography","author":"M Shantz","year":"2013","unstructured":"Shantz, M., Teske, E.: Solving the elliptic curve discrete logarithm problem using Semaev polynomials, Weil descent and Gr\u00f6bner basis methods \u2013 an experimental study. In: Fischlin, M., Katzenbeisser, S. (eds.) Number Theory and Cryptography. LNCS, vol. 8260, pp. 94\u2013107. Springer, Heidelberg (2013). \nhttps:\/\/doi.org\/10.1007\/978-3-642-42001-6_7"},{"key":"11_CR29","unstructured":"Silva, J.P.M., Sakallah, K.A.: Conflict analysis in search algorithms for satisfiability. In: ICTAI, pp. 467\u2013469. IEEE Computer Society (1996)"},{"key":"11_CR30","unstructured":"Soos, M.: Enhanced Gaussian elimination in DPLL-based SAT solvers. In: Pragmatics of SAT (2010)"},{"key":"11_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1007\/978-3-642-02777-2_24","volume-title":"Theory and Applications of Satisfiability Testing - SAT 2009","author":"M Soos","year":"2009","unstructured":"Soos, M., Nohl, K., Castelluccia, C.: Extending SAT solvers to cryptographic problems. In: Kullmann, O. (ed.) SAT 2009. LNCS, vol. 5584, pp. 244\u2013257. Springer, Heidelberg (2009). \nhttps:\/\/doi.org\/10.1007\/978-3-642-02777-2_24"},{"key":"11_CR32","unstructured":"S\u00f6rensson, N., E\u00e9n, N.: A SAT solver with conflict-clause minimization. In: Proceedings of the Theory and Applications of Satisfiability Testing (2005)"},{"key":"11_CR33","unstructured":"Trimoska, M., Ionica, S., Dequen, G.: Parallel Collision Search Implementation (2019). \nhttps:\/\/github.com\/mtrimoska\/PCS"},{"key":"11_CR34","unstructured":"Trimoska, M., Ionica, S., Dequen, G.: EC Index Calculus Benchmarks (2020). \nhttps:\/\/github.com\/mtrimoska\/EC-Index-Calculus-Benchmarks"},{"key":"11_CR35","unstructured":"Trimoska, M., Ionica, S., Dequen, G.: Parity (XOR) reasoning for the index calculus attack. CoRR abs\/2001.11229 (2020). \nhttps:\/\/arxiv.org\/abs\/2001.11229"},{"key":"11_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/978-3-642-41383-4_8","volume-title":"Advances in Information and Computer Security","author":"Y-J Huang","year":"2013","unstructured":"Huang, Y.-J., Petit, C., Shinohara, N., Takagi, T.: Improvement of Faug\u00e8re et al.\u2019s method to solve ECDLP. In: Sakiyama, K., Terada, M. (eds.) IWSEC 2013. LNCS, vol. 8231, pp. 115\u2013132. Springer, Heidelberg (2013). \nhttps:\/\/doi.org\/10.1007\/978-3-642-41383-4_8"}],"container-title":["Lecture Notes in Computer Science","Progress in Cryptology - AFRICACRYPT 2020"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-51938-4_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,7,8]],"date-time":"2020-07-08T23:12:04Z","timestamp":1594249924000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-51938-4_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030519377","9783030519384"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-51938-4_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"5 July 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"AFRICACRYPT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Cryptology in Africa","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Cairo","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Egypt","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20 July 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 July 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"africacrypt2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/africacrypt2020.org\/index.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"easychair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"49","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"21","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"43% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"4.2","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"No","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"The conference was held virtually due to the COVID-19 pandemic.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}