{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T05:00:56Z","timestamp":1764997256185,"version":"3.37.3"},"reference-count":38,"publisher":"Oxford University Press (OUP)","issue":"12","license":[{"start":{"date-parts":[[2019,11,20]],"date-time":"2019-11-20T00:00:00Z","timestamp":1574208000000},"content-version":"vor","delay-in-days":2,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/501100001459","name":"Singapore Ministry of Education","doi-asserted-by":"crossref","award":["MOE2016-T2-2-014(S)"],"award-info":[{"award-number":["MOE2016-T2-2-014(S)"]}],"id":[{"id":"10.13039\/501100001459","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Gopalakrishnan\u2014NTU Presidential Postdoctoral Fellowship 2018"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019,12,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Efficient user revocation is a necessary but challenging problem in many multi-user cryptosystems. Among known approaches, server-aided revocation yields a promising solution, because it allows to outsource the major workloads of system users to a computationally powerful third party, called the server, whose only requirement is to carry out the computations correctly. Such a revocation mechanism was considered in the settings of identity-based encryption and attribute-based encryption by Qin et al. (2015, ESORICS) and Cui et al. (2016, ESORICS ), respectively. In this work, we consider the server-aided revocation mechanism in the more elaborate setting of predicate encryption (PE). The latter, introduced by Katz et al. (2008, EUROCRYPT), provides fine-grained and role-based access to encrypted data and can be viewed as a generalization of identity-based and attribute-based encryption. Our contribution is 2-fold. First, we formalize the model of server-aided revocable PE (SR-PE), with rigorous definitions and security notions. Our model can be seen as a non-trivial adaptation of Cui et al.\u2019s work into the PE context. Second, we put forward a lattice-based instantiation of SR-PE. The scheme employs the PE scheme of Agrawal et al. (2011, ASIACRYPT) and the complete subtree method of Naor et al. (2001, CRYPTO) as the two main ingredients, which work smoothly together thanks to a few additional techniques. Our scheme is proven secure in the standard model (in a selective manner), based on the hardness of the learning with errors problem.<\/jats:p>","DOI":"10.1093\/comjnl\/bxz079","type":"journal-article","created":{"date-parts":[[2019,7,9]],"date-time":"2019-07-09T11:08:32Z","timestamp":1562670512000},"page":"1849-1862","source":"Crossref","is-referenced-by-count":6,"title":["Server-Aided Revocable Predicate Encryption: Formalization and Lattice-Based Instantiation"],"prefix":"10.1093","volume":"62","author":[{"given":"San","family":"Ling","sequence":"first","affiliation":[{"name":"Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore, 637371"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Khoa","family":"Nguyen","sequence":"additional","affiliation":[{"name":"Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore, 637371"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Huaxiong","family":"Wang","sequence":"additional","affiliation":[{"name":"Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore, 637371"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Juanyang","family":"Zhang","sequence":"additional","affiliation":[{"name":"Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore, 637371"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2019,11,18]]},"reference":[{"key":"2019122311180812200_ref1","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1007\/978-3-540-78967-3_9","article-title":"Predicate encryption supporting disjunctions, polynomial equations, and inner products","volume-title":"Advances in Cryptology - EUROCRYPT 2008, 27th Annual Int. Conf. on the Theory and Applications of Cryptographic Techniques","author":"Katz","year":"2008"},{"key":"2019122311180812200_ref2","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1007\/11426639_27","article-title":"Fuzzy identity-based encryption","volume-title":"Advances in Cryptology\u2014EUROCRYPT 2005, 24th Annual Int. Conf. on the Theory and Applications of Cryptographic Techniques","author":"Sahai","year":"2005"},{"key":"2019122311180812200_ref3","first-page":"89","article-title":"Attribute-based encryption for fine-grained access control of encrypted data","volume-title":"Proc. of the 13th ACM Conf. on Computer and Communications Security, CCS 2006","author":"Goyal","year":"2006"},{"key":"2019122311180812200_ref4","first-page":"535","article-title":"Conjunctive, subset, and range queries on encrypted data","volume-title":"Theory of Cryptography, 4th Theory of Cryptography Conf., TCC 2007","author":"Boneh","year":"2007"},{"key":"2019122311180812200_ref5","doi-asserted-by":"crossref","first-page":"350","DOI":"10.1109\/SP.2007.29","article-title":"Multi-dimensional range query over encrypted data","volume-title":"2007 IEEE Symposium on Security and Privacy (S&P 2007)","author":"Shi","year":"2007"},{"key":"2019122311180812200_ref6","first-page":"417","article-title":"Identity-based encryption with efficient revocation","volume-title":"Proc. of the 15th ACM Conf. on Computer and Communications Security","author":"Alexandra","year":"2008"},{"key":"2019122311180812200_ref7","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/3-540-44647-8_3","article-title":"Revocation and tracing schemes for stateless receivers","volume-title":"Advances in Cryptology\u2014CRYPTO 2001, 21st Annual Int. Cryptology Conf.","author":"Naor","year":"2001"},{"key":"2019122311180812200_ref8","doi-asserted-by":"crossref","first-page":"278","DOI":"10.1007\/978-3-642-10868-6_17","article-title":"Attribute-based encryption supporting direct\/indirect revocation modes","volume-title":"Cryptography and Coding 2009","author":"Attrapadung","year":"2009"},{"key":"2019122311180812200_ref9","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1007\/978-3-642-32009-5_13","article-title":"Dynamic credentials and ciphertext delegation for attribute-based encryption","volume-title":"Advances in Cryptology\u2014CRYPTO 2012, 32nd Annual Cryptology Conf.","author":"Sahai","year":"2012"},{"key":"2019122311180812200_ref10","doi-asserted-by":"crossref","first-page":"286","DOI":"10.1007\/978-3-319-24174-6_15","article-title":"Server-aided revocable identity-based encryption","volume-title":"Computer Security\u2014ESORICS 2015, 20th European Symposium on Research in Computer Security","author":"Qin","year":"2015"},{"key":"2019122311180812200_ref11","doi-asserted-by":"crossref","first-page":"570","DOI":"10.1007\/978-3-319-45741-3_29","article-title":"Server-aided revocable attribute-based encryption","volume-title":"Computer Security\u2014ESORICS 2016, 21st European Symposium on Research in Computer Security","author":"Cui","year":"2016"},{"key":"2019122311180812200_ref12","first-page":"504","article-title":"Server-aided revocable attribute-based encryption resilient to decryption key exposure","volume-title":"Cryptology and Network Security\u201416th Int. Conf., CANS 2017","author":"Qin","year":"2017"},{"key":"2019122311180812200_ref13","first-page":"1","article-title":"Adaptive-ID secure revocable identity-based encryption","volume-title":"Topics in Cryptology\u2014CT-RSA 2009, The Cryptographers\u2019 Track at the RSA Conf. 2009","author":"Libert","year":"2009"},{"key":"2019122311180812200_ref14","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1007\/978-3-642-36362-7_14","article-title":"Revocable identity-based encryption revisited: security model and construction","volume-title":"Public-Key Cryptography\u2014PKC 2013, 16th Int. Conf. on Practice and Theory in Public-Key Cryptography","author":"Seo","year":"2013"},{"key":"2019122311180812200_ref15","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1007\/s10623-016-0287-3","article-title":"Efficient revocable identity-based encryption via subset difference methods","volume":"85","author":"Lee","year":"2017","journal-title":"Des. Codes Cryptography"},{"key":"2019122311180812200_ref16","first-page":"390","article-title":"Revocable identity-based encryption from lattices","volume-title":"Information Security and Privacy\u201417th Australasian Conf., ACISP 2012","author":"Chen","year":"2012"},{"key":"2019122311180812200_ref17","first-page":"283","article-title":"Adaptive-ID secure revocable identity-based encryption from lattices via subset difference method","volume-title":"Information Security Practice and Experience\u201411th Int. Conf., ISPEC 2015","author":"Cheng","year":"2015"},{"key":"2019122311180812200_ref18","first-page":"184","article-title":"Lattice-based revocable identity-based encryption with bounded decryption key exposure resistance","volume-title":"Information Security and Privacy\u201422nd Australasian Conf., ACISP 2017","author":"Takayasu","year":"2017"},{"key":"2019122311180812200_ref19","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1145\/237814.237838","article-title":"Generating hard instances of lattice problems (extended abstract)","volume-title":"Proc. of the Twenty-eighth Annual ACM Symposium on Theory of Computing","author":"Ajtai","year":"1996"},{"key":"2019122311180812200_ref20","first-page":"84","article-title":"On lattices, learning with errors, random linear codes, and cryptography","volume-title":"Proc. of the Thirty-seventh Annual ACM Symposium on Theory of Computing","author":"Oded","year":"2005"},{"key":"2019122311180812200_ref21","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1145\/1374376.1374407","article-title":"Trapdoors for hard lattices and new cryptographic constructions","volume-title":"Proc. of the Fortieth Annual ACM Symposium on Theory of Computing","author":"Gentry","year":"2008"},{"key":"2019122311180812200_ref22","doi-asserted-by":"crossref","first-page":"553","DOI":"10.1007\/978-3-642-13190-5_28","article-title":"Efficient lattice (H) IBE in the standard model","volume-title":"Advances in Cryptology\u2014EUROCRYPT 2010, 29th Annual Int. Conf. on the Theory and Applications of Cryptographic Techniques","author":"Agrawal","year":"2010"},{"key":"2019122311180812200_ref23","first-page":"107","article-title":"Server-aided revocable identity-based encryption from lattices","volume-title":"Cryptology and Network Security\u201415th Int. Conf., CANS 2016","author":"Nguyen","year":"2016"},{"key":"2019122311180812200_ref24","first-page":"137","article-title":"A lattice-based group signature scheme with message-dependent opening","volume-title":"Applied Cryptography and Network Security\u201414th Int. Conf., ACNS 2016","author":"Libert","year":"2016"},{"key":"2019122311180812200_ref25","first-page":"2277","article-title":"Efficient public trace and revoke from standard assumptions: Extended abstract","volume-title":"Proc. of the 2017 ACM SIGSAC Conf. on Computer and Communications Security","author":"Shweta","year":"2017"},{"key":"2019122311180812200_ref26","first-page":"305","article-title":"Revocable predicate encryption from lattices","volume-title":"Provable Security\u201411th Int. Conf., ProvSec 2017","author":"Ling","year":"2017"},{"key":"2019122311180812200_ref27","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-25385-0_2","article-title":"Functional encryption for inner product predicates from learning with errors","volume-title":"Advances in Cryptology\u2014ASIACRYPT 2011, 17th Int. Conf. on the Theory and Application of Cryptology and Information Security","author":"Agrawal","year":"2011"},{"key":"2019122311180812200_ref28","first-page":"350","article-title":"Fully private revocable predicate encryption","volume-title":"Information Security and Privacy\u201417th Australasian Conf., ACISP 2012","author":"Gonz\u00e1lez-Nieto","year":"2012"},{"key":"2019122311180812200_ref29","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/3-540-39568-7_5","article-title":"Identity-based cryptosystems and signature schemes","volume-title":"Advances in Cryptology, Proc. of CRYPTO\u201984","author":"Shamir","year":"1985"},{"key":"2019122311180812200_ref30","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1007\/978-3-642-55220-5_30","article-title":"Fully key-homomorphic encryption, arithmetic circuit ABE and compact garbled circuits","volume-title":"Advances in Cryptology\u2014EUROCRYPT 2014, 33rd Annual Int. Conf. on the Theory and Applications of Cryptographic Techniques","author":"Boneh","year":"2014"},{"key":"2019122311180812200_ref31","first-page":"1","article-title":"Generating hard instances of the short basis problem","volume-title":"ICALP 1999","author":"Ajtai","year":"1999"},{"key":"2019122311180812200_ref32","doi-asserted-by":"crossref","first-page":"535","DOI":"10.1007\/s00224-010-9278-3","article-title":"Generating shorter bases for hard random lattices","volume":"48","author":"Alwen","year":"2011","journal-title":"Theory Comput. Syst."},{"key":"2019122311180812200_ref33","doi-asserted-by":"crossref","first-page":"700","DOI":"10.1007\/978-3-642-29011-4_41","article-title":"Trapdoors for lattices: simpler, tighter, faster, smaller","volume-title":"Advances in Cryptology\u2014EUROCRYPT 2012, 31st Annual Int. Conf. on the Theory and Applications of Cryptographic Techniques","author":"Micciancio","year":"2012"},{"key":"2019122311180812200_ref34","doi-asserted-by":"crossref","first-page":"752","DOI":"10.1007\/978-3-662-46447-2_34","article-title":"Predicate encryption for multi-dimensional range queries from lattices","volume-title":"Public-Key Cryptography\u2014PKC 2015, 18th IACR Int. Conf. on Practice and Theory in Public-Key Cryptography","author":"Gay","year":"2015"},{"key":"2019122311180812200_ref35","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1145\/1536414.1536461","article-title":"Public-key cryptosystems from the worst-case shortest vector problem: extended abstract","volume-title":"Proc. of the Forty-first Annual ACM Symposium on Theory of Computing","author":"Peikert","year":"2009"},{"key":"2019122311180812200_ref36","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1007\/978-3-642-36362-7_15","article-title":"Improved (hierarchical) inner-product encryption from lattices","volume-title":"Public-Key Cryptography\u2014PKC 2013, 16th Int. Conf. on Practice and Theory in Public-Key Cryptography","author":"Xagawa","year":"2013"},{"key":"2019122311180812200_ref37","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1007\/978-3-642-01001-9_10","article-title":"Adaptive security in broadcast encryption systems (with short ciphertexts)","volume-title":"Advances in Cryptology\u2014EUROCRYPT 2009, 28th Annual Int. Conf. on the Theory and Applications of Cryptographic Techniques","author":"Gentry","year":"2009"},{"key":"2019122311180812200_ref38","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1007\/978-3-662-48000-7_25","article-title":"Predicate encryption for circuits from LWE","volume-title":"Advances in Cryptology\u2014CRYPTO 2015, 35th Annual Cryptology Conf.","author":"Gorbunov","year":"2015"}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/comjnl\/article-pdf\/62\/12\/1849\/31568425\/bxz079.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/academic.oup.com\/comjnl\/article-pdf\/62\/12\/1849\/31568425\/bxz079.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,18]],"date-time":"2023-09-18T02:49:06Z","timestamp":1695005346000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/62\/12\/1849\/5628022"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,18]]},"references-count":38,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2019,11,18]]},"published-print":{"date-parts":[[2019,12,10]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxz079","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"type":"print","value":"0010-4620"},{"type":"electronic","value":"1460-2067"}],"subject":[],"published-other":{"date-parts":[[2019,12]]},"published":{"date-parts":[[2019,11,18]]}}}