{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:27:30Z","timestamp":1750307250979,"version":"3.41.0"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2010,12,1]],"date-time":"2010-12-01T00:00:00Z","timestamp":1291161600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Inf. Syst. Secur."],"published-print":{"date-parts":[[2010,12]]},"abstract":"<jats:p>Forward-Secure Signatures (FSS) prevent forgeries for past time periods when an attacker obtains full access to the signer\u2019s storage by evolving the private key in a one-way fashion. To simplify the integration of these primitives into standard security architectures, Boyen et al. [2006] recently introduced the concept of forward-secure signatures with untrusted updates where private keys are additionally protected by a second factor (derived from a password). Key updates can be made on encrypted version of signing keys so that passwords only come into play for signing messages and not at update time (since update is not user-driven). The scheme put forth by Boyen et al. relies on bilinear maps and does not require the random oracle. They also suggest the integration of untrusted updates in the Bellare-Miner forward-secure signature. Their work left open the problem of endowing other existing FSS systems with the same second factor protection, and a natural second question is whether the method can apply to other key-evolving paradigms. This article solves the first problem by showing an efficient generic construction that does not require to set a bound on the number of time periods at key generation. The article then extends the unprotected update model to other key-evolving primitives such as forward-secure public key encryption and key-insulated cryptosystems.<\/jats:p>","DOI":"10.1145\/1880022.1880031","type":"journal-article","created":{"date-parts":[[2010,12,29]],"date-time":"2010-12-29T14:32:48Z","timestamp":1293633168000},"page":"1-34","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Key Evolution Systems in Untrusted Update Environments"],"prefix":"10.1145","volume":"13","author":[{"given":"Beno\u00eet","family":"Libert","sequence":"first","affiliation":[{"name":"Universit\u00e9 Catholique de Louvain, Crypto Group"}]},{"given":"Jean-Jacques","family":"Quisquater","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Catholique de Louvain, Crypto Group"}]},{"given":"Moti","family":"Yung","sequence":"additional","affiliation":[{"name":"Google Inc. and Columbia University"}]}],"member":"320","published-online":{"date-parts":[[2010,12]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the Annual International Conference on the Theory and Application of Crytology and Information Security, Advances in Cryptology (ASIACRYPT\u201900)","volume":"1976","author":"Abdalla M.","unstructured":"Abdalla , M. and Reyzin , L . 2000. A new forward-secure digital signature scheme . In Proceedings of the Annual International Conference on the Theory and Application of Crytology and Information Security, Advances in Cryptology (ASIACRYPT\u201900) . Lecture Notes in Computer Science , vol. 1976 , Springer, 116--129. Abdalla, M. and Reyzin, L. 2000. A new forward-secure digital signature scheme. In Proceedings of the Annual International Conference on the Theory and Application of Crytology and Information Security, Advances in Cryptology (ASIACRYPT\u201900). Lecture Notes in Computer Science, vol. 1976, Springer, 116--129."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the Cryptographer\u2019s Track at the RSA Conference, Topics in Cryptology (CT-RSA\u201901)","volume":"2020","author":"Abdalla M.","unstructured":"Abdalla , M. , Miner , S. , and Namprempre , C . 2001. Forward-secure threshold signature schemes . In Proceedings of the Cryptographer\u2019s Track at the RSA Conference, Topics in Cryptology (CT-RSA\u201901) . Lecture Notes in Computer Science , vol. 2020 , Springer, 441--456. Abdalla, M., Miner, S., and Namprempre, C. 2001. Forward-secure threshold signature schemes. In Proceedings of the Cryptographer\u2019s Track at the RSA Conference, Topics in Cryptology (CT-RSA\u201901). Lecture Notes in Computer Science, vol. 2020, Springer, 441--456."},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 4th ACM Conference on Computer and Communications Security (CCS\u201997)","author":"Anderson R.","year":"1997","unstructured":"Anderson , R. 1997 . Two remarks on public key cryptology . In Proceedings of the 4th ACM Conference on Computer and Communications Security (CCS\u201997) . ACM Press. Anderson, R. 1997. Two remarks on public key cryptology. In Proceedings of the 4th ACM Conference on Computer and Communications Security (CCS\u201997). ACM Press."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1455770.1455827"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/646764.703986"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1180405.1180453"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/168588.168596"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1767011.1767013"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00208000"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/2394539.2394589"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the Conference on Public Key Cryptography (PKC\u201903)","volume":"2567","author":"Boldyreva A.","year":"2003","unstructured":"Boldyreva , A. 2003 . Efficient threshold signature, multisignature and blind signature schemes based on the Gap-Diffie-Hellman-group signature scheme . In Proceedings of the Conference on Public Key Cryptography (PKC\u201903) . Lecture Notes in Computer Science , vol. 2567 , Springer, 31--46. Boldyreva, A. 2003. Efficient threshold signature, multisignature and blind signature schemes based on the Gap-Diffie-Hellman-group signature scheme. In Proceedings of the Conference on Public Key Cryptography (PKC\u201903). Lecture Notes in Computer Science, vol. 2567, Springer, 31--46."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24676-3_14"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-89255-7_28"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the Annual International Conference on Theory and Application of Cryptology and Information Security, Advances in Cryptology (ASIACRYPT\u201901)","volume":"2248","author":"Boneh D.","unstructured":"Boneh , D. , Lynn , B. , and Shacham , H . 2001. Short signatures from the Weil pairing . In Proceedings of the Annual International Conference on Theory and Application of Cryptology and Information Security, Advances in Cryptology (ASIACRYPT\u201901) . Lecture Notes in Computer Science , vol. 2248 , Springer. Boneh, D., Lynn, B., and Shacham, H. 2001. Short signatures from the Weil pairing. In Proceedings of the Annual International Conference on Theory and Application of Cryptology and Information Security, Advances in Cryptology (ASIACRYPT\u201901). Lecture Notes in Computer Science, vol. 2248, Springer."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/11426639_26"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1180405.1180430"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2005.03.028"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/1766171.1766193"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/948109.948130"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30576-7_11"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/947380.947387"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/647087.715707"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/1767011.1767014"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/648120.746921"},{"key":"e_1_2_1_25_1","first-page":"441","article-title":"A generic construction for intrusion-resilient public-key encryption. In Proceedings of the Cryptographer\u2019s Track at the RSA Conference, Topics in Cryptology (CT-RSA\u201904)","volume":"2964","author":"Dodis Y.","year":"2004","unstructured":"Dodis , Y. , Franklin , M. , Katz , J. , Miyaji , A. , and Yung , M. 2004 . A generic construction for intrusion-resilient public-key encryption. In Proceedings of the Cryptographer\u2019s Track at the RSA Conference, Topics in Cryptology (CT-RSA\u201904) . Lecture Notes in Computer Science , vol. 2964 , Spring er, 441 -- 456 . Dodis, Y., Franklin, M., Katz, J., Miyaji, A., and Yung, M. 2004. A generic construction for intrusion-resilient public-key encryption. In Proceedings of the Cryptographer\u2019s Track at the RSA Conference, Topics in Cryptology (CT-RSA\u201904). Lecture Notes in Computer Science, vol. 2964, Springer, 441--456.","journal-title":"Lecture Notes in Computer Science"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/36664.36676"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the Annual International Conference on the Theory and Application of Cryptology and Information Security, Advances in Cryptology (ASIACRYPT\u201902)","volume":"2501","author":"Gentry C.","unstructured":"Gentry , C. and Silverberg , A . 2002. Hierarchical id-based cryptography . In Proceedings of the Annual International Conference on the Theory and Application of Cryptology and Information Security, Advances in Cryptology (ASIACRYPT\u201902) . Lecture Notes in Computer Science , vol. 2501 , Springer. Gentry, C. and Silverberg, A. 2002. Hierarchical id-based cryptography. In Proceedings of the Annual International Conference on the Theory and Application of Cryptology and Information Security, Advances in Cryptology (ASIACRYPT\u201902). Lecture Notes in Computer Science, vol. 2501, Springer."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217017"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/646753.704901"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques, Advances in Cryptology (EUROCRYPT\u201902)","volume":"2332","author":"Horwitz J.","unstructured":"Horwitz , J. and Lynn , B . 2002. Toward hierarchical identity-based encryption . In Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques, Advances in Cryptology (EUROCRYPT\u201902) . Lecture Notes in Computer Science , vol. 2332 , Springer. Horwitz, J. and Lynn, B. 2002. Toward hierarchical identity-based encryption. In Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques, Advances in Cryptology (EUROCRYPT\u201902). Lecture Notes in Computer Science, vol. 2332, Springer."},{"key":"e_1_2_1_31_1","first-page":"1","article-title":"A public key cryptosystem suitable for digital multisignatures","volume":"71","author":"Itakura K.","year":"1983","unstructured":"Itakura , K. and Nakamura , K. 1983 . A public key cryptosystem suitable for digital multisignatures . NEC Res. Devel. 71 , 1 -- 8 . Itakura, K. and Nakamura, K. 1983. A public key cryptosystem suitable for digital multisignatures. NEC Res. Devel. 71, 1--8.","journal-title":"NEC Res. Devel."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/646766.704153"},{"key":"e_1_2_1_33_1","series-title":"Lecture Notes in Computer Science","volume-title":"Sibir: Signer-base intrusion-resilient signatures. In Proceedings of the International Cryptology Conference, Advances in Cryptology (CRYPTO\u201902)","author":"Itkis G.","year":"2002","unstructured":"Itkis , G. and Reyzin , L . 2002 . Sibir: Signer-base intrusion-resilient signatures. In Proceedings of the International Cryptology Conference, Advances in Cryptology (CRYPTO\u201902) . Lecture Notes in Computer Science , vol. 2442 , Springer , 499--514. Itkis, G. and Reyzin, L. 2002. Sibir: Signer-base intrusion-resilient signatures. In Proceedings of the International Cryptology Conference, Advances in Cryptology (CRYPTO\u201902). Lecture Notes in Computer Science, vol. 2442, Springer, 499--514."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/948109.948132"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the Conference on Security in Communication Networks (SCN\u201902)","volume":"2576","author":"Kozlov A.","unstructured":"Kozlov , A. and Reyzin , L . 2002. Forward-secure signatures with fast key update . In Proceedings of the Conference on Security in Communication Networks (SCN\u201902) . Lecture Notes in Computer Science , vol. 2576 , Springer. Kozlov, A. and Reyzin, L. 2002. Forward-secure signatures with fast key update. In Proceedings of the Conference on Security in Communication Networks (SCN\u201902). Lecture Notes in Computer Science, vol. 2576, Springer."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/352600.352617"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/11761679_28"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24676-3_5"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/647087.715826"},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the International Cryptology Conference, Advances in Cryptology (CRYPTO\u201988)","volume":"403","author":"Merkle R.","year":"1990","unstructured":"Merkle , R. 1990 . A digital signature based on a conventional encryption function . In Proceedings of the International Cryptology Conference, Advances in Cryptology (CRYPTO\u201988) . Lecture Notes in Computer Science , vol. 403 , Springer, 369--378. Merkle, R. 1990. A digital signature based on a conventional encryption function. In Proceedings of the International Cryptology Conference, Advances in Cryptology (CRYPTO\u201988). Lecture Notes in Computer Science, vol. 403, Springer, 369--378."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/501983.502017"},{"key":"e_1_2_1_42_1","first-page":"295","article-title":"Monotone signatures. In Proceedings of the Conference on Financial Cryptography 2001 (FC\u201901)","volume":"2339","author":"Naccache D.","year":"2002","unstructured":"Naccache , D. , Pointcheval , D. , and Tymen , C. 2002 . Monotone signatures. In Proceedings of the Conference on Financial Cryptography 2001 (FC\u201901) . Lecture Notes in Computer Science , vol. 2339 , Spring er, 295 -- 308 . Naccache, D., Pointcheval, D., and Tymen, C. 2002. Monotone signatures. In Proceedings of the Conference on Financial Cryptography 2001 (FC\u201901). Lecture Notes in Computer Science, vol. 2339, Springer, 295--308.","journal-title":"Lecture Notes in Computer Science"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/1788414.1788418"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.5555\/112331.112381"},{"key":"e_1_2_1_45_1","volume-title":"Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques, Advances in Cryptology (EUROCRYPT\u201996)","volume":"1070","author":"Pointcheval D.","unstructured":"Pointcheval , D. and Stern , J . 1996. Security proofs for signature schemes . In Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques, Advances in Cryptology (EUROCRYPT\u201996) . Lecture Notes in Computer Science , vol. 1070 , Springer. Pointcheval, D. and Stern, J. 1996. Security proofs for signature schemes. In Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques, Advances in Cryptology (EUROCRYPT\u201996). Lecture Notes in Computer Science, vol. 1070, Springer."},{"key":"e_1_2_1_46_1","unstructured":"Rabin M. O. 1979. Digitalized signatures and public-key functions as intractable as factorization. Tech. rep. MIT\/LCS\/TR-212 MIT Laboratory for Computer Science. Rabin M. O. 1979. Digitalized signatures and public-key functions as intractable as factorization. Tech. rep. MIT\/LCS\/TR-212 MIT Laboratory for Computer Science."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-72540-4_13"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100269"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.5555\/646754.705037"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/501983.502015"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/11426639_7"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/1030083.1030130"}],"container-title":["ACM Transactions on Information and System Security"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1880022.1880031","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1880022.1880031","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:52:15Z","timestamp":1750243935000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1880022.1880031"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,12]]},"references-count":52,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,12]]}},"alternative-id":["10.1145\/1880022.1880031"],"URL":"https:\/\/doi.org\/10.1145\/1880022.1880031","relation":{},"ISSN":["1094-9224","1557-7406"],"issn-type":[{"type":"print","value":"1094-9224"},{"type":"electronic","value":"1557-7406"}],"subject":[],"published":{"date-parts":[[2010,12]]},"assertion":[{"value":"2009-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-12-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}