{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,11]],"date-time":"2024-08-11T00:52:31Z","timestamp":1723337551513},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2011,9,6]],"date-time":"2011-09-06T00:00:00Z","timestamp":1315267200000},"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":[[2012,10]]},"DOI":"10.1007\/s00145-011-9104-3","type":"journal-article","created":{"date-parts":[[2011,9,6]],"date-time":"2011-09-06T16:17:00Z","timestamp":1315325820000},"page":"557-600","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Graph Coloring Applied to Secure Computation in Non-Abelian Groups"],"prefix":"10.1007","volume":"25","author":[{"given":"Yvo","family":"Desmedt","sequence":"first","affiliation":[]},{"given":"Josef","family":"Pieprzyk","sequence":"additional","affiliation":[]},{"given":"Ron","family":"Steinfeld","sequence":"additional","affiliation":[]},{"given":"Xiaoming","family":"Sun","sequence":"additional","affiliation":[]},{"given":"Christophe","family":"Tartary","sequence":"additional","affiliation":[]},{"given":"Huaxiong","family":"Wang","sequence":"additional","affiliation":[]},{"given":"Andrew Chi-Chih","family":"Yao","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,9,6]]},"reference":[{"key":"9104_CR1","doi-asserted-by":"publisher","DOI":"10.1002\/0471722154","volume-title":"The Probabilistic Method","author":"N. Alon","year":"2000","unstructured":"N. Alon, J.H. Spencer, The Probabilistic Method (Wiley-Interscience, New York, 2000)"},{"key":"9104_CR2","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1145\/72981.72995","volume-title":"8th Annual ACM Symposium on Principles of Distributed Computing","author":"J. Bar-Ilan","year":"1989","unstructured":"J. Bar-Ilan, D. Beaver, Non-cryptographic fault-tolerant computing in a constant number of rounds of interaction, in 8th Annual ACM Symposium on Principles of Distributed Computing (ACM, New York, 1989), pp.\u00a0201\u2013209"},{"key":"9104_CR3","first-page":"1","volume-title":"18th Annual ACM Symposium on Theory of Computing","author":"D.A. Barrington","year":"1986","unstructured":"D.A. Barrington, Bounded-width polynomial-size branching programs recognize exactly those languages in NC\n                  1, in 18th Annual ACM Symposium on Theory of Computing (ACM, New York, 1986), pp.\u00a01\u20135"},{"key":"9104_CR4","first-page":"1","volume-title":"20th Annual ACM Symposium on Theory of Computing","author":"M. Ben-Or","year":"1988","unstructured":"M. Ben-Or, S. Goldwasser, A. Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, in 20th Annual ACM Symposium on Theory of Computing (ACM, New York, 1988), pp.\u00a01\u201310"},{"key":"9104_CR5","series-title":"Lecture Notes in Computer Science","first-page":"251","volume-title":"Advances in Cryptology: Crypto\u201986","author":"J. Benaloh","year":"1987","unstructured":"J. Benaloh, Secret sharing homomorphisms: keeping shares of a secret, in Advances in Cryptology: Crypto\u201986. Lecture Notes in Computer Science, vol.\u00a0263 (Springer, Berlin, 1987), pp. 251\u2013260"},{"key":"9104_CR6","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139167383","volume-title":"Percolation","author":"B. Bollob\u00e0s","year":"2006","unstructured":"B. Bollob\u00e0s, O. Riordan, Percolation (Cambridge University Press, Cambridge, 2006)"},{"key":"9104_CR7","first-page":"11","volume-title":"20th Annual ACM Symposium on Theory of Computing","author":"D. Chaum","year":"1988","unstructured":"D. Chaum, C. Cr\u00e9peau, I. Damg\u00e5rd, Multi-party unconditionally secure protocols, in 20th Annual ACM Symposium on Theory of Computing (ACM, New York, 1988), pp.\u00a011\u201319"},{"key":"9104_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1007\/3-540-39200-9_37","volume-title":"Advances in Cryptology: Eurocrypt\u201903","author":"R. Cramer","year":"2003","unstructured":"R. Cramer, S. Fehr, Y. Ishai, E. Kushilevitz, Efficient multi-party computation over rings, in Advances in Cryptology: Eurocrypt\u201903. Lecture Notes in Computer Science, vol.\u00a02656 (Springer, Berlin, 2003), pp.\u00a0596\u2013613"},{"key":"9104_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"572","DOI":"10.1007\/978-3-540-74143-5_32","volume-title":"Advances in Cryptology\u2014Crypto\u201907","author":"I. Damg\u00e5rd","year":"2007","unstructured":"I. Damg\u00e5rd, J.B. Nielsen, Scalable and unconditionally secure multiparty computation, in Advances in Cryptology\u2014Crypto\u201907. Lecture Notes in Computer Science, vol.\u00a04622 (Springer, Berlin, 2007), pp.\u00a0572\u2013590"},{"key":"9104_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1007\/11681878_15","volume-title":"3rd Theory of Cryptography Conference","author":"I. Damg\u00e5rd","year":"2006","unstructured":"I. Damg\u00e5rd, M. Fitzi, E. Kiltz, J.B. Nielsen, T. Toft, Unconditionally secure constant-rounds multi-party computation for equality, comparison, bits and commitments, in 3rd Theory of Cryptography Conference. Lecture Notes in Computer Science, vol.\u00a03876 (Springer, Berlin, 2006), pp.\u00a0285\u2013304"},{"key":"9104_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1007\/978-3-642-13190-5_23","volume-title":"Advances in Cryptology\u2014Eurocrypt\u201910","author":"I. Damg\u00e5rd","year":"2010","unstructured":"I. Damg\u00e5rd, Y. Ishai, M. Kr\u00f8igaard, Perfectly secure multiparty computation and the computational overhead of cryptography, in Advances in Cryptology\u2014Eurocrypt\u201910. Lecture Notes in Computer Science, vol.\u00a06110 (Springer, Berlin, 2010), pp.\u00a0445\u2013465"},{"key":"9104_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1007\/11602613_29","volume-title":"16th International Symposium on Algorithms and Computation","author":"Y. Desmedt","year":"2005","unstructured":"Y. Desmedt, Y. Wang, M. Burmester, A\u00a0complete characterization of tolerable adversary structures for secure point-to-point transmissions, in 16th International Symposium on Algorithms and Computation. Lecture Notes in Computer Science, vol.\u00a03827 (Springer, Berlin, 2005), pp.\u00a0277\u2013287"},{"key":"9104_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"591","DOI":"10.1007\/978-3-540-74143-5_33","volume-title":"Advances in Cryptology\u2014Crypto\u201907","author":"Y. Desmedt","year":"2007","unstructured":"Y. Desmedt, J. Pieprzyk, R. Steinfeld, H. Wang, On secure multi-party computation in black-box groups, in Advances in Cryptology\u2014Crypto\u201907. Lecture Notes in Computer Science, vol.\u00a04622 (Springer, Berlin, 2007), pp.\u00a0591\u2013612"},{"key":"9104_CR14","series-title":"Graduate Texts in Mathematics","volume-title":"Graph Theory","author":"R. Diestel","year":"2000","unstructured":"R. Diestel, Graph Theory, 2nd edn. Graduate Texts in Mathematics (Springer, Berlin, 2000)","edition":"2"},{"issue":"6","key":"9104_CR15","doi-asserted-by":"publisher","first-page":"644","DOI":"10.1109\/TIT.1976.1055638","volume":"22","author":"W. Diffie","year":"1976","unstructured":"W. Diffie, M.E. Hellman, New directions in cryptography. IEEE Trans. Inf. Theory\n                  22(6), 644\u2013654 (1976)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"4","key":"9104_CR16","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1109\/TIT.1985.1057074","volume":"31","author":"T. El Gamal","year":"1985","unstructured":"T. El Gamal, A public-key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inf. Theory\n                  31(4), 469\u2013472 (1985)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9104_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1007\/3-540-48071-4_39","volume-title":"Advances in Cryptology\u2014Crypto\u201992","author":"Y. Frankel","year":"1993","unstructured":"Y. Frankel, Y. Desmedt, M. Burmester, Non-existence of homomorphic general sharing schemes for some key spaces (extended abstract), in Advances in Cryptology\u2014Crypto\u201992. Lecture Notes in Computer Science, vol.\u00a0740 (Springer, Berlin, 1993), pp.\u00a0549\u2013557"},{"key":"9104_CR18","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511721656","volume-title":"Foundations of Cryptography: Basic Applications","author":"O. Goldreich","year":"2004","unstructured":"O. Goldreich, Foundations of Cryptography: Basic Applications, vol.\u00a0II (Cambridge University Press, Cambridge, 2004)"},{"issue":"3","key":"9104_CR19","doi-asserted-by":"publisher","first-page":"790","DOI":"10.1214\/aoms\/1177706894","volume":"28","author":"J.M. Hammersley","year":"1957","unstructured":"J.M. Hammersley, Percolation processes: lower bounds for the critical probability. Ann. Math. Stat.\n                  28(3), 790\u2013795 (1957)","journal-title":"Ann. Math. Stat."},{"key":"9104_CR20","first-page":"25","volume-title":"16th Annual ACM Symposium on Principles of Distributed Computing","author":"M. Hirt","year":"1997","unstructured":"M. Hirt, U. Maurer, Complete characterization of adversaries tolerable in secure multi-party computation (extended abstract), in 16th Annual ACM Symposium on Principles of Distributed Computing (ACM, New York, 1997), pp.\u00a025\u201334"},{"key":"9104_CR21","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4899-2730-9","volume-title":"Percolation Theory for Mathematicians","author":"H. Kesten","year":"1982","unstructured":"H. Kesten, Percolation Theory for Mathematicians (Birkh\u00e4user, Basel, 1982)"},{"issue":"4","key":"9104_CR22","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1007\/s00145-001-0018-3","volume":"15","author":"S.S. Magliveras","year":"2002","unstructured":"S.S. Magliveras, D.R. Stinson, T. van Trung, New approaches to designing public key cryptosystems using one-way functions and trapdoors in finite groups. J.\u00a0Cryptol.\n                  15(4), 285\u2013297 (2002)","journal-title":"J.\u00a0Cryptol."},{"key":"9104_CR23","series-title":"Advanced Courses in Mathematics\u2014CRM Barcelona","volume-title":"Group-Based Cryptography","author":"A. Myasnikov","year":"2008","unstructured":"A. Myasnikov, V. Shpilrain, A. Ushakov, Group-Based Cryptography. Advanced Courses in Mathematics\u2014CRM Barcelona (Birkh\u00e4user, Basel, 2008)"},{"key":"9104_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"470","DOI":"10.1007\/3-540-44647-8_28","volume-title":"Advances in Cryptology\u2014Crypto\u201901","author":"S.-H. Paeng","year":"2001","unstructured":"S.-H. Paeng, K.-C. Ha, J.H. Kim, S. Chee, C. Park, New public key cryptosystem using finite non Abelian groups, in Advances in Cryptology\u2014Crypto\u201901. Lecture Notes in Computer Science, vol.\u00a02139 (Springer, Berlin, 2001), pp. 470\u2013485"},{"issue":"2","key":"9104_CR25","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1145\/359340.359342","volume":"21","author":"R.L. Rivest","year":"1978","unstructured":"R.L. Rivest, A. Shamir, L.M. Adleman, A\u00a0method for obtaining digital signatures and public key cryptosystems. Commun. ACM\n                  21(2), 120\u2013126 (1978)","journal-title":"Commun. ACM"},{"issue":"11","key":"9104_CR26","doi-asserted-by":"publisher","first-page":"612","DOI":"10.1145\/359168.359176","volume":"22","author":"A. Shamir","year":"1979","unstructured":"A. Shamir, How to share a secret. Commun. ACM\n                  22(11), 612\u2013613 (1979)","journal-title":"Commun. ACM"},{"key":"9104_CR27","doi-asserted-by":"crossref","first-page":"729","DOI":"10.4310\/MRL.2001.v8.n6.a4","volume":"8","author":"S. Smirnov","year":"2001","unstructured":"S. Smirnov, W. Werner, Critical exponents for two-dimensional percolation. Math. Res. Lett.\n                  8, 729\u2013744 (2001)","journal-title":"Math. Res. Lett."},{"key":"9104_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/978-3-540-89255-7_3","volume-title":"Advances in Cryptology\u2014Asiacrypt\u201908","author":"X. Sun","year":"2008","unstructured":"X. Sun, A.C.-C. Yao, C. Tartary, Graph design for secure multiparty computation over non-Abelian groups, in Advances in Cryptology\u2014Asiacrypt\u201908. Lecture Notes in Computer Science, vol.\u00a05350 (Springer, Berlin, 2008), pp.\u00a037\u201353"},{"key":"9104_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/3-540-39568-7_3","volume-title":"Advances in Cryptology\u2014Crypto\u201984","author":"N.R. Wagner","year":"1985","unstructured":"N.R. Wagner, M.R. Magyarik, A\u00a0public key encryption scheme based on the word problem, in Advances in Cryptology\u2014Crypto\u201984. Lecture Notes in Computer Science, vol.\u00a0196 (Springer, Berlin, 1985), pp.\u00a019\u201336"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-011-9104-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00145-011-9104-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-011-9104-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-011-9104-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T08:05:46Z","timestamp":1586333146000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00145-011-9104-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,9,6]]},"references-count":29,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,10]]}},"alternative-id":["9104"],"URL":"https:\/\/doi.org\/10.1007\/s00145-011-9104-3","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,9,6]]},"assertion":[{"value":"22 August 2010","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 September 2011","order":2,"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"}]}}