Abstract: |
We propose the first batch-verifiable secret sharing scheme with a significant security property, namely that of unconditional privacy. Verifiability and privacy of secret-shared messages are a crucial feature, e.g., in distributed computing scenarios, and verifiable secret sharing schemes with unconditional privacy (but without a batching feature) exist for a long time, e.g., Ben-Or, Goldwasser, and Wigderson (STOC 1988). Unfortunately, those schemes are able to verify only a single message at a time which, however, is not a very realistic scenario in a more practical setting. Namely, large files in real-world implementations are often split into many message blocks on a several-byte level and, thus, many known single-message verifiable secret sharing schemes tend to behave inefficiently in such a scenario. To improve practicability, batch-verifiable secret sharing was proposed by Bellare, Garay, and Rabin (ACM PODC 1996). In their scheme, the servers are able to verify a batch of messages (instead of only one) at almost the same amortized efficiency costs in comparison to efficient existing verifiable secret sharing schemes that only deal with single messages. However, the Bellare-Garay-Rabin scheme does not consider the important security property of unconditional privacy. Unconditionally private schemes information-theoretically guarantee privacy even against computationally unbounded adversaries and, hence, can be seen to be private in a long-term sense. In this work, we lift the Bellare-Garay-Rabin scheme to the unconditional privacy setting in a rigorous manner while preserving the practicability of their scheme simultaneously. |