Discussions on Unconditionally Secure VSS Robust against Dishonest Majority

概要

論文の詳細を見る
In this paper, we introduce an unconditionally secure verifiable secret sharing scheme that works even if majority of the players are dishonest. We mean by unconditionally secure that the security of the scheme does not depend on any unproven assumptions such as computational ones. We assume that each player including a dealer has a pre-distributed private key, so that each player can verify any share using his or her private key non-interactively and independently from the other players. Therefore, in the reconstruction phase, even if majority of the players are dishonest but at least t players give correct shares, then the secret can be correctly reconstructed, where t is threshold of the underlying secret sharing scheme. Such a pre-distributed private key can be formed if we have Rivest's trusted initializer or if we can execute interactive multi-party computation at some point of time when more than 2/3 of the players can be trusted (or 1/2 if broadcast channel is available). We achieved a VSS scheme with pre-distributed private keys such that privacy of secret is unconditionally hidden from an adversary with unbound computing power with less than t colluders. Simultaneously, even majority of players are dishonest and with unbounded computing power, if there are more than t honest players, then they can reconstruct a consistent secret.
社団法人電子情報通信学会の論文
2002-07-12