Stefan Dziembowski and Krzysztof
Pietrzak
Intrusion-Resilient Secret Sharing
accepted to FOCS 2007
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 $M$ 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 can choose some player to corrupt and some function, and he 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 by infected by malicious software like viruses, who can compute any function on the infected machine, but cannot send out (undetected) 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 send 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. For the latter we need BSM-secure functions (which are basically locally computable extractors) with the additional property of being permutations. We give a generic construction (a two-round Feistel network) which turns any BSM-secure function into a permutation (in fact, this construction works for any kind of extractor).
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.
Available files: [PS (draft)]
Intrusion-Resilient Secret Sharing
accepted to FOCS 2007
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 $M$ 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 can choose some player to corrupt and some function, and he 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 by infected by malicious software like viruses, who can compute any function on the infected machine, but cannot send out (undetected) 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 send 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. For the latter we need BSM-secure functions (which are basically locally computable extractors) with the additional property of being permutations. We give a generic construction (a two-round Feistel network) which turns any BSM-secure function into a permutation (in fact, this construction works for any kind of extractor).
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.
Available files: [PS (draft)]