International Association
for Cryptologic Research

In this paper we consider the problem of secret sharing where shares

are encrypted using a public-key encryption (PKE) scheme and

ciphertexts are publicly available. While intuition tells us that the

secret should be protected if the PKE is secure against

chosen-ciphertext attacks (i.e., CCA-secure), formally proving this

reveals some subtle and non-trivial challenges. We isolate the

problems that this raises, and devise a new analysis technique called

``plaintext randomization\'\' that can successfully overcome these

challenges, resulting in the desired proof. The encryption of

different shares can use one key or multiple keys, with natural

applications in both scenarios.