Paper 2007/359

Intrusion-Resilient Secret Sharing

Stefan Dziembowski and Krzysztof Pietrzak

Abstract

We introduce a new primitive called Intrusion-Resilient Secret Sharing (IRSS), whose security proof exploits the fact that there exist functions which can be efficiently computed interactively using low communication complexity in k, but not in k - 1 rounds. IRSS is a means of sharing a secret message amongst a set of players which comes with a very strong security guarantee. The shares in an IRSS are made artificially large so that it is hard to retrieve them completely, and the reconstruction procedure is interactive requiring the players to exchange k short messages. The adversaries considered can attack the scheme in rounds, where in each round the adversary chooses some player to corrupt and some function, and retrieves the output of that function applied to the share of the corrupted player. This model captures for example computers connected to a network which can occasionally be infected by malicious software like viruses, which can compute any function on the infected machine, but cannot sent out a huge amount of data. Using methods from the Bounded-Retrieval Model, we construct an IRSS scheme which is secure against any computationally unbounded adversary as long as the total amount of information retrieved by the adversary is somewhat less than the length of the shares, and the adversary makes at most k - 1 corruption rounds (as described above, where k rounds are necessary for reconstruction). We extend our basic scheme in several ways in order to allow the shares sent by the dealer to be short (the players then blow them up locally) and to handle even stronger adversaries who can learn some of the shares completely. As mentioned, there is an obvious connection between IRSS schemes and the fact that there exist functions with an exponential gap in their communication complexity for k and k - 1 rounds. Our scheme implies such a separation which is in several aspects stronger than the previously known ones.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. extended version of a paper appearing at FOCS 2007
Contact author(s)
stefan @ dziembowski net
History
2007-09-13: revised
2007-09-13: received
See all versions
Short URL
https://ia.cr/2007/359
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2007/359,
      author = {Stefan Dziembowski and Krzysztof Pietrzak},
      title = {Intrusion-Resilient Secret Sharing},
      howpublished = {Cryptology ePrint Archive, Paper 2007/359},
      year = {2007},
      note = {\url{https://eprint.iacr.org/2007/359}},
      url = {https://eprint.iacr.org/2007/359}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.