Research Abstracts - 2007

Introduction

We are interested in the problem of creating a system that keeps a secret in the presence of Byzantine failures and malicious attacks. Additionally we are interested in long-lived systems, so that preservation of the secret must continue indefinitely. An example of a secret is the private key used by a key distribution system to sign its certificates. We would want such a system to have the potential to run forever, without a concern that the private key will be compromised.

Such a secret can be preserved by secret sharing [1,5] which allows a collection of parties to possess shares of a secret value. 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,4] 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.

The notion of "recovery" is problematic, however. 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 the membership of the group to change. 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, care is needed when transferring a secret to a new group of shareholders, since each group might have up to t faulty nodes and a naïve transfer of shares from an old group of servers to a new group may reveal the secret.

Furthermore, existing 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 have developed Mobile Proactive Secret Sharing (MPSS), a new PSS scheme that addresses all these problem. 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. A further important point is that MPSS works in an asynchronous network setting such as the Internet.

Our scheme is based on Herzberg et al. [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, that scheme did not work in an asynchronous setting. Furthermore, to ensure that members of the old group do not learn anything about the new share polynomial P + Q, we had to augment the scheme with additional polynomials to ensure that only members of the new group can learn points on P + Q. MPSS 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. Our protocol also supports 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 allow the threshold to change. Many prior works on PSS have not addressed the issue of changing the group [2,3], and the ones that have addressed the issue [6,7] tend to have a worst-case communication complexity that is exponential in the number of shareholders. Our scheme is the first to show how to transfer the secret to a new group in polynomial time.

Additionally, we have developed an efficient implementation of our scheme. Our approach uses a coordinator to direct the resharing, with a protocol to change the coordinator if it misbehaves. The approach results in better performance than other PSS schemes in the optimistic case where the coordinator is honest, while preserving correctness and termination in other cases.

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

References:

[1] G. R. Blakley. Safeguarding cryptographic keys. In Proc. AFIPS 1979, volume 48, pages 313-317, June 1979.

[2] 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.

[3] 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.

[4] 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.

[5] A. Shamir. How to share a secret. Communications of the ACM, 22:612-613, 1979.

[6] 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.

[7] L. Zhou, F. Schneider, and R. van Renesse. APSS: Proactive secret sharing in asynchronous systems. ACM Transations on Information and System Security, 8(3):259-286, Aug 2005.