In this paper we consider evolving 2-threshold secret sharing schemes. In such schemes, the number of participants grows over time and is potentially unbounded, any two participants reconstruct the secret, and no single participant can figure out any partial information about it. They are referred to as$(2,\infty)$-threshold secret sharing schemes. The cost of a$(2,\infty)$-threshold secret sharing scheme can be measured as the maximum, over all possible$n\ge 2$, of the ratio between the sum of the lengths of the shares for the first n participants and the sum of the lengths of the shares for a (standard) optimal$(2,n)$-threshold secret sharing scheme. It is known that such a cost measure is lower bounded by$3/2$. Moreover, currently, the best known$(2,\infty)$-threshold secret sharing scheme has cost 1.59375. Our contribution improves the state-of-the-art in several ways:•We describe a new$(2,\infty)$-threshold secret sharing scheme whose cost is 1.5859375, improving on the previous best known scheme. • Motivated by the fact that in some applications one knows a lower bound on the number of participants, we generalize the cost measure, by considering the maximum over all possible$n\ge z_{0}$, where$z_{0}$is any integer greater than or equal to 2. • We provide constructions of optimal schemes for the generalized cost measure and through a theoretical analysis we prove some interesting properties for the lower bound of the cost. • By using algorithmic techniques, for reasonably small cases, we exhaustively study the problem of finding tight lower bounds. In particular, we obtain a lower bound of 1.534375, improving the lower bound of$3/2$. We close the paper summarizing our findings and discussing some open issues.

In classical secret sharing schemes a dealer shares a secret among a set of participants in such a way that qualified subsets can reconstruct the secret, while forbidden ones do not get any kind of information about it. The basic parameter to optimize is the size of the shares, that is, the amount of secret information that the dealer has to give to participants. In this paper we formalize a notion of probabilistic secret sharing schemes, in which qualified subsets can reconstruct the secret but only with a certain controlled probability. We show that, by allowing a bounded error in the reconstruction of the secret, it is possible to drastically reduce the size of the shares the participants get (with respect to classical secret sharing schemes). We provide efficient constructions both for threshold access structures on a finite set of participants and for evolving threshold access structures, where the set of participants is potentially infinite. Some of our constructions yield shares of constant size (i.e., not depending on the number of participants) and an error probability of successfully reconstructing the secret which can be made as close to 1 as desired.

The growing need for user privacy protection has lead to the development of general notions and efficient tools for building privacy-preserving applications. Among them, the notion of key privacy in public-key encryption, which guarantees that an adversary is unable to tell with which public key a certain ciphertext has been produced, plays a key-role in the design of several anonymous protocols. Apparently, it seems to be unrelated to the security of the encrypted content, and it looks like just an additional property the encryption scheme can enjoy. In this paper we show that for a robust encryption scheme key privacy under chosen ciphertext attack implies non-malleability and, hence, security under chosen ciphertext attacks. Then, we look at two privacy-preserving protocols: secret sets and anonymous broadcast encryption. We prove that secret sets and anonymous broadcast are equivalent w.r.t. non-adaptive adversaries: the first can be used to design the second and vice versa. Finally, we revisit some previous constructions for secret sets, and we show the security properties they enjoy within a rigorously defined adversarial model.

A recent research trend, motivated by the massive deployment of RFID technology, looks at cryptographic protocols for securing communication between entities in which some of the parties have very limited computing capabilities. In this paper, we focus our attention on SASI, a new RFID authentication protocol, designed for providing Strong Authentication and Strong Integrity. SASI is a good representative of a family of RFID authentication protocols, referred to as Ultralightweight RFID authentication protocols. These protocols, suitable for passive Tags with limited computational power and storage, involve simple bitwise operations such as and, or, exclusive or, modular addition, and cyclic shift operations. They are efficient, fit the hardware constraints, and can be seen as an example of the above research trend. However, the main concern is the real security of these protocols, which are often supported only by apparently reasonable and intuitive arguments. The contribution we provide with this work is the following: we start by showing some weaknesses in the SASI protocol, and then, we describe how such weaknesses, through a sequence of simple steps, can be used to compute in an efficient way all secret data used for the authentication process. Specifically, we describe three attacks: 1) a desynchronization attack, through which an adversary can break the synchronization between the RFID Reader and the Tag; 2) an identity disclosure attack, through which an adversary can compute the identity of the Tag; and 3) a full disclosure attack, which enables an adversary to retrieve all secret data stored in the Tag. Then, we present some experimental results, obtained by running several tests on an implementation of the protocol, in order to evaluate the performance of the proposed attacks, which confirm that the attacks are effective and efficient. It comes out that an active adversary by interacting with a Tag more or less three hundred times, makes the authentication protocol completely useless. Finally, we close the paper with some observations. The cryptoanalysis of SASI gets some new light on the ultralightweight approach, and can also serve as a warning to researchers working on the field and tempted to apply these techniques. Indeed, the results of this work, rise serious questions regarding the limits of the ultralightweight family of protocols, and on the benefits of these ad hoc protocol design strategies and informal security analysis.

A key distribution scheme is a method by means of which a trusted party distributes pieces of information among a set of users in such a way that each group of them can compute a common key for secure communication. In this paper we present a model for unconditionally secure key distribution schemes, i.e., schemes whose security is independent of the power of the adversary. We prove lower bounds on the amount of information the trusted party has to generate and each user has to keep secret in such schemes, and we show that some previous unconditionally secure models for key distribution fall in our model. As a consequence, the lower bounds given in the literature for these models can be seen as corollaries of our results. Hence, the main contribution of the paper consists in pointing out a sort of common structure underlying some apparently different key distribution techniques.

This paper deals with the access control problem. We assume that valuable resources need to be protected against unauthorized users and that, to this aim, a password-based access control scheme is employed. Such an abstract scenario captures many applicative settings. The issue we focus our attention on is the following: password-based schemes provide a certain level of security as long as users choose good passwords, i.e., passwords that are hard to guess in a reasonable amount of time. In order to force the users to make good choices, a proactive password checker can be implemented as a submodule of the access control scheme. Such a checker, any time the user chooses/changes his own password, decides on the fly whether to accept or refuse the new password, depending on its guessability. Hence, the question is: how can we get an effective and efficient proactive password checker? By means of neural networks and statistical techniques, we answer the above question, developing suitable proactive password checkers. Through a series of experiments, we show that these checkers have very good performance: error rates are comparable to those of the best existing checkers, implemented on different principles and by using other methodologies, and the memory requirements are better in several cases. It is the first time that neural network technology has been fully and successfully applied to designing proactive password checkers

Self-healing key distribution schemes allow group managers to broadcast session keys to large and dynamic groups of users over unreliable channels. Roughly speaking, even if during a certain session some broadcast messages are lost due to network faults, the self-healing property of the scheme enables each group member to recover the key from the broadcast messages he has received before and after that session. Such schemes are quite suitable in supporting secure communication in wireless networks and mobile wireless ad-hoc networks. Recent papers have focused on self-healing key distribution, and have provided definitions, stated in terms of the entropy function, and some constructions. The contribution of this paper is the following: We analyze current definitions of self-healing key distribution and, for two of them, we show that no protocol can achieve the definition. We show that a lower bound on the size of the broadcast message, previously derived, does not hold. We propose a new definition of self-healing key distribution, and we show that it can be achieved by concrete schemes. We give some lower bounds on the resources required for implementing such schemes, i.e., user memory storage and communication complexity. We prove that the bounds are tight

A self-healing key distribution scheme enables a group of users to establish a group key over an unreliable channel. In such a protocol, a group manager, to distribute a session key to each member of the group, broadcasts packets along the channel. If some packet gets lost, the users are still capable of recovering the group key using the received packets, without requesting additional transmission from the group manager. A user must be member both before and after the session in which a particular key is sent and lost, in order to be recovered through "self-healing". In this paper we propose a new technique to do self-healing, and we provide a secure and efficient scheme.

A self-healing key distribution scheme enables a dynamic group of users to establish a group key over an unreliable channel. In such a scheme, a group manager, to distribute a session key to each member of the group, broadcasts packets along the channel. If some packets get lost, users are still capable of recovering the group key using the received packets, without requesting additional transmission from the group manager. A user must be member both before and after the session in which a particular key is sent in order to recover the key through "self-healing". This novel and appealing approach to key distribution is quite suitable in military applications and in several Internet-related settings, where high security requirements should be satisfied. We show a ciphertext-only attack that applies to a proposed scheme.

A (k,n)-threshold visual cryptography scheme (VCS) is a method to encode a secret image SI into n shadow images called shares such that any k or more shares enable the "visual" recovery of the secret image. However, by inspecting less than k shares one cannot gain any information on the secret image. The "visual" recovery consists of copying the shares onto transparencies and then stacking them. Any k shares will reveal the secret image without any cryptographic computation. In this paper we analyze the contrast of the reconstructed image for a (k,n)-threshold VCS. We define a canonical form for a (k,n)-threshold VCS and provide a characterization of a (k,,n)-threshold VCS. We completely characterize a contrast optimal (n-1,n)-threshold VCS in canonical form. Moreover, for $n\geq 4$, we provide a contrast optimal (3,n)-threshold VCS in canonical form. We first describe a family of (3,n)-threshold VCS achieving various values of contrast and pixel expansion. Then we prove an upper bound on the contrast of any (3,n)-threshold VCS and show that a scheme in the described family has optimal contrast. Finally, for k=4,5 we present two schemes with contrast asymptotically equal to 1/64 and 1/256, respectively.

A one-restricted key agreement scheme is a method by which initially a trusted authority distributes private individual pieces of information to a set of users. Later, each member of any group of users of a given size, referred to as a conference, can compute a common key by exchanging messages over a broadcast channel all users have access to. Such schemes can be used to establish only one common key. In this paper we analyse τ-restricted key agreement schemes. Such schemes allow the computation of up to rτ common keys for τ distinct conferences. For certain values of the parameters the scheme that we propose distributes less information than the trivial one obtained by considering τ copies of a one-restricted scheme.