Lattice-Based Threshold Changeability for Standard
Ron Steinfeld, Josef Pieprzyk, Huaxiong Wang
We consider the problem of increasing the threshold parameter of a secret-sharing scheme after the setup (share distri- bution) phase, without further communication between the dealer and the shareholders. Previous solutions to this problem require one to start off with a nonstandard scheme designed specifically for this purpose, or to have communication between shareholders. In contrast, we show how to increase the threshold parameter of the standard Shamir secret-sharing scheme without communica- tion between the shareholders. Our technique can thus be applied to existing Shamir schemes even if they were set up without con- sideration to future threshold increases. Our method is a new positive cryptographic application for lat- tice reduction algorithms, inspired by recent work on lattice-based list decoding of Reed-Solomon codes with noise bounded in the Lee norm. We use fundamental results from the theory of lattices (geometry of numbers) to prove quantitative statements about the information-theoretic security of our construction. These lattice- based security proof techniques may be of independent interest.
•Jan 1, 2007•1 citation