ON DYNAMIC THRESHOLD SCHEMES

An (m, n) threshold scheme is to decompose the master key K into n sec ret shadows in such a way that the master key K cannot be reclaimed un less any m shadows are collected. However, any m-1 or fewer shadows pr ovide absolutely no information about K. In 1989, Laih et al. proposed the concept of dynamic threshold schemes which allow the master key t o be updated without changing the secret shadows. However, the perfect dynamic threshold scheme, which provides perfect secrecy though the m aster key is allowed to be changed, has not been proposed. Nor has any paper shown the existence of perfect dynamic threshold schemes. In th is paper, we prove that perfect dynamic threshold schemes do not exist when their master keys need be updated [log(2)\L\log(2)\K\] times or more without changing the secret shadows, where L is the secret shadow space and K is the master key space. Furthermore, we propose an perfe ct dynamic threshold scheme which allows its master key to be updated once without changing the secret shadows.