Nearly optimal robust secret sharing. Cheraghchi, M. In Proceedings of the IEEE International Symposium on Information Theory (ISIT), pages 2509–2513, 2016. Extended version in Designs, Codes and Cryptography.Link Paper doi abstract bibtex We prove that a known approach to improve Shamir's celebrated secret sharing scheme; i.e., adding an information-theoretic authentication tag to the secret, can make it robust for $n$ parties against any collusion of size $δ n$, for any constant $δ ∈ (0, 1/2)$. This result holds in the so-called ``non-rushing'' model in which the $n$ shares are submitted simultaneously for reconstruction. We thus obtain a fully explicit and robust secret sharing scheme in this model that is essentially optimal in all parameters including the share size which is $k(1+o(1)) + O(κ)$, where $k$ is the secret length and $κ$ is the security parameter. Like Shamir's scheme, in this modified scheme any set of more than $δ n$ honest parties can efficiently recover the secret. Using algebraic geometry codes instead of Reed-Solomon codes, the share length can be decreased to a constant (only depending on $δ$) while the number of shares $n$ can grow independently. In this case, when $n$ is large enough, the scheme satisfies the ``threshold'' requirement in an approximate sense; i.e., any set of $δ n(1+ρ)$ honest parties, for arbitrarily small $ρ > 0$, can efficiently reconstruct the secret.
@INPROCEEDINGS{ref:conf:Che16:SS,
author = {Mahdi Cheraghchi},
title = {Nearly optimal robust secret sharing},
booktitle = {Proceedings of the {IEEE International Symposium on
Information Theory (ISIT)}},
year = 2016,
pages = {2509--2513},
doi = {10.1109/ISIT.2016.7541751},
url_Link = {https://ieeexplore.ieee.org/document/7541751},
keywords = {Coding and information theory, Cryptography,
Algebraic coding theory},
abstract = {We prove that a known approach to improve Shamir's
celebrated secret sharing scheme; i.e., adding an
information-theoretic authentication tag to the
secret, can make it robust for $n$ parties against
any collusion of size $\delta n$, for any constant
$\delta \in (0, 1/2)$. This result holds in the
so-called ``non-rushing'' model in which the $n$
shares are submitted simultaneously for
reconstruction. We thus obtain a fully explicit and
robust secret sharing scheme in this model that is
essentially optimal in all parameters including the
share size which is $k(1+o(1)) + O(\kappa)$, where
$k$ is the secret length and $\kappa$ is the
security parameter. Like Shamir's scheme, in this
modified scheme any set of more than $\delta n$
honest parties can efficiently recover the secret.
Using algebraic geometry codes instead of
Reed-Solomon codes, the share length can be
decreased to a constant (only depending on $\delta$)
while the number of shares $n$ can grow
independently. In this case, when $n$ is large
enough, the scheme satisfies the ``threshold''
requirement in an approximate sense; i.e., any set
of $\delta n(1+\rho)$ honest parties, for
arbitrarily small $\rho > 0$, can efficiently
reconstruct the secret.},
note = {Extended version in {Designs, Codes and
Cryptography.}},
url_Paper = {https://eprint.iacr.org/2015/951}
}
Downloads: 0
{"_id":"H6jhCfaMiL8WkEY3s","bibbaseid":"cheraghchi-nearlyoptimalrobustsecretsharing-2016","authorIDs":["2n8MNophuzbeevTa8","3NEcSaujokmJYSDaa","3tFWxWs2qWeYAZx9a","4QNcMTdRiWr2gs8Sk","5KoQWR3vSjnsoZNz5","5i4QHRc5LGio8Mf5u","62bYDgAFwCxaQ4Q9T","685mTysGDdQJKGxEE","6sX76eTffL7p76peN","8NLx3B3FAvaK54hSK","9NZpjMJLG7dNWroGm","9aD4MPX9ELhsyJmaR","9aFgrqcc4j28kZn8n","A9wAgP7TPK9tw28qY","BJ6h7zrsT3L89RKSg","BWL9E9QxvrST7y7ym","Cht4qGZ9eYAvPygNC","D3NMRJpac7Z2oFz7x","EiL6Xv4GTWGB97B8H","F3Y934eNyTeEJsg6E","FDEj5Zwdm28pFcAnB","FJdyLy2TL3v973ge8","GxccwstJJuJ4rg7Dq","H4D7r27RcPALT5DCs","HP7szFXWBWFXXZhdA","HRX7xsd7ZkTNvr67D","Hj3KN5PTNMST8hD3b","JEvEPvDBYNNXgGBnp","JYpde2ppjXLva6cre","KFgC2dZG7jXYAgZ3T","NRg9mmaSB55QqzNnH","NWCEkq6XqRBCiGmMe","NpGaG45evixRFDMiF","NyDiXeBc7cuxdWrqh","P6pva6vpPZCz6ndh9","Py2jfYGNZKNt7nxL6","Q6E9aDkYPcbhngLMx","QYrXKExv3BPABZGyA","QupQWsidagmv2nu8Z","SGZ2YignSm7njeTxy","SSuyWxzudqBDgAosw","THz3CmRmH3zZ9Xfud","TTEBJzPHwrY4d2Qfi","Wzr7kB4bxMDqceidA","YedfCw6zcDLoWAWFL","YtTEuSL9GJ8pkKcZw","Z3w2d32WjDczZMeGo","aduB2YE7dcNtbHnAN","c8gPvTXFPd9NazgEw","d6HAadRZAtz97Y2so","dTBDNYCcYKNNdhqaR","ezDt3Lb3Q6Sbo2rfX","fXtxgjbjZswBmF45i","ftBpmnKRHoB2muB8u","gKxHau44e8gnmxs6v","hM29eSWZbASnmDdFf","hw7Q4GHDAHkLTAyeB","i6Ns5rSW8R3ifxeHg","jJcoL4QWRkJQ59LfW","kKvRZ55rH7sfbubS2","kdfqsAMqCFDhpuW3S","koPTGcsAkwhGbkAYe","manxWg6Q3ZC5vW4JE","pwN2yYKo5DdSDaZGs","qpSgMrJ8WQNupjbXX","sD5Wq95oeSzqGF9kn","uSGLWGoXjyDyozeEy","wCcpScxkvg5RkcmWm","xKz7kx4eXbnkHeNXP","xeiij9YsbXBbMjciP","yGxZz3yuu6krMRxgK","yjJrpKY5QmDe8SXvm","zaR6PwJ7aC9xWBpiy"],"author_short":["Cheraghchi, M."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"firstnames":["Mahdi"],"propositions":[],"lastnames":["Cheraghchi"],"suffixes":[]}],"title":"Nearly optimal robust secret sharing","booktitle":"Proceedings of the IEEE International Symposium on Information Theory (ISIT)","year":"2016","pages":"2509–2513","doi":"10.1109/ISIT.2016.7541751","url_link":"https://ieeexplore.ieee.org/document/7541751","keywords":"Coding and information theory, Cryptography, Algebraic coding theory","abstract":"We prove that a known approach to improve Shamir's celebrated secret sharing scheme; i.e., adding an information-theoretic authentication tag to the secret, can make it robust for $n$ parties against any collusion of size $δ n$, for any constant $δ ∈ (0, 1/2)$. This result holds in the so-called ``non-rushing'' model in which the $n$ shares are submitted simultaneously for reconstruction. We thus obtain a fully explicit and robust secret sharing scheme in this model that is essentially optimal in all parameters including the share size which is $k(1+o(1)) + O(κ)$, where $k$ is the secret length and $κ$ is the security parameter. Like Shamir's scheme, in this modified scheme any set of more than $δ n$ honest parties can efficiently recover the secret. Using algebraic geometry codes instead of Reed-Solomon codes, the share length can be decreased to a constant (only depending on $δ$) while the number of shares $n$ can grow independently. In this case, when $n$ is large enough, the scheme satisfies the ``threshold'' requirement in an approximate sense; i.e., any set of $δ n(1+ρ)$ honest parties, for arbitrarily small $ρ > 0$, can efficiently reconstruct the secret.","note":"Extended version in Designs, Codes and Cryptography.","url_paper":"https://eprint.iacr.org/2015/951","bibtex":"@INPROCEEDINGS{ref:conf:Che16:SS,\n author =\t {Mahdi Cheraghchi},\n title =\t {Nearly optimal robust secret sharing},\n booktitle =\t {Proceedings of the {IEEE International Symposium on\n Information Theory (ISIT)}},\n year =\t 2016,\n pages =\t {2509--2513},\n doi =\t\t {10.1109/ISIT.2016.7541751},\n url_Link =\t {https://ieeexplore.ieee.org/document/7541751},\n keywords =\t {Coding and information theory, Cryptography,\n Algebraic coding theory},\n abstract =\t {We prove that a known approach to improve Shamir's\n celebrated secret sharing scheme; i.e., adding an\n information-theoretic authentication tag to the\n secret, can make it robust for $n$ parties against\n any collusion of size $\\delta n$, for any constant\n $\\delta \\in (0, 1/2)$. This result holds in the\n so-called ``non-rushing'' model in which the $n$\n shares are submitted simultaneously for\n reconstruction. We thus obtain a fully explicit and\n robust secret sharing scheme in this model that is\n essentially optimal in all parameters including the\n share size which is $k(1+o(1)) + O(\\kappa)$, where\n $k$ is the secret length and $\\kappa$ is the\n security parameter. Like Shamir's scheme, in this\n modified scheme any set of more than $\\delta n$\n honest parties can efficiently recover the secret.\n Using algebraic geometry codes instead of\n Reed-Solomon codes, the share length can be\n decreased to a constant (only depending on $\\delta$)\n while the number of shares $n$ can grow\n independently. In this case, when $n$ is large\n enough, the scheme satisfies the ``threshold''\n requirement in an approximate sense; i.e., any set\n of $\\delta n(1+\\rho)$ honest parties, for\n arbitrarily small $\\rho > 0$, can efficiently\n reconstruct the secret.},\n note =\t {Extended version in {Designs, Codes and\n Cryptography.}},\n url_Paper =\t {https://eprint.iacr.org/2015/951}\n}\n\n","author_short":["Cheraghchi, M."],"key":"ref:conf:Che16:SS","id":"ref:conf:Che16:SS","bibbaseid":"cheraghchi-nearlyoptimalrobustsecretsharing-2016","role":"author","urls":{" link":"https://ieeexplore.ieee.org/document/7541751"," paper":"https://eprint.iacr.org/2015/951"},"keyword":["Coding and information theory","Cryptography","Algebraic coding theory"],"metadata":{"authorlinks":{"cheraghchi, m":"https://mahdi.ch/"}}},"bibtype":"inproceedings","biburl":"http://mahdi.ch/writings/cheraghchi.bib","creationDate":"2020-05-28T23:00:52.248Z","downloads":2,"keywords":["coding and information theory","cryptography","algebraic coding theory"],"search_terms":["nearly","optimal","robust","secret","sharing","cheraghchi"],"title":"Nearly optimal robust secret sharing","year":2016,"dataSources":["YZqdBBx6FeYmvQE6D"]}