{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,21]],"date-time":"2026-10-21T18:19:52Z","timestamp":1792606792664,"version":"4.5.0"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2023,1,17]],"date-time":"2023-01-17T00:00:00Z","timestamp":1673913600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,1,17]],"date-time":"2023-01-17T00:00:00Z","timestamp":1673913600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Des. Codes Cryptogr."],"published-print":{"date-parts":[[2023,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>This paper presents the <jats:italic>first attribute-based signature<\/jats:italic> () scheme supporting signing policies representable by <jats:italic>Turing machines<\/jats:italic> (), based on <jats:italic>well-studied computational assumptions<\/jats:italic>. Our work supports <jats:italic>arbitrary<\/jats:italic>s as signing policies in the sense that the s can accept signing attribute strings of <jats:italic>unbounded<\/jats:italic> polynomial length and there is <jats:italic>no limit<\/jats:italic> on their running time, description size, or space complexity. Moreover, we are able to achieve <jats:italic>input-specific<\/jats:italic> running time for the signing algorithm. All other known expressive  schemes could at most support signing policies realizable by either arbitrary polynomial-size circuits or s having a pre-determined upper bound on the running time. Consequently, those schemes can only deal with signing attribute strings whose lengths are a priori bounded, as well as suffers from the worst-case running time problem. On a more positive note, for the <jats:italic>first<\/jats:italic> time in the literature, the signature size of our  scheme only depends on the size of the signed message and is completely <jats:italic>independent<\/jats:italic> of the size of the signing policy under which the signature is generated. This is a significant achievement from the point of view of communication efficiency. Our  construction makes use of indistinguishability obfuscation () for polynomial-size circuits and certain -compatible cryptographic tools. Note that, all of these building blocks including  for polynomial-size circuits are currently known to be realizable under well-studied computational assumptions.<\/jats:p>","DOI":"10.1007\/s10623-022-01163-8","type":"journal-article","created":{"date-parts":[[2023,1,17]],"date-time":"2023-01-17T12:11:48Z","timestamp":1673957508000},"page":"1845-1872","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Short attribute-based signatures for arbitrary Turing machines from standard assumptions"],"prefix":"10.1007","volume":"91","author":[{"given":"Pratish","family":"Datta","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ratna","family":"Dutta","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sourav","family":"Mukhopadhyay","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2023,1,17]]},"reference":[{"key":"1163_CR1","unstructured":"Ananth P., Jain A., Sahai A.: Indistinguishability obfuscation without multilinear maps: io from lwe, bilinear maps, and weak pseudorandomness. In: Cryptology ePrint Archive, Report 2018\/615 (2018)."},{"key":"1163_CR2","doi-asserted-by":"crossref","unstructured":"Ananth P., Jain A., Lin H., Matt C., Sahai A.: Indistinguishability obfuscation without multilinear maps: new paradigms via low degree weak pseudorandomness and security amplification. In: CRYPTO 2019, pp. 284\u2013332. Springer (2019).","DOI":"10.1007\/978-3-030-26954-8_10"},{"key":"1163_CR3","doi-asserted-by":"crossref","unstructured":"Barak B., Goldreich O., Impagliazzo R., Rudich S., Sahai A., Vadhan S., Yan, K.: On the (im) possibility of obfuscating programs. In: CRYPTO 2001, pp. 1\u201318. Springer (2001).","DOI":"10.1007\/3-540-44647-8_1"},{"key":"1163_CR4","doi-asserted-by":"crossref","unstructured":"Bellare M., Fuchsbauer G.: Policy-based signatures. In: PKC 2014, pp. 520\u2013537. Springer (2014).","DOI":"10.1007\/978-3-642-54631-0_30"},{"key":"1163_CR5","doi-asserted-by":"crossref","unstructured":"Boneh D., Waters B.: Constrained pseudorandom functions and their applications. In: ASIACRYPT 2013, pp. 280\u2013300. Springer (2013).","DOI":"10.1007\/978-3-642-42045-0_15"},{"key":"1163_CR6","doi-asserted-by":"crossref","unstructured":"Datta P., Okamoto T., Takashima K.: Efficient attribute-based signatures for unbounded arithmetic branching programs. In: PKC 2019, pp. 127\u2013158. Springer (2019).","DOI":"10.1007\/978-3-030-17253-4_5"},{"key":"1163_CR7","doi-asserted-by":"crossref","unstructured":"Deshpande A., Koppula V., Waters B.: Constrained pseudorandom functions for unconstrained inputs. In: EUROCRYPT 2016, pp. 124\u2013153. Springer (2016).","DOI":"10.1007\/978-3-662-49896-5_5"},{"key":"1163_CR8","doi-asserted-by":"crossref","unstructured":"Garg S., Gentry C., Halevi S., Raykova M., Sahai A., Waters B.: Candidate indistinguishability obfuscation and functional encryption for all circuits. In: FOCS 2013, pp. 40\u201349. IEEE (2013).","DOI":"10.1109\/FOCS.2013.13"},{"key":"1163_CR9","doi-asserted-by":"crossref","unstructured":"Gay R., Jain A., Lin H., Sahai A.: Indistinguishability obfuscation from simple-to-state hard problems: new assumptions, new techniques, and simplification. In: EUROCRYPT 2021, pp. 97\u2013126. Springer (2021).","DOI":"10.1007\/978-3-030-77883-5_4"},{"issue":"4","key":"1163_CR10","doi-asserted-by":"publisher","first-page":"792","DOI":"10.1145\/6490.6503","volume":"33","author":"O Goldreich","year":"1986","unstructured":"Goldreich O., Goldwasser S., Micali S.: How to construct random functions. J. ACM 33(4), 792\u2013807 (1986).","journal-title":"J. ACM"},{"key":"1163_CR11","doi-asserted-by":"crossref","unstructured":"Hubacek P., Wichs D.: On the communication complexity of secure function evaluation with long output. In: ITCS 2015, pp. 163\u2013172. ACM (2015).","DOI":"10.1145\/2688073.2688105"},{"key":"1163_CR12","doi-asserted-by":"crossref","unstructured":"Jain A., Lin H., Matt C., Sahai A.: How to leverage hardness of constant-degree expanding polynomials over $${\\mathbb{R}}$$ to build $$i{\\cal{O}}$$. In: EUROCRYPT 2019, pp. 251\u2013281. Springer (2019).","DOI":"10.1007\/978-3-030-17653-2_9"},{"key":"1163_CR13","unstructured":"Jain A., Lin H., Sahai A.: Simplifying constructions and assumptions for $$i{\\cal{O}} $$. In: Cryptology ePrint Archive, Report 2019\/1252 (2019)."},{"key":"1163_CR14","doi-asserted-by":"crossref","unstructured":"Jain A., Lin H., Sahai A.: Indistinguishability obfuscation from LPN over $${\\mathbb{F}}_{p}$$, DLIN, and PRGs in $${\\sf NC}^0$$. In: Cryptology ePrint Archive, Report 2021\/1334 (2021).","DOI":"10.1007\/978-3-031-06944-4_23"},{"key":"1163_CR15","doi-asserted-by":"crossref","unstructured":"Jain A., Lin H., Sahai A.: Indistinguishability obfuscation from well-founded assumptions. In: STOC 2021, pp. 60\u201373. ACM (2021).","DOI":"10.1145\/3406325.3451093"},{"key":"1163_CR16","doi-asserted-by":"crossref","unstructured":"Kaafarani A.E., Katsumata S.: Attribute-based signatures for unbounded circuits in the rom and efficient instantiations from lattices. In: PKC 2018, pp. 89\u2013119. Springer (2018).","DOI":"10.1007\/978-3-319-76581-5_4"},{"key":"1163_CR17","doi-asserted-by":"crossref","unstructured":"Koppula V., Lewko A.B., Waters B.: Indistinguishability obfuscation for turing machines with unbounded memory. In: STOC 2015, pp. 419\u2013428. ACM (2015).","DOI":"10.1145\/2746539.2746614"},{"key":"1163_CR18","unstructured":"Lin H., Matt C.: Pseudo flawed-smudging generators and their application to indistinguishability obfuscation. In: Cryptology ePrint Archive, Report 2018\/646 (2018)."},{"key":"1163_CR19","doi-asserted-by":"crossref","unstructured":"Maji H.K., Prabhakaran M., Rosulek M.: Attribute-based signatures. In: CT-RSA 2011, pp. 376\u2013392. Springer (2011).","DOI":"10.1007\/978-3-642-19074-2_24"},{"key":"1163_CR20","doi-asserted-by":"crossref","unstructured":"Okamoto T., Takashima K.: Efficient attribute-based signatures for non-monotone predicates in the standard model. In: PKC 2011, pp. 35\u201352. Springer (2011).","DOI":"10.1007\/978-3-642-19379-8_3"},{"key":"1163_CR21","doi-asserted-by":"crossref","unstructured":"Okamoto T., Pietrzak K., Waters B., Wichs D.: New realizations of somewhere statistically binding hashing and positional accumulators. In: ASIACRYPT 2015, pp. 121\u2013145. Springer (2015).","DOI":"10.1007\/978-3-662-48797-6_6"},{"key":"1163_CR22","doi-asserted-by":"crossref","unstructured":"Sahai A., Waters B.: How to use indistinguishability obfuscation: deniable encryption, and more. In: STOC 2014, pp. 475\u2013484. ACM (2014).","DOI":"10.1145\/2591796.2591825"},{"key":"1163_CR23","doi-asserted-by":"crossref","unstructured":"Sakai Y., Attrapadung N., Hanaoka G.: Attribute-based signatures for circuits from bilinear map. In: PKC 2016, pp. 283\u2013300. Springer (2016).","DOI":"10.1007\/978-3-662-49384-7_11"},{"key":"1163_CR24","doi-asserted-by":"crossref","unstructured":"Sakai Y., Katsumata S., Attrapadung N., Hanaoka G.: Attribute-based signatures for unbounded languages from standard assumptions. In: ASIACRYPT 2018, pp. 493\u2013522. Springer (2018).","DOI":"10.1007\/978-3-030-03329-3_17"},{"key":"1163_CR25","doi-asserted-by":"crossref","unstructured":"Tang F., Li H., Liang B.: Attribute-based signatures for circuits from multilinear maps. In: ISC 2014, pp. 54\u201371. Springer (2014).","DOI":"10.1007\/978-3-319-13257-0_4"},{"key":"1163_CR26","doi-asserted-by":"crossref","unstructured":"Tsabary R.: An equivalence between attribute-based signatures and homomorphic signatures, and new constructions for both. In: TCC 2018, pp. 489\u2013518. Springer (2018).","DOI":"10.1007\/978-3-319-70503-3_16"}],"container-title":["Designs, Codes and Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-022-01163-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10623-022-01163-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-022-01163-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,20]],"date-time":"2023-04-20T20:08:51Z","timestamp":1682021331000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10623-022-01163-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,17]]},"references-count":26,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2023,5]]}},"alternative-id":["1163"],"URL":"https:\/\/doi.org\/10.1007\/s10623-022-01163-8","relation":{},"ISSN":["0925-1022","1573-7586"],"issn-type":[{"value":"0925-1022","type":"print"},{"value":"1573-7586","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,1,17]]},"assertion":[{"value":"26 June 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 May 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 December 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 January 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}