000181702 001__ 181702
000181702 005__ 20180913061553.0
000181702 0247_ $$2doi$$a10.1007/978-3-642-29011-4_13
000181702 022__ $$a0302-9743
000181702 037__ $$aCONF
000181702 245__ $$aUnconditionally-Secure Robust Secret Sharing with Compact Shares
000181702 260__ $$bSpringer-Verlag$$c2012
000181702 269__ $$a2012
000181702 336__ $$aConference Papers
000181702 520__ $$aWe consider the problem of reconstructing a shared secret in the presence of faulty shares, with unconditional security. We require that any t shares give no information on the shared secret, and reconstruction is possible even if up to t out of the n shares are incorrect. The interesting setting is n/3 <= t < n/2, where reconstruction of a shared secret in the presence of faulty shares is possible, but only with an increase in the share size, and only if one admits a small failure probability. The goal of this work is to minimize this overhead in the share size. Known schemes either have a Omega(k n)-overhead in share size, where k is the security parameter, or they have a close-to-optimal overhead of order O(k + n) but have an exponential running time (in n). In this paper, we propose a new scheme that has a close-to-optimal overhead in the share size of order O(k + n log(n)), and a polynomial running time. Interestingly, the shares in our new scheme are prepared in the very same way as in the well-known scheme by Rabin and Ben-Or, which relies on message authentication, but we use a message authentication code with short tags and keys and with correspondingly weak security. The short tags and keys give us the required saving in the share size. Surprisingly, we can compensate for the weakened security of the authentication and achieve an exponentially small (in k) failure probability by means of a more sophisticated reconstruction procedure.
000181702 700__ $$0246643$$aCevallos, Alfonso$$g222377
000181702 700__ $$aFehr, Serge
000181702 700__ $$aOstrovsky, Rafail
000181702 700__ $$aRabani, Yuval
000181702 7112_ $$aAdvances in Cryptology - EUROCRYPT 2012 - 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques$$cCambridge, UK$$dApril 15-19, 2012
000181702 773__ $$j7237$$q195-208$$tLecture Notes in Computer Science
000181702 909C0 $$0252437$$pMATHAA$$xU10112
000181702 909CO $$ooai:infoscience.tind.io:181702$$pconf
000181702 917Z8 $$x222377
000181702 917Z8 $$x148230
000181702 937__ $$aEPFL-CONF-181702
000181702 973__ $$aOTHER$$rREVIEWED$$sPUBLISHED
000181702 980__ $$aCONF