{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T16:45:38Z","timestamp":1761324338695},"reference-count":50,"publisher":"Institute of Electronics, Information and Communications Engineers (IEICE)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEICE Trans. Fundamentals"],"published-print":{"date-parts":[[2021,1,1]]},"DOI":"10.1587\/transfun.2020cip0003","type":"journal-article","created":{"date-parts":[[2020,12,31]],"date-time":"2020-12-31T22:11:46Z","timestamp":1609452706000},"page":"25-57","source":"Crossref","is-referenced-by-count":2,"title":["Efficient Attribute-Based Signatures for Unbounded Arithmetic Branching Programs"],"prefix":"10.1587","volume":"E104.A","author":[{"given":"Pratish","family":"DATTA","sequence":"first","affiliation":[{"name":"NTT Research, Inc."}]},{"given":"Tatsuaki","family":"OKAMOTO","sequence":"additional","affiliation":[{"name":"NTT Research, Inc."}]},{"given":"Katsuyuki","family":"TAKASHIMA","sequence":"additional","affiliation":[{"name":"Mitsubishi Electric Corporation"}]}],"member":"532","reference":[{"key":"1","doi-asserted-by":"crossref","unstructured":"[1] P. Datta, T. Okamoto, and K. Takashima, \u201cEfficient attribute-based signatures for unbounded arithmetic branching programs,\u201d PKC 2019, pp.127-158, Springer, 2019. 10.1007\/978-3-030-17253-4_5","DOI":"10.1007\/978-3-030-17253-4_5"},{"key":"2","unstructured":"[2] H. Maji, M. Prabhakaran, and M. Rosulek, \u201cAttribute-based signatures: Achieving attribute-privacy and collusion-resistance,\u201d Cryptology ePrint Archive, Report 2008\/328, 2008."},{"key":"3","doi-asserted-by":"crossref","unstructured":"[3] W. Diffie and M. Hellman, \u201cNew directions in cryptography,\u201d IEEE Trans. Inf. Theory, vol.22, no.6, pp.644-654, 1976. 10.1109\/tit.1976.1055638","DOI":"10.1109\/TIT.1976.1055638"},{"key":"4","doi-asserted-by":"publisher","unstructured":"[4] H.K. Maji, M. Prabhakaran, and M. Rosulek, \u201cAttribute-based signatures,\u201d CT-RSA 2011, pp.376-392, Springer, 2011. 10.1007\/978-3-642-19074-2_24","DOI":"10.1007\/978-3-642-19074-2_24"},{"key":"5","unstructured":"[5] H.K. Maji, M. Prabhakaran, and M. Rosulek, \u201cAttribute-based signatures,\u201d Cryptology ePrint Archive, Report 2010\/595, 2010. This is the full version of [4]."},{"key":"6","doi-asserted-by":"crossref","unstructured":"[6] S.F. Shahandashti and R. Safavi-Naini, \u201cThreshold attribute-based signatures and their application to anonymous credential systems,\u201d AFRICACRYPT 2009, pp.198-216, Springer, 2009. 10.1007\/978-3-642-02384-2_13","DOI":"10.1007\/978-3-642-02384-2_13"},{"key":"7","unstructured":"[7] J. Li and K. Kim, \u201cAttribute-based ring signatures,\u201d Cryptology ePrint Archive, Report 2008\/394, 2008."},{"key":"8","doi-asserted-by":"crossref","unstructured":"[8] J. Li, M.H. Au, W. Susilo, D. Xie, and K. Ren, \u201cAttribute-based signature and its applications,\u201d ASIACCS 2010, pp.60-69, ACM, 2010. 10.1145\/1755688.1755697","DOI":"10.1145\/1755688.1755697"},{"key":"9","doi-asserted-by":"crossref","unstructured":"[9] J. Herranz, F. Laguillaumie, B. Libert, and C. R\u00e0fols, \u201cShort attribute-based signatures for threshold predicates,\u201d CT-RSA 2012, pp.51-67, Springer, 2012. 10.1007\/978-3-642-27954-6_4","DOI":"10.1007\/978-3-642-27954-6_4"},{"key":"10","doi-asserted-by":"crossref","unstructured":"[10] T. Okamoto and K. Takashima, \u201cEfficient attribute-based signatures for non-monotone predicates in the standard model,\u201d PKC-2011, pp.35-52, Springer, 2011. 10.1007\/978-3-642-19379-8_3","DOI":"10.1007\/978-3-642-19379-8_3"},{"key":"11","doi-asserted-by":"crossref","unstructured":"[11] T. Okamoto and K. Takashima, \u201cDecentralized attribute-based signatures,\u201d PKC 2013, pp.125-142, Springer, 2013. 10.1007\/978-3-642-36362-7_9","DOI":"10.1007\/978-3-642-36362-7_9"},{"key":"12","doi-asserted-by":"publisher","unstructured":"[12] A. El Kaafarani, E. Ghadafi, and D. Khader, \u201cDecentralized traceable attribute-based signatures,\u201d CT-RSA 2014, pp.327-348, Springer, 2014. 10.1007\/978-3-319-04852-9_17","DOI":"10.1007\/978-3-319-04852-9_17"},{"key":"13","unstructured":"[13] A. El Kaafarani and R. El Bansarkhani, \u201cPost-quantum attribute-based signatures from lattice assumptions,\u201d Cryptology ePrint Archive, Report 2016\/823, 2016."},{"key":"14","doi-asserted-by":"crossref","unstructured":"[14] F. Tang, H. Li, and B. Liang, \u201cAttribute-based signatures for circuits from multilinear maps,\u201d ISC 2014, pp.54-71, Springer, 2014. 10.1007\/978-3-319-13257-0_4","DOI":"10.1007\/978-3-319-13257-0_4"},{"key":"15","doi-asserted-by":"crossref","unstructured":"[15] Y. Sakai, N. Attrapadung, and G. Hanaoka, \u201cAttribute-based signatures for circuits from bilinear map,\u201d PKC 2016, pp.283-300, Springer, 2016. 10.1007\/978-3-662-49384-7_11","DOI":"10.1007\/978-3-662-49384-7_11"},{"key":"16","doi-asserted-by":"crossref","unstructured":"[16] R. Tsabary, \u201cAn equivalence between attribute-based signatures and homomorphic signatures, and new constructions for both,\u201d TCC 2017, pp.489-518, Springer, 2017. 10.1007\/978-3-319-70503-3_16","DOI":"10.1007\/978-3-319-70503-3_16"},{"key":"17","doi-asserted-by":"crossref","unstructured":"[17] A. El Kaafarani and S. Katsumata, \u201cAttribute-based signatures for unbounded circuits in the ROM and efficient instantiations from lattices,\u201d PKC 2018, pp.89-119, Springer, 2018. 10.1007\/978-3-319-76581-5_4","DOI":"10.1007\/978-3-319-76581-5_4"},{"key":"18","unstructured":"[18] P. Datta, R. Dutta, and S. Mukhopadhyay, \u201cAttribute-based signatures for turing machines,\u201d Cryptology ePrint Archive, Report 2017\/801, 2017."},{"key":"19","doi-asserted-by":"crossref","unstructured":"[19] Y. Sakai, S. Katsumata, N. Attrapadung, and G. Hanaoka, \u201cAttribute-based signatures for unbounded languages from standard assumptions,\u201d ASIACRYPT 2018, pp.493-522, Springer, 2018. 10.1007\/978-3-030-03329-3_17","DOI":"10.1007\/978-3-030-03329-3_17"},{"key":"20","doi-asserted-by":"publisher","unstructured":"[20] M. Bellare and G. Fuchsbauer, \u201cPolicy-based signatures,\u201d PKC 2014, pp.520-537, Springer, 2014. 10.1007\/978-3-642-54631-0_30","DOI":"10.1007\/978-3-642-54631-0_30"},{"key":"21","doi-asserted-by":"crossref","unstructured":"[21] T. Okamoto and K. Takashima, \u201cEfficient attribute-based signatures for non-monotone predicates in the standard model,\u201d Cryptology ePrint Archive, Report 2011\/700, 2011. This is the full version of [10].","DOI":"10.1007\/978-3-642-19379-8_3"},{"key":"22","doi-asserted-by":"publisher","unstructured":"[22] M. F\u00fcrer, \u201cFaster integer multiplication,\u201d SIAM J. Comput., vol.39, no.3, pp.979-1005, 2009. 10.1137\/070711761","DOI":"10.1137\/070711761"},{"key":"23","doi-asserted-by":"publisher","unstructured":"[23] B. Applebaum, Y. Ishai, and E. Kushilevitz, \u201cHow to garble arithmetic circuits,\u201d SIAM J. Comput., vol.43, no.2, pp.905-929, 2014. 10.1137\/120875193","DOI":"10.1137\/120875193"},{"key":"24","doi-asserted-by":"crossref","unstructured":"[24] M. Keller, E. Orsini, and P. Scholl, \u201cMASCOT: Faster malicious arithmetic secure computation with oblivious transfer,\u201d ACM-CCS 2016, pp.830-842, ACM, 2016. 10.1145\/2976749.2978357","DOI":"10.1145\/2976749.2978357"},{"key":"25","doi-asserted-by":"publisher","unstructured":"[25] B. Parno, J. Howell, C. Gentry, and M. Raykova, \u201cPinocchio: Nearly practical verifiable computation,\u201d Commun. ACM, vol.59, no.2, pp.103-112, 2016. 10.1145\/2856449","DOI":"10.1145\/2856449"},{"key":"26","unstructured":"[26] Y. Ishai and E. Kushilevitz, \u201cPrivate simultaneous messages protocols with applications,\u201d ITCS 1997, pp.174-183, IEEE, 1997. 10.1109\/istcs.1997.595170"},{"key":"27","doi-asserted-by":"crossref","unstructured":"[27] Y. Ishai and E. Kushilevitz, \u201cPerfect constant-round secure computation via perfect randomizing polynomials,\u201d ICALP 2002, pp.244-256, Springer, 2002. 10.1007\/3-540-45465-9_22","DOI":"10.1007\/3-540-45465-9_22"},{"key":"28","doi-asserted-by":"crossref","unstructured":"[28] M. Abe, M. Chase, B. David, M. Kohlweiss, R. Nishimaki, and M. Ohkubo, \u201cConstant-size structure-preserving signatures: Generic constructions and simple assumptions,\u201d ASIACRYPT 2012, pp.4-24, Springer, 2012. 10.1007\/978-3-642-34961-4_3","DOI":"10.1007\/978-3-642-34961-4_3"},{"key":"29","doi-asserted-by":"publisher","unstructured":"[29] D.M. Freeman, \u201cConverting pairing-based cryptosystems from composite-order groups to prime-order groups,\u201d EUROCRYPT 2010, pp.44-61, Springer, 2010. 10.1007\/978-3-642-13190-5_3","DOI":"10.1007\/978-3-642-13190-5_3"},{"key":"30","doi-asserted-by":"crossref","unstructured":"[30] A. Guillevic, \u201cComparing the pairing efficiency over composite-order and prime-order elliptic curves,\u201d ACNS 2013, pp.357-372, Springer, 2013. 10.1007\/978-3-642-38980-1_22","DOI":"10.1007\/978-3-642-38980-1_22"},{"key":"31","doi-asserted-by":"publisher","unstructured":"[31] R. Barbulescu, P. Gaudry, A. Joux, and E. Thom\u00e9, \u201cA heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic,\u201d EUROCRYPT 2014, pp.1-16, Springer, 2014. 10.1007\/978-3-642-55220-5_1","DOI":"10.1007\/978-3-642-55220-5_1"},{"key":"32","doi-asserted-by":"publisher","unstructured":"[32] F. G\u00f6lo\u011flu, R. Granger, G. McGuire, and J. Zumbr\u00e4gel, \u201cOn the function field sieve and the impact of higher splitting probabilities,\u201d CRYPTO 2013, pp.109-128, Springer, 2013. 10.1007\/978-3-642-40084-1_7","DOI":"10.1007\/978-3-642-40084-1_7"},{"key":"33","doi-asserted-by":"publisher","unstructured":"[33] A. Joux, \u201cFaster index calculus for the medium prime case application to 1175-bit and 1425-bit finite fields,\u201d EUROCRYPT 2013, pp.177-193, Springer, 2013. 10.1007\/978-3-642-38348-9_11","DOI":"10.1007\/978-3-642-38348-9_11"},{"key":"34","doi-asserted-by":"publisher","unstructured":"[34] A. Joux, \u201cA new index calculus algorithm with complexity <i>l<\/i>(1\/4+<i>o<\/i>(1)) in small characteristic,\u201d SAC 2013, pp.355-379, Springer, 2013. 10.1007\/978-3-662-43414-7_18","DOI":"10.1007\/978-3-662-43414-7_18"},{"key":"35","unstructured":"[35] M. Karchmer and A. Wigderson, \u201cOn span programs,\u201d Structure in Complexity Theory Conference 1993, pp.102-111, IEEE, 1993. 10.1109\/sct.1993.336536"},{"key":"36","doi-asserted-by":"crossref","unstructured":"[36] Y. Ishai and H. Wee, \u201cPartial garbling schemes and their applications,\u201d ICALP 2014, pp.650-662, Springer, 2014. 10.1007\/978-3-662-43948-7_54","DOI":"10.1007\/978-3-662-43948-7_54"},{"key":"37","doi-asserted-by":"crossref","unstructured":"[37] T. Okamoto and K. Takashima, \u201cHierarchical predicate encryption for inner-products,\u201d ASIACRYPT 2009, pp.214-231, Springer, 2009. 10.1007\/978-3-642-10366-7_13","DOI":"10.1007\/978-3-642-10366-7_13"},{"key":"38","doi-asserted-by":"publisher","unstructured":"[38] T. Okamoto and K. Takashima, \u201cFully secure functional encryption with general relations from the decisional linear assumption,\u201d CRYPTO 2010, pp.191-208, Springer, 2010. 10.1007\/978-3-642-14623-7_11","DOI":"10.1007\/978-3-642-14623-7_11"},{"key":"39","doi-asserted-by":"crossref","unstructured":"[39] J. Tomida, M. Abe, and T. Okamoto, \u201cEfficient functional encryption for inner-product values with full-hiding security,\u201d ISC 2016, pp.408-425, Springer, 2016. 10.1007\/978-3-319-45871-7_24","DOI":"10.1007\/978-3-319-45871-7_24"},{"key":"40","doi-asserted-by":"crossref","unstructured":"[40] V. Shoup, \u201cLower bounds for discrete logarithms and related problems,\u201d EUROCRYPT 1997, pp.256-266, Springer, 1997. 10.1007\/3-540-69053-0_18","DOI":"10.1007\/3-540-69053-0_18"},{"key":"41","doi-asserted-by":"crossref","unstructured":"[41] T. Okamoto and K. Takashima, \u201cFully secure unbounded inner-product and attribute-based encryption,\u201d ASIACRYPT 2012, pp.349-366, Springer, 2012. 10.1007\/978-3-642-34961-4_22","DOI":"10.1007\/978-3-642-34961-4_22"},{"key":"42","doi-asserted-by":"crossref","unstructured":"[42] T. Okamoto and K. Takashima, \u201cFully secure unbounded inner-product and attribute-based encryption,\u201d Cryptology ePrint Archive, Report 2012\/671, 2012. This is the full version of [41].","DOI":"10.1007\/978-3-642-34961-4_22"},{"key":"43","doi-asserted-by":"crossref","unstructured":"[44] B. Waters, \u201cCiphertext-policy attribute-based encryption: An expressive, efficient, and provably secure realization,\u201d PKC 2011, pp.53-70, Springer, 2011. 10.1007\/978-3-642-19379-8_4","DOI":"10.1007\/978-3-642-19379-8_4"},{"key":"44","doi-asserted-by":"crossref","unstructured":"[45] B. Waters, \u201cDual system encryption: Realizing fully secure ibe and hibe under simple assumptions,\u201d CRYPTO 2009, pp.619-636, Springer, 2009. 10.1007\/978-3-642-03356-8_36","DOI":"10.1007\/978-3-642-03356-8_36"},{"key":"45","doi-asserted-by":"publisher","unstructured":"[46] A. Lewko and B. Waters, \u201cNew techniques for dual system encryption and fully secure hibe with short ciphertexts,\u201d TCC 2010, pp.455-479, Springer, 2010. 10.1007\/978-3-642-11799-2_27","DOI":"10.1007\/978-3-642-11799-2_27"},{"key":"46","doi-asserted-by":"crossref","unstructured":"[47] K. Takashima, \u201cNew proof techniques for DLIN-based adaptively secure attribute-based encryption,\u201d ACISP 2017, pp.85-105, Springer, 2017. 10.1007\/978-3-319-60055-0_5","DOI":"10.1007\/978-3-319-60055-0_5"},{"key":"47","doi-asserted-by":"crossref","unstructured":"[48] L. Kowalczyk, J. Liu, T. Malkin, and K. Meiyappan, \u201cMitigating the one-use restriction in attribute-based encryption,\u201d ICISC 2018, pp.23-36, Springer, 2018. 10.1007\/978-3-030-12146-4_2","DOI":"10.1007\/978-3-030-12146-4_2"},{"key":"48","doi-asserted-by":"crossref","unstructured":"[49] L. Kowalczyk and H. Wee, \u201cCompact adaptively secure abe for NC<sup>1<\/sup> from <i>k<\/i>-Lin,\u201d EUROCRYPT 2019, pp.3-33, Springer, 2019. 10.1007\/978-3-030-17656-3","DOI":"10.1007\/978-3-030-17653-2_1"},{"key":"49","doi-asserted-by":"publisher","unstructured":"[50] L. Kowalczyk and H. Wee, \u201cCompact adaptively secure abe for NC<sup>1<\/sup> from <i>k<\/i>-Lin,\u201d J. Cryptol., vol.33, no.3, pp.954-1002, 2020. 10.1007\/s00145-019-09335-x","DOI":"10.1007\/s00145-019-09335-x"},{"key":"50","doi-asserted-by":"publisher","unstructured":"[51] J. Groth and A. Sahai, \u201cEfficient non-interactive proof systems for bilinear groups,\u201d EUROCRYPT 2008, pp.415-432, Springer, 2008. 10.1007\/978-3-540-78967-3_24","DOI":"10.1007\/978-3-540-78967-3_24"}],"container-title":["IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transfun\/E104.A\/1\/E104.A_2020CIP0003\/_pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,1,2]],"date-time":"2021-01-02T03:37:17Z","timestamp":1609558637000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transfun\/E104.A\/1\/E104.A_2020CIP0003\/_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,1]]},"references-count":50,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021]]}},"URL":"https:\/\/doi.org\/10.1587\/transfun.2020cip0003","relation":{},"ISSN":["0916-8508","1745-1337"],"issn-type":[{"value":"0916-8508","type":"print"},{"value":"1745-1337","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1,1]]}}}