Research Abstracts - 2006

Mobile Proactive Secret Sharing

David Schultz, Barbara Liskov & Moses Liskov

Introduction

Secret sharing allows a collection of parties to possess shares of a secret value (such as a secret key), such that any t + 1 shares can be used to reconstruct the secret, yet any t shares provide no information about the secret. However, in long-lived systems, servers can be compromised over time, giving an adversary the opportunity to collect more than t shares and recover the secret. Proactive secret sharing (PSS) schemes [2,3] attempt to address this problem by using a share regeneration protocol, in which a new set of shares of the same secret is generated and the old shares discarded, rendering useless any collection of t or fewer shares the adversary may have learned. PSS imagines a world in which servers are "recovered" at a rate equal to that at which they are compromised. However, there are several significant flaws in this model.

First, "recovery" is problematic. Merely restarting a compromised node is insufficient, because the attacker could have learned the node's secret information (such as its encryption key, for instance). But discarding a node's secret information is also problematic because if the node is honest, this effectively causes it to fail, which could cause the group to exceed its failure threshold and thus make it impossible for the group to reshare the secret.

A better approach is to allow shareholders to be replaced with different nodes. This provides a reasonable methodology for a system administrator: identify a set of "fresh" nodes, e.g., recently added nodes or newly recovered nodes with new keys, and direct the secret shares to be moved to them. However, PSS schemes do not permit the replacement of one shareholder with another. Furthermore, a difficulty in defining such schemes is that a naïve transfer of shares from an old group of servers to a new group may reveal the secret if more than t faulty servers exist between the old group and the new group.

Furthermore, PSS schemes do not allow the threshold t to change, which may be desirable in a long-lived system. The threshold has a meaning: it represents an assumption about how easily nodes can become corrupted. If current events dictate a reevaluation of this assumption, it would be better to change to a new threshold rather than start over. For instance, a new vulnerability in Windows might lead to a decision to increase t, whereas the patch of that vulnerability might later lead to it being decreased.

Approach

We introduce the concept of mobile proactive secret sharing (MPSS), a generalization of PSS that addresses all these problems. In MPSS, as in other proactive secret sharing schemes, servers execute a periodic share refreshment protocol. However, MPSS allows the shares to be transferred to a new group of share holders, which may be larger or smaller than the old group, without revealing any extra information to corrupted nodes. Hence, proactive secret sharing can be thought of as a special case of MPSS where the old and new groups are restricted to be identical. We give an efficient and practical protocol for MPSS in the asynchronous network setting.

Our scheme is based on [2] in that new shares are formed by taking an existing Shamir share polynomial $P$ and adding to it another polynomial Q such that Q(0) = 0. However, care must be taken to ensure that members of the old group do not learn anything about the new share polynomial P + Q, so we must augment this scheme with additional polynomials to ensure that only members of the new group can learn points on P + Q. Our scheme uses Feldman commitments and Byzantine agreement to generate these polynomials in the old group such that each node learns only the points intended for it. All nodes can verify that they have received points on the same polynomials, and that those polynomials satisfy the appropriate correctness conditions. Hence, Byzantine-faulty nodes are unable to cheat. We extend this protocol to support increasing and decreasing the number of shareholders.

To be useful in real systems, a proactive secret sharing scheme must operate in an asynchronous network, allow the set of shareholders to change between resharings to permit replacement of bad nodes, and ideally, allow the size of this set to change. MPSS is the first protocol to achieve all of these goals. Earlier schemes operated only in synchronous networks [2], did not support changing the set of shareholders [2,1], or had overhead that was exponential in the number of shareholders [4]. Moreover, we discuss how to implement the protocol efficiently by using a coordinator, resulting in much better performance than other PSS schemes in the optimistic case where the coordinator is honest, while preserving correctness and termination in other cases.

Research Support

This research is supported by NSF ITR-6896772 and Quanta, Inc.

References:

[1] C. Cachin, K. Kursawe, A. Lysyanskaya, and R. Strobl. Asynchronous verifiable secret sharing and proactive cryptosystems. In Proc. 9th (ACM) conference on Computer and Communications Security, pages 88-97. (ACM) Press, 2002.

[2] A. Herzberg, S. Jarecki, H. Krawczyk, and M. Yung. Proactive secret sharing, or how to cope with perpetual leakage. In D. Coppersmith, editor, Advances in Cryptology--CRYPTO '95, volume 963 of Lecture Notes in Computer Science, pages 457-469. Springer-Verlag, 27-31 Aug. 1995.

[3] R. Ostrovsky and M. Yung. How to withstand mobile virus attacks. In Proceedings of the 10th (ACM) Symposium on the Principles of Distributed Computing, pages 51-61, 1991.

[4] T. M. Wong, C. Wang, and J. Wing. Verifiable secret redistribution for archive systems. In Proceedings of the 1st International IEEE Security in Storage Workshop, 2002.