{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T16:32:14Z","timestamp":1775579534399,"version":"3.50.1"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2006,11,1]],"date-time":"2006-11-01T00:00:00Z","timestamp":1162339200000},"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":[[2006,11]]},"abstract":"<jats:p>\n            We present a novel way to implement the secret-sharing-based family of revocation schemes of Naor and Pinkas [2003]. The basic scheme of [Naor and Pinkas 2000] uses Shamir's polynomial secret-sharing to revoke up to\n            <jats:italic>r<\/jats:italic>\n            users, where\n            <jats:italic>r<\/jats:italic>\n            is the degree of the secret-sharing polynomial, and it is information theoretically secure against coalitions of up to\n            <jats:italic>r<\/jats:italic>\n            collaborators. The nonrevoked users use Lagrange interpolation in order to compute the new key. Our basic scheme uses a novel modification of Shamir's polynomial secret-sharing: The secret equals the leading coefficient of the polynomial (as opposed to the free coefficient as in the original scheme) and the polynomial is reconstructed by Newton interpolation (rather than Lagrange interpolation). Comparing our scheme to one variant of the Naor--Pinkas scheme, we offer revocation messages that are shorter by a factor of almost 2, while the computation cost at the user end is smaller by a constant factor of approximately 13\/2. Comparing to a second variant of the Naor--Pinkas scheme, our scheme offers a reduction of\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>r<\/jats:italic>\n            ) in the computation cost at the user end, without affecting any of the other performance parameters. We then extend our basic scheme to perform multiround revocation for stateless and stateful receivers, along the lines offered by Naor and Pinkas [2000] and Kogan et al. [2003]. We show that using Newton rather than Lagrange interpolants enables a significantly more efficient transmission of the new revocation message and shorter response time for each round. Pay TV systems that implement broadcast encryption techniques can benefit significantly from the improved efficiency offered by our revocation schemes.\n          <\/jats:p>","DOI":"10.1145\/1187441.1187444","type":"journal-article","created":{"date-parts":[[2007,1,16]],"date-time":"2007-01-16T19:38:29Z","timestamp":1168976309000},"page":"461-486","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Improved efficiency for revocation schemes via Newton interpolation"],"prefix":"10.1145","volume":"9","author":[{"given":"Noam","family":"Kogan","sequence":"first","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tamir","family":"Tassa","sequence":"additional","affiliation":[{"name":"The Open University, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2006,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.865073"},{"key":"e_1_2_1_2_1","volume-title":"Advances in Cryptology---ASIACRYPT '99","volume":"1716","author":"Anzai J.","unstructured":"Anzai , J. , Matsuzaki , N. , and Matsumoto , T . 1999. A quick group key distribution scheme with entity revocation . Advances in Cryptology---ASIACRYPT '99 . Lecture Notes in Computer Science , vol. 1716 , Springer Verlag, New York. 333--347.]] Anzai, J., Matsuzaki, N., and Matsumoto, T. 1999. A quick group key distribution scheme with entity revocation. Advances in Cryptology---ASIACRYPT '99. Lecture Notes in Computer Science, vol. 1716, Springer Verlag, New York. 333--347.]]"},{"key":"e_1_2_1_3_1","series-title":"Lecture Notes in Computer Science","volume-title":"How to broadcast a secret. Advances in Cryptology---EUROCRYPT '91","author":"Berkovits S.","unstructured":"Berkovits , S. 1991. How to broadcast a secret. Advances in Cryptology---EUROCRYPT '91 . Lecture Notes in Computer Science , vol. 547 , Springer Verlag , New York , 535--541.]] Berkovits, S. 1991. How to broadcast a secret. Advances in Cryptology---EUROCRYPT '91. Lecture Notes in Computer Science, vol. 547, Springer Verlag, New York, 535--541.]]"},{"key":"e_1_2_1_4_1","series-title":"Lecture Notes in Computer Science, 1423","volume-title":"The decision Diffie--Hellman problem. The Third Algorithmic Number Theory Symposium","author":"Boneh D.","unstructured":"Boneh , D. 1998. The decision Diffie--Hellman problem. The Third Algorithmic Number Theory Symposium , Lecture Notes in Computer Science, 1423 , Springer Verlag , New York , 48--63.]] Boneh, D. 1998. The decision Diffie--Hellman problem. The Third Algorithmic Number Theory Symposium, Lecture Notes in Computer Science, 1423, Springer Verlag, New York, 48--63.]]"},{"key":"e_1_2_1_5_1","volume-title":"IEEE INFOCOM '99","author":"Canetti R.","unstructured":"Canetti , R. , Garay , J. , Itkis , G. , Micciancio , D. , Naor , M. , and Pinkas , B . 1999a. Multicast security: A taxonomy and efficient constructions . IEEE INFOCOM '99 . 708--716.]] Canetti, R., Garay, J., Itkis, G., Micciancio, D., Naor, M., and Pinkas, B. 1999a. Multicast security: A taxonomy and efficient constructions. IEEE INFOCOM '99. 708--716.]]"},{"key":"e_1_2_1_6_1","volume-title":"Advances in Cryptology---EUROCRYPT '99","volume":"1592","author":"Canetti R.","unstructured":"Canetti , R. , Malkin , T. , and Nissim , K . 1999b. Efficient communication-storage tradeoffs for multicast encryption . Advances in Cryptology---EUROCRYPT '99 . Lecture Notes in Computer Science , vol. 1592 , Springer Verlag, New York. 459--474.]] Canetti, R., Malkin, T., and Nissim, K. 1999b. Efficient communication-storage tradeoffs for multicast encryption. Advances in Cryptology---EUROCRYPT '99. Lecture Notes in Computer Science, vol. 1592, Springer Verlag, New York. 459--474.]]"},{"key":"e_1_2_1_7_1","volume-title":"Advances in Cryptology---ASIACRYPT '98","volume":"1514","author":"Cohen H.","unstructured":"Cohen , H. , Miyaji , A. , and Ono , T . 1998. Efficient elliptic curve exponentiation using mixed coordinates . Advances in Cryptology---ASIACRYPT '98 . Lecture Notes in Computer Science , vol. 1514 , Springer Verlag, New York. 51--65.]] Cohen, H., Miyaji, A., and Ono, T. 1998. Efficient elliptic curve exponentiation using mixed coordinates. Advances in Cryptology---ASIACRYPT '98. Lecture Notes in Computer Science, vol. 1514, Springer Verlag, New York. 51--65.]]"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","first-page":"644","DOI":"10.1109\/TIT.1976.1055638","article-title":"New directions in cryptography","volume":"22","author":"Diffie W.","year":"1976","unstructured":"Diffie , W. and Hellman , M. E. 1976 . New directions in cryptography . IEEE Transactions on Information Theory , 22 , 644 -- 654 .]] Diffie, W. and Hellman, M. E. 1976. New directions in cryptography. IEEE Transactions on Information Theory, 22, 644--654.]]","journal-title":"IEEE Transactions on Information Theory"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1007\/978-3-540-44993-5_5","article-title":"Public key broadcast encryption for stateless receivers. Digital Rights Management Workshop","volume":"2696","author":"Dodis Y.","year":"2002","unstructured":"Dodis , Y. and Fazio , N. 2002 a. Public key broadcast encryption for stateless receivers. Digital Rights Management Workshop . Lecture Notes in Computer Science , vol. 2696. 61 -- 80 .]] Dodis, Y. and Fazio, N. 2002a. Public key broadcast encryption for stateless receivers. Digital Rights Management Workshop. Lecture Notes in Computer Science, vol. 2696. 61--80.]]","journal-title":"Lecture Notes in Computer Science"},{"key":"e_1_2_1_10_1","volume-title":"Lecture Notes in Computer Science","volume":"2567","author":"Dodis Y.","unstructured":"Dodis , Y. and Fazio , N . 2002b. Public key trace and revoke scheme secure against adaptive chosen ciphertext attack. Public Key Cryptography 2003 . Lecture Notes in Computer Science , vol. 2567 , Springer Verlag, New York. 100--115.]] Dodis, Y. and Fazio, N. 2002b. Public key trace and revoke scheme secure against adaptive chosen ciphertext attack. Public Key Cryptography 2003. Lecture Notes in Computer Science, vol. 2567, Springer Verlag, New York. 100--115.]]"},{"key":"e_1_2_1_11_1","volume-title":"Principles of Distributed Computing---PODC '03","author":"Dodis Y.","year":"2035","unstructured":"Dodis , Y. , Fazio , N. , Kiayias , A. , and Yung , M . 2003. Scalable public-key tracing and revoking . Principles of Distributed Computing---PODC '03 . 190--199.]] 10.1145\/87 2035 .872062 Dodis, Y., Fazio, N., Kiayias, A., and Yung, M. 2003. Scalable public-key tracing and revoking. Principles of Distributed Computing---PODC '03. 190--199.]] 10.1145\/872035.872062"},{"key":"e_1_2_1_12_1","series-title":"Lecture Notes in Computer Science","volume-title":"A public key cryptosystem and a signature scheme based on discrete logarithms. Advances in Cryptology---CRYPTO '84","author":"El-Gamal T.","unstructured":"El-Gamal , T. 1985. A public key cryptosystem and a signature scheme based on discrete logarithms. Advances in Cryptology---CRYPTO '84 . Lecture Notes in Computer Science , vol. 196 , Springer Verlag , New York . 10--18.]] El-Gamal, T. 1985. A public key cryptosystem and a signature scheme based on discrete logarithms. Advances in Cryptology---CRYPTO '84. Lecture Notes in Computer Science, vol. 196, Springer Verlag, New York. 10--18.]]"},{"key":"e_1_2_1_13_1","volume-title":"The 28th IEEE Symposium on Foundations of Computer Science. 427--437","author":"Feldman P.","year":"1987","unstructured":"Feldman , P. 1987 . A practical scheme for non-interactive verifiable secret-sharing . The 28th IEEE Symposium on Foundations of Computer Science. 427--437 .]] Feldman, P. 1987. A practical scheme for non-interactive verifiable secret-sharing. The 28th IEEE Symposium on Foundations of Computer Science. 427--437.]]"},{"key":"e_1_2_1_14_1","volume-title":"Advances in Cryptology---CRYPTO '93","volume":"773","author":"Fiat A.","unstructured":"Fiat , A. and Naor , M . 1994. Broadcast encryption . Advances in Cryptology---CRYPTO '93 . Lecture Notes in Computer Science , vol. 773 , Springer Verlag, New York. 480--491.]] Fiat, A. and Naor, M. 1994. Broadcast encryption. Advances in Cryptology---CRYPTO '93. Lecture Notes in Computer Science, vol. 773, Springer Verlag, New York. 480--491.]]"},{"key":"e_1_2_1_15_1","volume-title":"Lecture Notes in Computer Science","volume":"1880","author":"Garay J. A.","unstructured":"Garay , J. A. , Staddon , J. , and Wool , A . 2000. Long-lived broadcast encryption. Advances in Cryptology---CRYPTO 2000 . Lecture Notes in Computer Science , vol. 1880 , Springer Verlag, New York. 333--352.]] Garay, J. A., Staddon, J., and Wool, A. 2000. Long-lived broadcast encryption. Advances in Cryptology---CRYPTO 2000. Lecture Notes in Computer Science, vol. 1880, Springer Verlag, New York. 333--352.]]"},{"key":"e_1_2_1_16_1","volume-title":"Lecture Notes in Computer Science","volume":"3152","author":"Goodrich M. T.","unstructured":"Goodrich , M. T. , Sun , J. Z. , and Tamassia , R . 2004. Efficient tree-based revocation in groups of low-state devices, Advances in Cryptology---CRYPTO 2004 . Lecture Notes in Computer Science , vol. 3152 , Springer Verlag, New York. 511--527.]] Goodrich, M. T., Sun, J. Z., and Tamassia, R. 2004. Efficient tree-based revocation in groups of low-state devices, Advances in Cryptology---CRYPTO 2004. Lecture Notes in Computer Science, vol. 3152, Springer Verlag, New York. 511--527.]]"},{"key":"e_1_2_1_17_1","volume-title":"Lecture Notes in Computer Science","volume":"2442","author":"Halevy D.","unstructured":"Halevy , D. and Shamir , A . 2002. The LSD broadcast encryption scheme. Advances in Cryptology---CRYPTO 2002 . Lecture Notes in Computer Science , vol. 2442 , Springer Verlag, New York. 47--60.]] Halevy, D. and Shamir, A. 2002. The LSD broadcast encryption scheme. Advances in Cryptology---CRYPTO 2002. Lecture Notes in Computer Science, vol. 2442, Springer Verlag, New York. 47--60.]]"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Kim C. H. Hwang Y. H. and \n      Lee P. J\n  . \n  2003\n  . An efficient public-key trace and revoke scheme secure against adaptive chosen ciphertext attack. ASIACRYPT 2003 Lecture Notes in Computer Science vol. \n  2894 Springer Verlag New York. 359--373.]]  Kim C. H. Hwang Y. H. and Lee P. J. 2003. An efficient public-key trace and revoke scheme secure against adaptive chosen ciphertext attack. ASIACRYPT 2003 Lecture Notes in Computer Science vol. 2894 Springer Verlag New York. 359--373.]]","DOI":"10.1007\/978-3-540-40061-5_23"},{"key":"e_1_2_1_19_1","volume-title":"The 24th IEEE Symposium on Security and Privacy. 225--235","author":"Kogan N.","unstructured":"Kogan , N. , Shavitt , Y. , and Wool , A . 2003. A practical revocation scheme for broadcast encryption using smartcards . The 24th IEEE Symposium on Security and Privacy. 225--235 .]] Kogan, N., Shavitt, Y., and Wool, A. 2003. A practical revocation scheme for broadcast encryption using smartcards. The 24th IEEE Symposium on Security and Privacy. 225--235.]]"},{"key":"e_1_2_1_20_1","volume-title":"Advances in Cryptology---CRYPTO '99","volume":"1666","author":"Kumar R.","unstructured":"Kumar , R. , Rajagopalan , S. , and Sahai , A . 1999. Coding constructions for blacklisting problems without computational assumptions . Advances in Cryptology---CRYPTO '99 . Lecture Notes in Computer Science , vol. 1666 , Springer Verlag, New York. 609--623.]] Kumar, R., Rajagopalan, S., and Sahai, A. 1999. Coding constructions for blacklisting problems without computational assumptions. Advances in Cryptology---CRYPTO '99. Lecture Notes in Computer Science, vol. 1666, Springer Verlag, New York. 609--623.]]"},{"key":"e_1_2_1_21_1","volume-title":"Advances in Cryptology---EUROCRYPT '98","volume":"1403","author":"Luby M.","unstructured":"Luby , M. and Staddon , J . 1998. Combinatorial bounds for broadcast encryption . Advances in Cryptology---EUROCRYPT '98 . Lecture Notes in Computer Science , vol. 1403 , Springer Verlag, New York. 512--526.]] Luby, M. and Staddon, J. 1998. Combinatorial bounds for broadcast encryption. Advances in Cryptology---EUROCRYPT '98. Lecture Notes in Computer Science, vol. 1403, Springer Verlag, New York. 512--526.]]"},{"key":"e_1_2_1_22_1","volume-title":"Lecture Notes in Computer Science","volume":"2139","author":"Naor D.","unstructured":"Naor , D. , Naor , M. , and Lotspiech , J. B . 2001. Revocation and tracing schemes for stateless receivers. Advances in Cryptology---CRYPTO 2001 . Lecture Notes in Computer Science , vol. 2139 , Springer Verlag, New York. 41--62.]] Naor, D., Naor, M., and Lotspiech, J. B. 2001. Revocation and tracing schemes for stateless receivers. Advances in Cryptology---CRYPTO 2001. Lecture Notes in Computer Science, vol. 2139, Springer Verlag, New York. 41--62.]]"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Naor M.\n     and \n      Pinkas B\n  . \n  2000\n  . Efficient trace and revoke schemes. Financial Cryptography 2000 Lecture Notes in Computer Science vol. \n  1962 Springer Verlag New York. 1--20.]]   Naor M. and Pinkas B. 2000. Efficient trace and revoke schemes. Financial Cryptography 2000 Lecture Notes in Computer Science vol. 1962 Springer Verlag New York. 1--20.]]","DOI":"10.1007\/3-540-45472-1_1"},{"key":"e_1_2_1_24_1","volume-title":"The 38th IEEE symposium on Foundations of Computer Science. 458--467","author":"Naor M.","unstructured":"Naor , M. and Reingold , O . 1997. Number-theoretic constructions of efficient pseudo-random functions . The 38th IEEE symposium on Foundations of Computer Science. 458--467 .]] Naor, M. and Reingold, O. 1997. Number-theoretic constructions of efficient pseudo-random functions. The 38th IEEE symposium on Foundations of Computer Science. 458--467.]]"},{"key":"e_1_2_1_25_1","volume-title":"Digital Rights Management Workshop","volume":"2320","author":"Pinkas B.","year":"2001","unstructured":"Pinkas , B. 2001 . Efficient state updates for key management . Digital Rights Management Workshop 2001, Lecture Notes in Computer Science , vol. 2320 . 40--56.]] Pinkas, B. 2001. Efficient state updates for key management. Digital Rights Management Workshop 2001, Lecture Notes in Computer Science, vol. 2320. 40--56.]]"},{"key":"e_1_2_1_26_1","first-page":"8","article-title":"Polynomial codes over certain finite fields","volume":"1960","author":"Reed I. S.","year":"1960","unstructured":"Reed , I. S. and Solomon , G. 1960 . Polynomial codes over certain finite fields . Journal of the Society of Industrial and Applied Mathematics 1960 , 8 . 300--304.]] Reed, I. S. and Solomon, G. 1960. Polynomial codes over certain finite fields. Journal of the Society of Industrial and Applied Mathematics 1960, 8. 300--304.]]","journal-title":"Journal of the Society of Industrial and Applied Mathematics"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/359168.359176"},{"key":"e_1_2_1_28_1","volume-title":"Cryptography, Theory and Practice","author":"Stinson D.","unstructured":"Stinson , D. 2005. Cryptography, Theory and Practice , 3 rd ed., CRC Press , Boca Raton, FL .]] Stinson, D. 2005. Cryptography, Theory and Practice, 3rd ed., CRC Press, Boca Raton, FL.]]","edition":"3"},{"key":"e_1_2_1_29_1","volume-title":"Lecture Notes in Computer Science","volume":"1992","author":"Tzeng W. G.","unstructured":"Tzeng , W. G. and Tzeng , Z. J . 2001. A public-key traitor tracing scheme with revocation using dynamic shares. Public Key Cryptography 2001 . Lecture Notes in Computer Science , vol. 1992 , Springer Verlag, New York. 207--224.]] Tzeng, W. G. and Tzeng, Z. J. 2001. A public-key traitor tracing scheme with revocation using dynamic shares. Public Key Cryptography 2001. Lecture Notes in Computer Science, vol. 1992, Springer Verlag, New York. 207--224.]]"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Wallner D. M. Harder E. J. and Agee R. C. 1999. Key management for multicast: Issues and architectures. Request for Comments 2627 (June).]]   Wallner D. M. Harder E. J. and Agee R. C. 1999. Key management for multicast: Issues and architectures. Request for Comments 2627 (June).]]","DOI":"10.17487\/rfc2627"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.836475"}],"container-title":["ACM Transactions on Information and System Security"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1187441.1187444","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1187441.1187444","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:08:12Z","timestamp":1750262892000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1187441.1187444"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,11]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2006,11]]}},"alternative-id":["10.1145\/1187441.1187444"],"URL":"https:\/\/doi.org\/10.1145\/1187441.1187444","relation":{},"ISSN":["1094-9224","1557-7406"],"issn-type":[{"value":"1094-9224","type":"print"},{"value":"1557-7406","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,11]]},"assertion":[{"value":"2006-11-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}