{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,1]],"date-time":"2026-02-01T05:29:37Z","timestamp":1769923777138,"version":"3.49.0"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2024,8,5]],"date-time":"2024-08-05T00:00:00Z","timestamp":1722816000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,8,5]],"date-time":"2024-08-05T00:00:00Z","timestamp":1722816000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002835","name":"Chalmers University of Technology","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100002835","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptogr Eng"],"published-print":{"date-parts":[[2024,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Digital signatures are widely deployed to authenticate the source of incoming information, or to certify data integrity. Common signature verification procedures return a decision (accept\/reject) only at the very end of the execution. If interrupted prematurely, however, the verification process cannot infer any meaningful information about the validity of the given signature. This limitation is due to the algorithm design solely, and it is not inherent to signature verification. In this work, we provide a formal framework to extract information from prematurely interrupted signature verification, independently of why the process halts: we propose a generic verification procedure that progressively builds confidence on the final decision. Our transformation builds on a simple but powerful intuition and applies to a wide range of existing schemes considered to be post-quantum secure, including some lattice-based and multivariate equations based constructions. We demonstrate the feasibility of our approach through an implementation on off-the-shelf resource-constrained devices. In particular, an intensive testing activity has been conducted measuring the increase of performance on three IoT boards\u2014i.e., Arduino, Raspberry, and Espressif\u2014and a consumer-grade laptop. While the primary motivation of progressive verification is to mitigate unexpected interruptions, we show that verifiers can leverage it in two innovative ways. First, progressive verification can be used to intentionally adjust the soundness of the verification process. Second, our transformation splits verification into a computationally intensive offline set-up (run once), and an efficient online verification that is faster than the original algorithm. We conclude showing how to tweak our compiler for progressive verification to work on a wide range of signatures with properties, on three real-life use cases, and in combination with efficient verification.<\/jats:p>","DOI":"10.1007\/s13389-024-00358-0","type":"journal-article","created":{"date-parts":[[2024,8,5]],"date-time":"2024-08-05T03:11:46Z","timestamp":1722827506000},"page":"551-575","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Progressive and efficient verification for digital signatures: extensions and experimental results"],"prefix":"10.1007","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0956-1616","authenticated-orcid":false,"given":"Cecilia","family":"Boschini","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7274-6600","authenticated-orcid":false,"given":"Dario","family":"Fiore","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7804-6696","authenticated-orcid":false,"given":"Elena","family":"Pagnin","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0009-0002-1257-061X","authenticated-orcid":false,"given":"Luca","family":"Torresetti","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5689-8575","authenticated-orcid":false,"given":"Andrea","family":"Visconti","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,8,5]]},"reference":[{"key":"358_CR1","doi-asserted-by":"crossref","unstructured":"Albrecht, M.R., Curtis, B.R., Deo, A., Davidson, A., Player, R., Postlethwaite, E.W., Virdia, F., Wunderer, T.: Estimate all the LWE, NTRU schemes! in security and cryptography for networks SCN, LNCS (2018)","DOI":"10.1007\/978-3-319-98113-0_19"},{"key":"358_CR2","doi-asserted-by":"crossref","unstructured":"Armknecht, F., Walther, P., Tsudik, G., Beck, M., Strufe, T.: ProMACs: Progressive and resynchronizing macs for continuous efficient authentication of message streams. In: Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, pp. 211\u2013223 (2020)","DOI":"10.1145\/3372297.3423349"},{"key":"358_CR3","doi-asserted-by":"crossref","unstructured":"Backes, M., Fiore, D., Reischuk, R.M.: Verifiable delegation of computation on outsourced data. In: 2013 ACM SIGSAC CCS, pp. 863\u2013874. ACM (2013)","DOI":"10.1145\/2508859.2516681"},{"key":"358_CR4","doi-asserted-by":"crossref","unstructured":"Bendlin, R., Krehbiel, S., Peikert, C.: How to share a lattice trapdoor: threshold protocols for signatures and (H)IBE. In: ACNS (2013)","DOI":"10.1007\/978-3-642-38980-1_14"},{"key":"358_CR5","unstructured":"Bernstein, D.J.: A secure public-key signature system with extremely fast verification"},{"key":"358_CR6","doi-asserted-by":"crossref","unstructured":"Beullens, W.: Breaking rainbow takes a weekend on a laptop. In: Advances in Cryptology\u2014CRYPTO 2022, pp. 464\u2013479. Springer, Switzerland (2022)","DOI":"10.1007\/978-3-031-15979-4_16"},{"key":"358_CR7","doi-asserted-by":"crossref","unstructured":"Beullens, W.: Mayo: Practical post-quantum signatures from oil-and-vinegar maps. In: International Conference on Selected Areas in Cryptography, pp. 355\u2013376. Springer, New York (2022)","DOI":"10.1007\/978-3-030-99277-4_17"},{"key":"358_CR8","unstructured":"Beullens, W., Szepieniec, A., Vercauteren, F., Preneel, B.: LUOV: Signature scheme proposal for NIST PQC project (2019)"},{"key":"358_CR9","doi-asserted-by":"crossref","unstructured":"Boneh, D., Freeman, D.M.: Linearly homomorphic signatures over binary fields and new tools for lattice-based signatures. In: PKC, pp. 1\u201316. Springer, New York (2011)","DOI":"10.1007\/978-3-642-19379-8_1"},{"key":"358_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1007\/978-3-031-09234-3_22","volume-title":"Applied Cryptography and Network Security\u201320th International Conference, ACNS 2022, Rome, Italy, Proceedings","author":"C Boschini","year":"2022","unstructured":"Boschini, C., Fiore, D., Pagnin, E.: Progressive and efficient verification for digital signatures. In: Ateniese, G., Venturi, D. (eds.) Applied Cryptography and Network Security\u201320th International Conference, ACNS 2022, Rome, Italy, Proceedings. Lecture Notes in Computer Science, vol. 13269, pp. 440\u2013458. Springer, New York (2022)"},{"key":"358_CR11","doi-asserted-by":"crossref","unstructured":"Boyen, X.: Lattice mixing and vanishing trapdoors: a framework for fully secure short signatures and more. In: PKC, pp. 499\u2013517. Springer, New York (2010)","DOI":"10.1007\/978-3-642-13013-7_29"},{"key":"358_CR12","doi-asserted-by":"crossref","unstructured":"\u00c7al\u0131k, \u00c7., Dworkin, M., Dykas, N., Peralta, R.: Searching for best karatsuba recurrences. In: Analysis of Experimental Algorithms: Special Event. SEA$$^2$$ 2019, Kalamata, Greece, Revised Selected Papers, pp. 332\u2013342. Springer, New York (2019)","DOI":"10.1007\/978-3-030-34029-2_22"},{"key":"358_CR13","doi-asserted-by":"crossref","unstructured":"Cartor, R., Cartor, M., Lewis, M., Smith-Tone, D.: Iprainbow. In: Proceedings of Post-Quantum Cryptography: 13th International Workshop, PQCrypto 2022, Virtual Event, pp. 170\u2013184. Springer, New York (2022)","DOI":"10.1007\/978-3-031-17234-2_9"},{"key":"358_CR14","doi-asserted-by":"crossref","unstructured":"Cash, D., Hofheinz, D., Kiltz, E., Peikert, C.: Bonsai trees, or how to delegate a lattice basis. In: EUROCRYPT, Springer, New York (2010)","DOI":"10.1007\/978-3-642-13190-5_27"},{"key":"358_CR15","doi-asserted-by":"crossref","unstructured":"Catalano, D., Fiore, D., Warinschi, B.: Homomorphic signatures with efficient verification for polynomial functions. In: Advances in Cryptology\u2014CRYPTO (2014)","DOI":"10.1007\/978-3-662-44371-2_21"},{"key":"358_CR16","doi-asserted-by":"crossref","unstructured":"Chen, Y., Lombardi, A., Ma, F., Quach, W.: Does fiat-Shamir require a cryptographic hash function? In: Malkin, T., Peikert, C. (eds.) CRYPTO (2021)","DOI":"10.1007\/978-3-030-84259-8_12"},{"issue":"3","key":"358_CR17","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1007\/s13389-019-00210-w","volume":"10","author":"A De Piccoli","year":"2020","unstructured":"De Piccoli, A., Visconti, A., Rizzo, O.G.: Polynomial multiplication over binary finite fields: new upper bounds. J. Cryptogr. Eng. 10(3), 197\u2013210 (2020)","journal-title":"J. Cryptogr. Eng."},{"key":"358_CR18","unstructured":"Ding, J., Chen, M.-S., Petzoldt, A., Schmidt, D., Yang, B.-Y.: Rainbow. Available at https:\/\/csrc.nist.gov\/projects\/post-quantum-cryptography\/round-2-submissions. Accessed 21 Sept 2020"},{"key":"358_CR19","doi-asserted-by":"publisher","DOI":"10.1007\/11496137_12","volume-title":"Rainbow, a new multivariable polynomial signature scheme","author":"J Ding","year":"2005","unstructured":"Ding, J., Schmidt, D.: Rainbow, a new multivariable polynomial signature scheme. In ACNS, LNCS (2005)"},{"key":"358_CR20","doi-asserted-by":"crossref","unstructured":"Fiore, D., Mitrokotsa, A., Nizzardo, L., Pagnin, E.: Multi-key homomorphic authenticators. In: ASIACRYPT (2016)","DOI":"10.1007\/978-3-662-53890-6_17"},{"key":"358_CR21","doi-asserted-by":"crossref","unstructured":"Fischlin, M.: Progressive verification: The case of message authentication. In: International Conference on Cryptology in India, pp. 416\u2013429. Springer, New York (2003)","DOI":"10.1007\/978-3-540-24582-7_31"},{"key":"358_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1007\/978-3-540-78967-3_3","volume-title":"Proceedings on Advances in Cryptology\u2013EUROCRYPT","author":"N Gama","year":"2008","unstructured":"Gama, N., Nguyen, P.Q.: Predicting lattice reduction. In: Smart, N.P. (ed.) Proceedings on Advances in Cryptology\u2013EUROCRYPT. Lecture Notes in Computer Science, vol. 4965, pp. 31\u201351. Springer, New York (2008)"},{"key":"358_CR23","doi-asserted-by":"crossref","unstructured":"Gennaro, R., Gentry, C., Parno, B.: Non-interactive verifiable computing: Outsourcing computation to untrusted workers. In: CRYPTO (2010)","DOI":"10.1007\/978-3-642-14623-7_25"},{"key":"358_CR24","volume-title":"ACM STOC","author":"C Gentry","year":"2008","unstructured":"Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: Dwork, C. (ed.) ACM STOC. ACM, New York (2008)"},{"key":"358_CR25","doi-asserted-by":"crossref","unstructured":"Gorbunov, S., Vaikuntanathan, V., Wichs, D.: Leveled fully homomorphic signatures from standard lattices. In: STOC, pp. 469\u2013477. ACM (2015)","DOI":"10.1145\/2746539.2746576"},{"key":"358_CR26","doi-asserted-by":"crossref","unstructured":"Gorbunov, S., Vinayagamurthy, D.: Riding on asymmetry: Efficient ABE for branching programs. In: ASIACRYPT, LNCS (2015)","DOI":"10.1007\/978-3-662-48797-6_23"},{"key":"358_CR27","doi-asserted-by":"crossref","unstructured":"Katsumata, S., Yamada, S.: Group signatures without NIZK: from lattices in the standard model. In: Advances in Cryptology\u2014EUROCRYPT (2019)","DOI":"10.1007\/978-3-030-17659-4_11"},{"key":"358_CR28","unstructured":"Lamport, L.: Constructing digital signatures from a one-way function. In: Technical report, CSL-98, SRI International (1979)"},{"key":"358_CR29","doi-asserted-by":"crossref","unstructured":"Le, D.V., Kelkar, M., Kate, A.: Flexible signatures: making authentication suitable for real-time environments. In: ESORICS. Springer, New York (2019)","DOI":"10.1007\/978-3-030-29959-0_9"},{"key":"358_CR30","doi-asserted-by":"crossref","unstructured":"Loveless, A., Dreslinski, R., Kasikci, B., Phan, L.T.X.: Igor: Accelerating byzantine fault tolerance for real-time systems with eager execution. In: IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS) (2021)","DOI":"10.1109\/RTAS52030.2021.00036"},{"key":"358_CR31","doi-asserted-by":"crossref","unstructured":"Lyubashevsky, V.: Lattice signatures without trapdoors. In: EUROCRYPT (2012)","DOI":"10.1007\/978-3-642-29011-4_43"},{"key":"358_CR32","doi-asserted-by":"crossref","unstructured":"Micciancio, D., Peikert, C.: Trapdoors for lattices: Simpler, tighter, faster, smaller. In: EUROCRYPT (2012)","DOI":"10.1007\/978-3-642-29011-4_41"},{"key":"358_CR33","doi-asserted-by":"crossref","unstructured":"Mohamed, M.S.E., Petzoldt, A.: RingRainbow\u2014An efficient multivariate ring signature scheme. In: Progress in Cryptology\u2014AFRICACRYPT, LNCS (2017)","DOI":"10.1007\/978-3-319-57339-7_1"},{"key":"358_CR34","unstructured":"Plantard, T., Sipasseuth, A., Dumondelle, C., Susilo, W.: DRS: diagonal dominant reduction for lattice-based signature. In: PQC Standardization Conference (2018)"},{"key":"358_CR35","doi-asserted-by":"crossref","unstructured":"Sipasseuth, A., Plantard, T., Susilo, W.: Using Freivalds\u2019 Algorithm to accelerate lattice-based signature verifications. In: ISPEC. Springer, New York (2019)","DOI":"10.1007\/978-3-030-34339-2_22"},{"key":"358_CR36","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1016\/j.jcss.2020.08.005","volume":"116","author":"AR Taleb","year":"2020","unstructured":"Taleb, A.R., Vergnaud, D.: Speeding-up verification of digital signatures. J. Comput. Syst. Sci. 116, 22\u201339 (2020)","journal-title":"J. Comput. Syst. Sci."},{"key":"358_CR37","unstructured":"Torresetti, L.: BLEP: a barebone library for efficient and progressive verification. https:\/\/github.com\/torres98\/BLEP (2022)"},{"key":"358_CR38","doi-asserted-by":"crossref","unstructured":"Tsabary, R.: An equivalence between attribute-based signatures and homomorphic signatures, and new constructions for both. In: Theory of Cryptography TCC (2017)","DOI":"10.1007\/978-3-319-70503-3_16"},{"key":"358_CR39","doi-asserted-by":"crossref","unstructured":"Wang, Q., Khurana, H., Huang, Y., Nahrstedt, K.: Time valid one-time signature for time-critical multicast data authentication. In: IEEE INFOCOM (2009)","DOI":"10.1109\/INFCOM.2009.5062037"}],"container-title":["Journal of Cryptographic Engineering"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13389-024-00358-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s13389-024-00358-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13389-024-00358-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,14]],"date-time":"2024-09-14T13:06:35Z","timestamp":1726319195000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s13389-024-00358-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,5]]},"references-count":39,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,9]]}},"alternative-id":["358"],"URL":"https:\/\/doi.org\/10.1007\/s13389-024-00358-0","relation":{},"ISSN":["2190-8508","2190-8516"],"issn-type":[{"value":"2190-8508","type":"print"},{"value":"2190-8516","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,8,5]]},"assertion":[{"value":"22 June 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 June 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 August 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}