Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Unconditionally-Secure Robust Secret Sharing with Compact Shares
 
conference paper

Unconditionally-Secure Robust Secret Sharing with Compact Shares

Cevallos, Alfonso  
•
Fehr, Serge
•
Ostrovsky, Rafail
Show more
2012
Lecture Notes in Computer Science
Advances in Cryptology - EUROCRYPT 2012 - 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques

We 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.

  • Details
  • Metrics
Type
conference paper
DOI
10.1007/978-3-642-29011-4_13
Author(s)
Cevallos, Alfonso  
Fehr, Serge
Ostrovsky, Rafail
Rabani, Yuval
Date Issued

2012

Publisher

Springer-Verlag

Published in
Lecture Notes in Computer Science
Volume

7237

Start page

195

End page

208

Editorial or Peer reviewed

REVIEWED

Written at

OTHER

EPFL units
MATHAA  
Event nameEvent placeEvent date
Advances in Cryptology - EUROCRYPT 2012 - 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques

Cambridge, UK

April 15-19, 2012

Available on Infoscience
October 9, 2012
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/86033
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés