{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,1]],"date-time":"2026-03-01T05:23:56Z","timestamp":1772342636922,"version":"3.50.1"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2016,1,14]],"date-time":"2016-01-14T00:00:00Z","timestamp":1452729600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptol"],"published-print":{"date-parts":[[2017,4]]},"DOI":"10.1007\/s00145-015-9226-0","type":"journal-article","created":{"date-parts":[[2016,1,15]],"date-time":"2016-01-15T03:54:17Z","timestamp":1452830057000},"page":"444-469","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":36,"title":["Secret-Sharing for NP"],"prefix":"10.1007","volume":"30","author":[{"given":"Ilan","family":"Komargodski","sequence":"first","affiliation":[]},{"given":"Moni","family":"Naor","sequence":"additional","affiliation":[]},{"given":"Eylon","family":"Yogev","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,1,14]]},"reference":[{"key":"9226_CR1","doi-asserted-by":"crossref","unstructured":"N. Alon, J. Spencer, The Probabilistic Method (3rd ed.) (Wiley, 2008)","DOI":"10.1002\/9780470277331"},{"key":"9226_CR2","unstructured":"A. Beimel, Secret-sharing schemes: a survey, in 3rd International Workshop, IWCC (2011), pp. 11\u201346"},{"key":"9226_CR3","doi-asserted-by":"crossref","unstructured":"B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Sahai, S.\u00a0P. Vadhan, K. Yang, On the (im)possibility of obfuscating programs, in CRYPTO. Lecture Notes in Computer Science, vol. 2139 (Springer, 2001), pp. 1\u201318","DOI":"10.1007\/3-540-44647-8_1"},{"key":"9226_CR4","doi-asserted-by":"crossref","unstructured":"B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Sahai, S. P. Vadhan, K. Yang, On the (im)possibility of obfuscating programs. J. ACM\u00a059(2), 6 (2012). Preliminary version appeared in CRYPTO 2001","DOI":"10.1145\/2160158.2160159"},{"key":"9226_CR5","unstructured":"B. Barak, S. Garg, Y. T. Kalai, O. Paneth, A. Sahai, Protecting obfuscation against algebraic attacks, in 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, EYROCRYPTO (2014), pp. 221\u2013238"},{"key":"9226_CR6","doi-asserted-by":"crossref","unstructured":"A. Beimel, Y. Ishai, On the power of nonlinear secrect-sharing. SIAM J. Discrete Math.\u00a019(1), 258\u2013280 (2005)","DOI":"10.1137\/S0895480102412868"},{"key":"9226_CR7","unstructured":"J. C. Benaloh, J. Leichter, Generalized secret sharing and monotone functions, in 8th Annual International Cryptology Conference, CRYPTO (1988), pp. 27\u201335"},{"key":"9226_CR8","doi-asserted-by":"crossref","unstructured":"G. R. Blakley, Safeguarding cryptographic keys. Proc. AFIPS Natl. Comput. Conf.\u00a022, 313\u2013317 (1979)","DOI":"10.1109\/MARK.1979.8817296"},{"key":"9226_CR9","doi-asserted-by":"crossref","unstructured":"M. Bellare, P. Rogaway, Robust computational secret sharing and a unified account of classical secret-sharing goals, in ACM Conference on Computer and Communications Security (ACM, 2007), pp. 172\u2013184","DOI":"10.1145\/1315245.1315268"},{"key":"9226_CR10","unstructured":"Z. Brakerski, G.\u00a0N. Rothblum, Black-box obfuscation for \n                    \n                      \n                    \n                    $$d$$\n                    \n                      \n                        d\n                      \n                    \n                  -CNFs, in Innovations in Theoretical Computer Science, ITCS (2014), pp. 235\u2013250"},{"key":"9226_CR11","unstructured":"Z. Brakerski, G.\u00a0N. Rothblum, Virtual black-box obfuscation for all circuits via generic graded encoding, in 11th Theory of Cryptography Conference, TCC (2014), pp. 1\u201325"},{"key":"9226_CR12","unstructured":"D. Boneh, M. Zhandry, Multiparty key exchange, efficient traitor tracing, and more from indistinguishability obfuscation, in 34th Annual Cryptology Conference, CRYPTO (2014), pp. 480\u2013499"},{"key":"9226_CR13","doi-asserted-by":"crossref","unstructured":"C. Dwork, M. Naor, O. Reingold, L.\u00a0J. Stockmeyer, Magic functions. J. ACM\u00a050(6), 852\u2013921 (2003)","DOI":"10.1145\/950620.950623"},{"key":"9226_CR14","unstructured":"S. Garg, C. Gentry, S. Halevi, M. Raykova, A. Sahai, B. Waters, Candidate indistinguishability obfuscation and functional encryption for all circuits, in 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS (2013), pp. 40\u201349"},{"key":"9226_CR15","unstructured":"S. Garg, C. Gentry, A. Sahai, B. Waters, Witness encryption and its applications, in Symposium on Theory of Computing Conference, STOC (2013), pp. 467\u2013476"},{"key":"9226_CR16","doi-asserted-by":"crossref","unstructured":"C. Gentry, A.\u00a0B. Lewko, A. Sahai, B. Waters, Indistinguishability obfuscation from the multilinear subgroup elimination assumption. IACR Cryptol. ePrint Arch.\u00a02014, 309 (2014)","DOI":"10.1109\/FOCS.2015.19"},{"key":"9226_CR17","unstructured":"C. Gentry, A.\u00a0B. Lewko, B. Waters, Witness encryption from instance independent assumptions, in 34th Annual Cryptology Conference, CRYPTO (2014), pp. 426\u2013443"},{"key":"9226_CR18","doi-asserted-by":"crossref","unstructured":"S. Goldwasser, S. Micali, Probabilistic encryption. J. Comput. Syst. Sci.\u00a028(2), 270\u2013299 (1984)","DOI":"10.1016\/0022-0000(84)90070-9"},{"key":"9226_CR19","unstructured":"M. Grigni, M. Sipser, Monotone complexity, in LMS Workshop on Boolean Function Complexity (1992), pp. 57\u201375"},{"key":"9226_CR20","doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad, R. Impagliazzo, L.\u00a0A. Levin, M. Luby, A pseudorandom generator from any one-way function. SIAM J. Comput.\u00a028(4), 1364\u20131396 (1999)","DOI":"10.1137\/S0097539793244708"},{"key":"9226_CR21","unstructured":"R. Impagliazzo, A personal view of average-case complexity, in 10th Annual Structure in Complexity Theory Conference (1995), pp. 134\u2013147"},{"key":"9226_CR22","doi-asserted-by":"crossref","unstructured":"M. Ito, A. Saito, T. Nishizeki, Multiple assignment scheme for sharing secret. J. Cryptol.\u00a06(1), 15\u201320 (1993)","DOI":"10.1007\/BF02620229"},{"key":"9226_CR23","unstructured":"I. Komargodski, T. Moran, M. Naor, R. Pass, A. Rosen, E. Yogev, One-way functions and (im)perfect obfuscation, in 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS (2014), pp. 374\u2013383"},{"key":"9226_CR24","unstructured":"H. Krawczyk, Secret sharing made short, in 13th Annual International Cryptology Conference, CRYPTO (1993), pp. 136\u2013146"},{"key":"9226_CR25","unstructured":"M. Karchmer, A. Wigderson, On span programs, in 8th Annual Structure in Complexity Theory Conference (1993), pp. 102\u2013111"},{"key":"9226_CR26","doi-asserted-by":"crossref","unstructured":"I. Komargodski, M. Zhandry, Cutting-edge cryptography through the lens of secret sharing. IACR Cryptol. ePrint Arch.\u00a0 2015, 735 (2015). To appear in TCC 2016-A","DOI":"10.1007\/978-3-662-49099-0_17"},{"key":"9226_CR27","doi-asserted-by":"crossref","unstructured":"M. Naor, Bit commitment using pseudorandomness. J. Cryptol.\u00a0 4(2), 151\u2013158 (1991)","DOI":"10.1007\/BF00196774"},{"key":"9226_CR28","unstructured":"M. Naor, On cryptographic assumptions and challenges, in 23rd Annual International Cryptology Conference, CRYPTO (2003), pp. 96\u2013109"},{"key":"9226_CR29","unstructured":"M. Naor, Secret sharing for access structures beyond \n                    \n                      \n                    \n                    $${\\sf P}$$\n                    \n                      \n                        P\n                      \n                    \n                   (2006). Slides: \n                    http:\/\/www.wisdom.weizmann.ac.il\/~naor\/PAPERS\/minicrypt.html"},{"key":"9226_CR30","unstructured":"R. Pass, K. Seth, S. Telang, Indistinguishability obfuscation from semantically-secure multilinear encodings, in 34th Annual Cryptology Conference, CRYPTO (2014), pp. 500\u2013517"},{"key":"9226_CR31","unstructured":"A.\u00a0A. Razborov, Lower bounds for the monotone complexity of some Boolean functions. Dokl. Ak. Nauk. SSSR\u00a0 281, 798\u2013801 (1985). English translation in: Soviet Math. Dokl. \u00a031, 354\u2013357 (1985)"},{"key":"9226_CR32","doi-asserted-by":"crossref","unstructured":"A. Shamir, How to share a secret. Commun. ACM \u00a022(11), 612\u2013613 (1979)","DOI":"10.1145\/359168.359176"},{"key":"9226_CR33","unstructured":"A. Sahai, B. Waters, How to use indistinguishability obfuscation: deniable encryption, and more, in Symposium on Theory of Computing, STOC (2014), pp. 475\u2013484"},{"key":"9226_CR34","unstructured":"V.\u00a0Vinod, A. Narayanan, K.\u00a0Srinathan, C.\u00a0P. Rangan, K. Kim, On the power of computational secret sharing, in 4th International Conference on Cryptology in India, INDOCRYPT (2003), pp. 162\u2013176"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-015-9226-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00145-015-9226-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-015-9226-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-015-9226-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T08:14:07Z","timestamp":1586333647000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00145-015-9226-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1,14]]},"references-count":34,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,4]]}},"alternative-id":["9226"],"URL":"https:\/\/doi.org\/10.1007\/s00145-015-9226-0","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,1,14]]},"assertion":[{"value":"7 January 2015","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 October 2015","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 January 2016","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}