Search

In this paper, we show a “direct” equivalence between certain authentication codes and robust threshold schemes. It was previously known that authentication codes and robust threshold schemes are closely related to similar types of designs, but direct equivalences had not been considered in the literature. Our new equivalences motivate the consideration of a certain “key-substitution attack.” We study this attack and analyze it in the setting of “dual authentication codes.” We also show how this viewpoint provides a nice way to prove properties and generalizations of some known constructions.

There has been considerable recent interest in “cloud storage” wherein a user asks a server to store a large file. One issue is whether the user can verify that the server is actually storing the file, and typically a challenge-response protocol is employed to convince the user that the file is indeed being stored correctly. The security of these schemes is phrased in terms of an extractor which will recover the file given any “proving algorithm” that has a sufficiently high success probability. This forms the basis of proof-of-retrievability (PoR) systems. In this paper, we study multiple server PoR systems. We formalize security definitions for two possible scenarios: (i) A threshold of servers succeeds with high enough probability (worst case), and (ii) the average of the success probability of all the servers is above a threshold (average case). We also motivate the study of confidentiality of the outsourced message. We give MPoR schemes which are secure under both these security definitions and provide reasonable confidentiality guarantees even when there is no restriction on the computational power of the servers. We also show how classical statistical techniques previously used by us can be extended to evaluate whether the responses of the provers are accurate enough to permit successful extraction. We also look at one specific instantiation of our construction when instantiated with the unconditionally secure version of the Shacham–Waters scheme. This scheme gives reasonable security and privacy guarantee. We show that, in the multi-server setting with computationally unbounded provers, one can overcome the limitation that the verifier needs to store as much secret information as the provers.

Abstract: A secret sharing scheme is a cryptographic protocol by means of which a dealer shares a secret among a set of participants in such a way that it can be subsequently reconstructed by certain qualified subsets. The setting we consider is the following: in a first phase, the dealer gives in a secure way a piece of information, called a share, to each participant. Then, participants belonging to a qualified subset send in a secure way their shares to a trusted party, referred to as a combiner, who computes the secret and sends it back to the participants. Cheating-immune secret sharing schemes are secret sharing schemes in the above setting where dishonest participants, during the reconstruction phase, have no advantage in sending incorrect shares to the combiner (i.e., cheating) as compared to honest participants. More precisely, a coalition of dishonest participants, by using their correct shares and the incorrect secret supplied by the combiner, have no better chance in determining the true secret (that would have been reconstructed if they submitted correct shares) than an honest participant. In this paper we study properties and constraints of cheating-immune secret sharing schemes. We show that a perfect secret sharing scheme cannot be cheating-immune. Then, we prove an upper bound on the number of cheaters tolerated in such schemes. We also repair a previously proposed construction to realize cheating-immune secret sharing schemes. Finally, we discuss some open problems. [Copyright &y& Elsevier]