{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:41:55Z","timestamp":1767339715455,"version":"3.37.3"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,7,30]],"date-time":"2020-07-30T00:00:00Z","timestamp":1596067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,7,30]],"date-time":"2020-07-30T00:00:00Z","timestamp":1596067200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ALAMBIC"],"award-info":[{"award-number":["ALAMBIC"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,1]]},"DOI":"10.1007\/s00453-020-00750-2","type":"journal-article","created":{"date-parts":[[2020,7,30]],"date-time":"2020-07-30T11:28:10Z","timestamp":1596108490000},"page":"72-115","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Privately Outsourcing Exponentiation to a Single Server: Cryptanalysis and Optimal Constructions"],"prefix":"10.1007","volume":"83","author":[{"given":"C\u00e9line","family":"Chevalier","sequence":"first","affiliation":[]},{"given":"Fabien","family":"Laguillaumie","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2113-3967","authenticated-orcid":false,"given":"Damien","family":"Vergnaud","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,7,30]]},"reference":[{"key":"750_CR1","unstructured":"Albrecht, M., Bai, S., Cad\u00e9, D., Pujol, X., Stehl\u00e9, D.: fplll-4.0, a floating-point LLL implementation. http:\/\/perso.ens-lyon.fr\/damien.stehle"},{"key":"750_CR2","unstructured":"Ateniese, G., Burns, R.C., Curtmola, R., Herring, J., Kissner, L., Peterson, Z.N.J., Song, D.X.: Provable data possession at untrusted stores. In: Ning, P., De Capitani di V., Sabrina, S., Paul F. (eds.), Proceedings of the 2007 ACM Conference on Computer and Communications Security, CCS 2007, Alexandria, Virginia, USA, October 28\u201331, 2007, ACM, pp. 598\u2013609 (2007)"},{"issue":"4","key":"750_CR3","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/s00145-004-0229-5","volume":"18","author":"RM Avanzi","year":"2005","unstructured":"Avanzi, R.M.: The complexity of certain multi-exponentiation techniques in cryptography. J. Cryptol. 18(4), 357\u2013373 (2005)","journal-title":"J. Cryptol."},{"issue":"1","key":"750_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02579403","volume":"6","author":"L Babai","year":"1986","unstructured":"Babai, L.: On Lov\u00e1sz\u2019 lattice reduction and the nearest lattice point problem. Combinatorica 6(1), 1\u201313 (1986)","journal-title":"Combinatorica"},{"key":"750_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-55220-5_1","volume-title":"Advances in Cryptology - EUROCRYPT 2014","author":"R Barbulescu","year":"2014","unstructured":"Barbulescu, R., Gaudry, P., Joux, A., Thom\u00e9, E.: A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic. In: Nguyen, P.Q., Oswald, E. (eds.) Advances in Cryptology - EUROCRYPT 2014. Lecture Notes in Computer Science, vol. 8441, pp. 1\u201316. Springer, Heidelberg, Germany (2014)"},{"key":"750_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1007\/3-540-45682-1_30","volume-title":"Advances in Cryptology\u2014ASIACRYPT 2001","author":"D Boneh","year":"2001","unstructured":"Boneh, D., Lynn, B., Shacham, H.: Short signatures from the Weil pairing. In: Boyd, C. (ed.) Advances in Cryptology\u2014ASIACRYPT 2001. Lecture Notes in Computer Science, vol. 2248, pp. 514\u2013532. Gold Coast, Springer, Heidelberg (2001)"},{"issue":"4","key":"750_CR7","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1007\/s00145-004-0314-9","volume":"17","author":"D Boneh","year":"2004","unstructured":"Boneh, D., Lynn, B., Shacham, H.: Short signatures from the Weil pairing. J. Cryptol. 17(4), 297\u2013319 (2004)","journal-title":"J. Cryptol."},{"key":"750_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1007\/BFb0054129","volume-title":"Advances in Cryptology\u2014EUROCRYPT\u201998","author":"V Boyko","year":"1998","unstructured":"Boyko, V., Peinado, M., Venkatesan, R.: Speeding up discrete log and factoring based schemes via precomputations. In: Nyberg, K. (ed.) Advances in Cryptology\u2014EUROCRYPT\u201998. Lecture Notes in Computer Science, vol. 1403, pp. 221\u2013235. Springer, Espoo (1998)"},{"key":"750_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1007\/3-540-47555-9_18","volume-title":"Advances in Cryptology\u2014EUROCRYPT\u201992","author":"EF Brickell","year":"1993","unstructured":"Brickell, E.F., Gordon, D.M., McCurley, K.S., Wilson, D.B.: Fast exponentiation with precomputation (extended abstract). In: Rueppel, R.A. (ed.) Advances in Cryptology\u2014EUROCRYPT\u201992. Lecture Notes in Computer Science, vol. 658, pp. 200\u2013207. Springer, Heidelberg (1993)"},{"key":"750_CR10","doi-asserted-by":"crossref","unstructured":"Canard, S., Devigne, J., Sanders, O.: Delegating a pairing can be both secure and efficient. In: Boureanu, I., Owesarski, P., Vaudenay, S. (eds.), ACNS 14: 12th International Conference on Applied Cryptography and Network Security, Lecture Notes in Computer Science, Springer, Heidelberg, vol. 8479, pp. 549\u2013565 (2014)","DOI":"10.1007\/978-3-319-07536-5_32"},{"key":"750_CR11","doi-asserted-by":"crossref","unstructured":"Cavallo, B., Di Crescenzo, G., Kahrobaei, D., Shpilrain, V.: Efficient and secure delegation of group exponentiation to a single server. In: Radio Frequency Identification. Security and Privacy Issues - 11th International Workshop, RFIDsec 2015, LNCS, pp. 156\u2013173 (2015)","DOI":"10.1007\/978-3-319-24837-0_10"},{"key":"750_CR12","doi-asserted-by":"crossref","unstructured":"Chen, X., Li, J., Ma, J., Tang, Q., Lou, W.: New algorithms for secure outsourcing of modular exponentiations. In: Foresti, S., Yung, M., Martinelli, F. (eds.) ESORICS 2012: 17th European Symposium on Research in Computer Security, Lecture Notes in Computer Science, Springer, Heidelberg, vol. 7459 pp. 541\u2013556 (2012)","DOI":"10.1007\/978-3-642-33167-1_31"},{"key":"750_CR13","doi-asserted-by":"crossref","unstructured":"Chevalier, C., Laguillaumie, F., Vergnaud, D.: Privately outsourcing exponentiation to a single server: Cryptanalysis and optimal constructions. In: Askoxylakis, I.G., Ioannidis, S., Katsikas, S.K., Meadows, C.A., (eds.) ESORICS 2016: 21st European Symposium on Research in Computer Security, Part I, Lecture Notes in Computer Science, Springer, Heidelberg, vol. 9878, pp. 261\u2013278 (2016)","DOI":"10.1007\/978-3-319-45744-4_13"},{"key":"750_CR14","doi-asserted-by":"crossref","unstructured":"Chevallier-Mames, B., Coron, J., McCullagh, N., Naccache, D., Scott, M.: Secure delegation of elliptic-curve pairing. In: Smart Card Research and Advanced Application, 9th IFIP WG 8.8\/11.2 International Conference, CARDIS 2010, LNCS, Springer, vol. 6035, pp. 24\u201335 (2010)","DOI":"10.1007\/978-3-642-12510-2_3"},{"key":"750_CR15","doi-asserted-by":"crossref","unstructured":"Coppersmith, D.: Finding a small root of a bivariate integer equation; factoring with high bits known. In: Maurer, U.M. (ed.) Advances in Cryptology\u2014EUROCRYPT\u201996, Lecture Notes in Computer Science, Springer, vol. 1070, pp. 178\u2013189 (1996)","DOI":"10.1007\/3-540-68339-9_16"},{"key":"750_CR16","doi-asserted-by":"crossref","unstructured":"Coppersmith, D.: Finding a small root of a univariate modular equation. In: Maurer, U.M. (ed.) Advances in Cryptology\u2014EUROCRYPT\u201996, Lecture Notes in Computer Science, Springer, Heidelberg, vol. 1070, pp. 155\u2013165 (1996)","DOI":"10.1007\/3-540-68339-9_14"},{"key":"750_CR17","doi-asserted-by":"crossref","unstructured":"Di Crescenzo, G., Khodjaeva, M., Kahrobaei, D., Shpilrain, V.: Secure delegation to a single malicious server: Exponentiation in RSA-type groups. In: 7th IEEE Conference on Communications and Network Security, CNS 2019, Washington, DC, USA, June 10\u201312, 2019, pp. 1\u20139. IEEE (2019)","DOI":"10.1109\/CNS.2019.8802691"},{"key":"750_CR18","doi-asserted-by":"crossref","unstructured":"de Rooij, P.: Efficient exponentiation using precomputation and vector addition chains. In: De Santis, A., (ed.) Advances in Cryptology\u2014EUROCRYPT\u201994, Lecture Notes in Computer Science, Perugia, Italy, Springer, Heidelberg, Germany, vol. 950, pp. 389\u2013399 (1995)","DOI":"10.1007\/BFb0053453"},{"issue":"1","key":"750_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s001459900016","volume":"10","author":"P de Rooij","year":"1997","unstructured":"de Rooij, P.: On Schnorr\u2019s preprocessing for digital signature schemes. J. Cryptol. 10(1), 1\u201316 (1997)","journal-title":"J. Cryptol."},{"key":"750_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jcss.2016.11.005","volume":"90","author":"Y Ding","year":"2017","unstructured":"Ding, Y., Xu, Z., Ye, J., Choo, K.-K.R.: Secure outsourcing of modular exponentiations under single untrusted programme model. J. Comput. Syst. Sci. 90, 1\u201313 (2017)","journal-title":"J. Comput. Syst. Sci."},{"key":"750_CR21","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139012843","volume-title":"Mathematics of Public Key Cryptography","author":"SD Galbraith","year":"2012","unstructured":"Galbraith, SD.: Mathematics of Public Key Cryptography. Cambridge University Press, Cambridge (2012)"},{"key":"750_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1007\/3-540-44647-8_11","volume-title":"Advances in Cryptology - CRYPTO 2001","author":"RP Gallant","year":"2001","unstructured":"Gallant, R.P., Lambert, R.J., Vanstone, S.A.: Faster point multiplication on elliptic curves with efficient endomorphisms. In: Kilian, J. (ed.) Advances in Cryptology - CRYPTO 2001. Lecture Notes in Computer Science, vol. 2139, pp. 190\u2013200. Springer, Heidelberg (2001)"},{"key":"750_CR23","doi-asserted-by":"crossref","unstructured":"Guillevic, A., Vergnaud, D.: Algorithms for outsourcing pairing computation. In: Joye, M., Moradi, A. (eds.) Smart Card Research and Advanced Applications\u201413th International Conference, CARDIS 2014, Paris, France, November 5-7, 2014. Revised Selected Papers, Lecture Notes in Computer Science, Springer, vol. 8968 pp. 193\u2013211 (2014)","DOI":"10.1007\/978-3-319-16763-3_12"},{"key":"750_CR24","unstructured":"Herrmann, M.: Lattice-based Cryptanalysis using Unravelled Linearization. PhD Thesis, Ruhr-Universit\u00e4t Bochum (2011)"},{"key":"750_CR25","doi-asserted-by":"crossref","unstructured":"Hohenberger, S., Lysyanskaya, A.: How to securely outsource cryptographic computations. In: Kilian, J. (ed.) TCC 2005: 2nd Theory of Cryptography Conference, Lecture Notes in Computer Science, Cambridge, Springer, Heidelberg, Germany, vol. 3378, pp. 264\u2013282 (2005)","DOI":"10.1007\/978-3-540-30576-7_15"},{"key":"750_CR26","doi-asserted-by":"crossref","unstructured":"Howgrave-Graham, N.: Finding small roots of univariate modular equations revisited. In: Darnell, M. (ed.) 6th IMA International Conference on Cryptography and Coding, Lecture Notes in Computer Science, Cirencester, UK, Springer, Heidelberg, Germany, vol. 1355, pp. 131\u2013142 (1997)","DOI":"10.1007\/BFb0024458"},{"key":"750_CR27","unstructured":"Juels, A., Kaliski, B.S. Jr.: Pors: proofs of retrievability for large files. In: Ning et al. [37], pp. 584\u2013597"},{"key":"750_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1007\/BFb0054124","volume-title":"Advances in Cryptology\u2013EUROCRYPT\u201998","author":"CS Jutla","year":"1998","unstructured":"Jutla, C.S.: On finding small solutions of modular multivariate polynomial equations. In: Nyberg, K. (ed.) Advances in Cryptology\u2013EUROCRYPT\u201998. Lecture Notes in Computer Science, vol. 1403, pp. 158\u2013170. Springer, Heidelberg (1998)"},{"key":"750_CR29","first-page":"1","volume":"15","author":"MS Kiraz","year":"2015","unstructured":"Kiraz, MS., Uzunkol, O.: Efficient and verifiable algorithms for secure outsourcing of cryptographic computations. Int. J. Inf. Secur. 15, 1\u201319 (2015)","journal-title":"Int. J. Inf. Secur."},{"key":"750_CR30","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01457454","volume":"261","author":"AK Lenstra","year":"1982","unstructured":"Lenstra, A.K., Lenstra Jr., H.W., Lov\u00e1sz, L.: Factoring polynomials with rational coefficients. Math. Ann. 261, 515\u2013534 (1982)","journal-title":"Math. Ann."},{"key":"750_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1007\/3-540-48658-5_11","volume-title":"Advances in Cryptology\u2014CRYPTO\u201994","author":"CH Lim","year":"1994","unstructured":"Lim, C.H., Lee, P.J.: More flexible exponentiation with precomputation. In: Desmedt, Y. (ed.) Advances in Cryptology\u2014CRYPTO\u201994. Lecture Notes in Computer Science, vol. 839, pp. 95\u2013107. Springer, Heidelberg, Germany (1994)"},{"issue":"8","key":"750_CR32","first-page":"1194","volume":"62","author":"T Mefenza","year":"2019","unstructured":"Mefenza, T., Vergnaud, D.: Cryptanalysis of server-aided RSA protocols with private-key splitting. Comput. J. 62(8), 1194\u20131213 (2019)","journal-title":"Comput. J."},{"key":"750_CR33","doi-asserted-by":"crossref","unstructured":"Micali, S., Pass, R., Rosen, A.: Input-indistinguishable computation. In: 47th Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, Berkeley, CA, USA, pp. 367\u2013378 (2006)","DOI":"10.1109\/FOCS.2006.43"},{"key":"750_CR34","unstructured":"M\u00f6ller, B.: Algorithms for multi-exponentiation. In: Vaudenay, S., Youssef, A.M. (eds.) SAC 2001: 8th Annual International Workshop on Selected Areas in Cryptography, Lecture Notes in Computer Science, Toronto, Ontario, Canada, Springer, Heidelberg, Germany, vol. 2259, pp. 165\u2013180 (2001)"},{"key":"750_CR35","unstructured":"Nguyen, P.Q., Shparlinski, I.E., Stern, J.: Distribution of modular sums and the security of server aided exponentiation. In: Workshop on Comp. Number Theory and Crypt, pp. 1\u201316 (1999)"},{"key":"750_CR36","doi-asserted-by":"crossref","unstructured":"Nguyen, P.Q., Stehl\u00e9, D.: Floating-point LLL revisited. In: Cramer, R. (ed.) Advances in Cryptology\u2014EUROCRYPT 2005, Lecture Notes in Computer Science, Aarhus, Denmark, Springer, Heidelberg, Germany, vol. 3494, pp. 215\u2013233 (2005)","DOI":"10.1007\/11426639_13"},{"key":"750_CR38","unstructured":"Sage Mathematics Software (2012) http:\/\/www.sagemath.org"},{"issue":"3","key":"750_CR39","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/BF00196725","volume":"4","author":"C-P Schnorr","year":"1991","unstructured":"Schnorr, C.-P.: Efficient signature generation by smart cards. J. Cryptol. 4(3), 161\u2013174 (1991)","journal-title":"J. Cryptol."},{"key":"750_CR40","doi-asserted-by":"crossref","unstructured":"Shacham, H., Waters, B.: Compact proofs of retrievability. In: Pieprzyk, J. (ed.) Advances in Cryptology \u2013 ASIACRYPT 2008, Lecture Notes in Computer Science, Melbourne, Australia, Springer, Heidelberg, Germany, vol. 5350, pp. 90\u2013107 (2008)","DOI":"10.1007\/978-3-540-89255-7_7"},{"key":"750_CR41","unstructured":"Shah, M.A., Baker, M., Mogul, J.C., Swaminathan, R.: Auditing to keep online storage services honest. In: Hunt, G.C. (ed.) Proceedings of HotOS\u201907: 11th Workshop on Hot Topics in Operating Systems, May 7\u20139, 2005, San Diego, California, USA, USENIX Association (2007)"},{"key":"750_CR42","doi-asserted-by":"crossref","unstructured":"Shoup, V.: Lower bounds for discrete logarithms and related problems. In: Fumy, Walter (ed.) Advances in Cryptology\u2014EUROCRYPT\u201997, Lecture Notes in Computer Science, Konstanz, Germany, Springer, Heidelberg, Germany, vol. 1233, pp. 256\u2013266 (1997)","DOI":"10.1007\/3-540-69053-0_18"},{"key":"750_CR43","first-page":"15","volume":"637","author":"Benjamin Smith","year":"2015","unstructured":"Smith, B.: Easy scalar decompositions for efficient scalar multiplication on elliptic curves and genus 2 Jacobians. Contemp. Math. Ser. 637, 15 (2015)","journal-title":"Contemp. Math. Ser."},{"key":"750_CR44","first-page":"806","volume":"71","author":"E.G. Straus","year":"1964","unstructured":"Straus, E.G.: Problems and solutions: addition chains of vectors. Am. Math. Mon. 71, 806\u2013808 (1964)","journal-title":"Am. Math. Mon."},{"key":"750_CR45","doi-asserted-by":"crossref","unstructured":"Wang, Y., Wu, Q., Wong, D.S., Qin, B., Chow, S.S.M., Liu, Z., Tan, X.: Securely outsourcing exponentiations with single untrusted program for cloud storage. In: Kutylowski, M., Vaidya, J. (eds.) ESORICS 2014: 19th European Symposium on Research in Computer Security, Part I, of Lecture Notes in Computer Science, Wroclaw, Poland, Springer, Heidelberg, Germany, vol. 8712, pp. 326\u2013343 (2014)","DOI":"10.1007\/978-3-319-11203-9_19"},{"issue":"1","key":"750_CR46","first-page":"167","volume":"8","author":"I Yie","year":"2005","unstructured":"Yie, I.: Cryptanalysis of Elgamal type digital signature schemes using integer decomposition. Trends Math. 8(1), 167\u2013175 (2005)","journal-title":"Trends Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00750-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-020-00750-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00750-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,29]],"date-time":"2021-07-29T23:32:57Z","timestamp":1627601577000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-020-00750-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,30]]},"references-count":45,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["750"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00750-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2020,7,30]]},"assertion":[{"value":"28 December 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 July 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 July 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}