Alfredo De Santis

TCS Journal 2021 Journal Article

Secret sharing schemes for infinite sets of participants: A new design technique

• Paolo D'Arco
• Roberto De Prisco
• Alfredo De Santis

We propose a new design technique for constructing secret sharing schemes over a potentially infinite set of participants. Our findings leverage on a nice property of secret sharing schemes for finite sets of participants based on the Chinese remainder theorem: the possibility of providing shares of different sizes to participants. We successful apply the technique to the ( 3, ∞ ) -threshold access structure. The scheme we exhibit improves over the best construction currently available. Most importantly, the idea underlying the technique is of independent interest. Hopefully, it could be employed for other access structures, and in other areas of secure computation for potentially infinite sets of players.

MFCS Conference 2018 Conference Paper

Probabilistic Secret Sharing

• Paolo D'Arco
• Roberto De Prisco
• Alfredo De Santis
• Angel L. Pérez del Pozo
• Ugo Vaccaro

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.

TCS Journal 2015 Journal Article

Anonymous protocols: Notions and equivalence

• Paolo D'Arco
• Alfredo De Santis

Privacy protection has become a major issue in modern societies. Many efforts have been provided in the last years to catch properly the requirements that cryptographic primitives and low-level protocols should meet in order to be useful for building privacy-preserving applications. In particular, anonymity is an important property to achieve, and 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 anonymous protocols. Secret sets and anonymous broadcast encryption are two examples of useful anonymous protocols. A secret set is a representation of a subset of users of a given universe satisfying some basic membership privacy properties, and anonymous broadcast encryption is a mechanism to encrypt a broadcast message that only authorized users, whose identities are kept secret, can decrypt. In this paper we show that, even if apparently the key privacy property of an encryption scheme seems to be unrelated to the security of the encrypted content, and it looks like just an additional property the encryption scheme can enjoy, for a robust encryption scheme key privacy under chosen ciphertext attack implies non-malleability and, hence, security under chosen ciphertext attacks. This result helps to simplify the set of requirements that public key encryption schemes need to satisfy when stating and proving theorems regarding anonymous protocols in which the encryption schemes are used. Then, we provide a formal model for both secret sets and anonymous broadcast encryption and we prove that they are equivalent with respect to non-adaptive adversaries: the former can be used to design the latter and vice versa. Finally, we revisit some previous constructions for secret sets, and we analyze the security properties they enjoy within our adversarial model.

TCS Journal 2013 Journal Article

Color visual cryptography schemes for black and white secret images

• Roberto De Prisco
• Alfredo De Santis

In this paper we propose the use of colors to improve visual cryptography schemes for black-and-white secret images. The resulting model is called colored-black-and-white visual cryptography (cbw-vc) model. Using this new model we exploit colors to obtain schemes to share b&w images using a smaller pixel expansion. In particular we provide ( 2, n ) -threshold schemes with pixel expansion m = ⌈ log 3 n ⌉, improving on the best pixel expansion attainable in the normal b&w model (bw-vc). For the case of schemes with perfect reconstruction of black pixels we provide a general construction that allows us to transform any bw-vc scheme into a cbw-vc scheme whose pixel expansion is 1/3 of the pixel expansion of the starting bw-vc scheme. We prove that, in the cbw-vc model, it is not possible to construct ( 2, n ) -threshold schemes, for n ⩾ 4, and ( k, n ) -threshold schemes, for k ⩾ 3, without pixel expansion. We also prove that there exist schemes with optimal contrast in the subset of schemes that use only full intensity colors; this is a direct consequence of the definition of contrast which distinguishes only black and non-black pixels. We discuss an alternative measure of contrast that takes into account the “distance” between colors. We conjecture that also with this definition of contrast there exist schemes that use only full intensity colors and achieve optimal contrast.

TCS Journal 2011 Journal Article

Efficient provably-secure hierarchical key assignment schemes

• Alfredo De Santis
• Anna Lisa Ferrara
• Barbara Masucci

A hierarchical key assignment scheme is a method to assign some private information and encryption keys to a set of classes in a partially ordered hierarchy, in such a way that the private information of a higher class can be used to derive the keys of all classes lower down in the hierarchy. In this paper we design and analyze hierarchical key assignment schemes which are provably secure and support dynamic updates to the hierarchy with local changes to the public information and without requiring any private information to be re-distributed. – We first consider the problem of constructing a hierarchical key assignment scheme by using as a building block a symmetric encryption scheme. We propose a new construction which is provably secure with respect to key indistinguishability, requires a single computational assumption, and improves on previous proposals. – Then, we show how to construct a hierarchical key assignment scheme by using as a building block a public-key broadcast encryption scheme. In particular, one of our constructions provides constant private information and public information linear in the number of classes in the hierarchy.

TCS Journal 2010 Journal Article

Variations on a theme by Akl and Taylor: Security and tradeoffs

• Paolo D’Arco
• Alfredo De Santis
• Anna Lisa Ferrara
• Barbara Masucci

In 1983, Akl and Taylor [Cryptographic solution to a problem of access control in a hierarchy, ACM Transactions on Computer Systems 1 (3) (1983) 239–248] first suggested the use of cryptographic techniques to enforce access control in hierarchical structures. Due to its simplicity and versatility, the scheme has been used, for more than twenty years, to implement access control in several different domains, including mobile agent environments and XML documents. However, despite its use over time, the scheme has never been fully analyzed with respect to security and efficiency requirements. In this paper we provide new results on the Akl–Taylor scheme and its variants. More precisely: • We provide a rigorous analysis of the Akl–Taylor scheme. We consider different key assignment strategies and prove that the corresponding schemes are secure against key recovery. • We show how to obtain different tradeoffs between the amount of public information and the number of steps required to perform key derivation in the proposed schemes. • We also look at the MacKinnon et al. and Harn and Lin schemes and prove they are secure against key recovery. • We describe an Akl–Taylor based key assignment scheme with time-dependent constraints and prove the scheme efficient, flexible and secure. • We propose a general construction, which is of independent interest, yielding a key assignment scheme offering security w. r. t. key indistinguishability, given any key assignment scheme which guarantees security against key recovery. • Finally, we show how to use our construction, along with our assignment strategies and tradeoffs, to obtain an Akl–Taylor scheme, secure w. r. t. key indistinguishability, requiring a constant amount of public information.

MFCS Conference 2009 Conference Paper

Security and Tradeoffs of the Akl-Taylor Scheme and Its Variants

• Paolo D'Arco
• Alfredo De Santis
• Anna Lisa Ferrara
• Barbara Masucci

Abstract In 1983 Akl and Taylor [ Cryptographic Solution to a Problem of Access Control in a Hierarchy, ACM Transactions on Computer Systems, 1(3), 239–248, 1983] first suggested the use of cryptographic techniques to enforce access control in hierarchical structures. Over time, their scheme has been used in several different contexts, including mobile agents environments and broadcast encryption. However, it has never been fully analyzed from the security point of view. We provide a rigorous analysis of the Akl-Taylor scheme and prove that it is secure against key recovery. We also show how to obtain different tradeoffs between the amount of public information and the number of steps required to perform key derivation. Moreover, we propose a general construction to set up a key assignment scheme secure w. r. t. key indistinguishability, given any key assignment scheme secure against key recovery. Finally, we show how to use our construction, along with our tradeoffs, to obtain a variant of the Akl-Taylor scheme, secure w. r. t key indistinguishability, requiring a constant amount of public information.

TCS Journal 2008 Journal Article

New constructions for provably-secure time-bound hierarchical key assignment schemes

• Alfredo De Santis
• Anna Lisa Ferrara
• Barbara Masucci

A time-bound hierarchical key assignment scheme is a method to assign time-dependent encryption keys to a set of classes in a partially ordered hierarchy, in such a way that each class in the hierarchy can compute the keys of all classes lower down in the hierarchy, according to temporal constraints. In this paper we propose new constructions for time-bound hierarchical key assignment schemes which are provably secure with respect to key indistinguishability. Our constructions use as a building block any provably-secure hierarchical key assignment scheme without temporal constraints and exhibit a tradeoff among the amount of private information held by each class, the amount of public data, the complexity of key derivation, and the computational assumption on which their security is based. Moreover, the proposed schemes support updates to the access hierarchy with local changes to public information and without requiring any private information to be re-distributed.

MFCS Conference 2007 Conference Paper

Efficient Provably-Secure Hierarchical Key Assignment Schemes

• Alfredo De Santis
• Anna Lisa Ferrara
• Barbara Masucci

Abstract A hierarchical key assignment scheme is a method to assign some private information and encryption keys to a set of classes in a partially ordered hierarchy, in such a way that the private information of a higher class can be used to derive the keys of all classes lower down in the hierarchy. In this paper we design and analyze hierarchical key assignment schemes which are provably-secure and support dynamic updates to the hierarchy with local changes to the public information and without requiring any private information to be re-distributed. We first show an encryption based construction which is provably secure with respect to key indistinguishability, requires a single computational assumption and improves on previous proposals. Then, we show how to reduce key derivation time at the expense of an increment of the amount of public information, by improving a previous result. Finally, we show a construction using as a building block a public-key broadcast encryption scheme. In particular, one of our constructions provides constant private information and public information linear in the number of classes in the hierarchy.

TCS Journal 2006 Journal Article

Visual cryptography schemes with optimal pixel expansion

• Carlo Blundo
• Stelvio Cimato
• Alfredo De Santis

A visual cryptography scheme encodes a black and white secret image into n shadow images called shares which are distributed to the n participants. Such shares are such that only qualified subsets of participants can “visually” recover the secret image. Usually, the reconstructed image will be darker than the background of the image itself. In this paper we consider visual cryptography schemes satisfying the model introduced by Tzeng and Hu [A new approach for visual cryptography, Designs, Codes and Cryptography 27 (3) (2002) 207–227]. In such a model, the recovered secret image can be darker or lighter than the background. We prove a lower bound on the pixel expansion of the scheme and, for ( 2, n ) -threshold visual cryptography schemes, we provide schemes achieving the bound. Our schemes improve on the ones proposed by Tzeng and Hu.

MFCS Conference 2004 Conference Paper

On NC 1 Boolean Circuit Composition of Non-interactive Perfect Zero-Knowledge

• Alfredo De Santis
• Giovanni Di Crescenzo
• Giuseppe Persiano

Abstract Non-Interactive Perfect Zero-Knowledge (NIPZK) and Perfect Zero-Knowledge (PZK) are the class of languages having a Perfect Zero-Knowledge proof system in the non-interactive and interactive model, respectively. In this paper we present new techniques for Boolean Circuit Compositions of NIPZK and PZK, and significantly enlarge the class of known languages having such proofs. Our main result is that all NC 1 circuit compositions over a certain class of languages (that includes for example quadratic residuosity languages) have NIPZK proofs. Previous results only applied to single threshold gates and certain CNF formulae. We also extend the class of known languages in PZK by allowing compositions over random self-reducible languages with respect to polynomial-size monotone circuits with fan-out >1 and certain additional restrictions on the allowed gates. Previous results only applied to polynomial-size formulae (that is, circuits with fan-out =1).

TCS Journal 2004 Journal Article

Randomness in secret sharing and visual cryptography schemes

• Annalisa De Bonis
• Alfredo De Santis

Secret sharing schemes allow a secret to be shared among a group of participants so that only qualified subsets of participants can recover the secret. A visual cryptography scheme (VCS) is a special kind of secret sharing scheme in which the secret to share consists of an image and the shares consist of xeroxed transparencies which are stacked to recover the shared image. In this paper, we analyze the relationship between secret sharing schemes and VCSs, focusing our attention on the amount of randomness required to generate the shares. We prove that secret sharing schemes for a set of secrets of size two (BSSs) and VCSs are “equivalent” with respect to the randomness. Indeed, we show how to transform a BSS for a given access structure into a VCS for the same access structure while preserving the randomness of the original scheme. We provide both upper and lower bounds on the randomness of BSSs. All VCSs presented in this paper allow a perfect reconstruction of black pixels.

TCS Journal 2001 Journal Article

Extended capabilities for visual cryptography

• Giuseppe Ateniese
• Carlo Blundo
• Alfredo De Santis
• Douglas R. Stinson

An extended visual cryptography scheme (EVCS), for an access structure (Γ Qual, Γ Forb ) on a set of n participants, is a technique to encode n images in such a way that when we stack together the transparencies associated to participants in any set X∈Γ Qual we get the secret message with no trace of the original images, but any X∈Γ Forb has no information on the shared image. Moreover, after the original images are encoded they are still meaningful, that is, any user will recognize the image on his transparency. The main contributions of this paper are the following: • A trade-off between the contrast of the reconstructed image and the contrast of the image on each transparency for (k, k)-threshold EVCS (in a (k, k)-threshold EVCS the image is visible if and only if k transparencies are stacked together). This yields a necessary and sufficient condition for the existence of (k, k)-threshold EVCS for the values of such contrasts. In case a scheme exists we explicitly construct it. • A general technique to implement EVCS, which uses hypergraph colourings. This technique yields (k, k)-threshold EVCS which are optimal with respect to the pixel expansion. Finally, we discuss some applications of this technique to various interesting classes of access structures by using relevant results from the theory of hypergraph colourings.

TCS Journal 1996 Journal Article

Fully dynamic secret sharing schemes

• Carlo Blundo
• Antonella Cresti
• Alfredo De Santis
• Ugo Vaccaro

We consider secret sharing schemes in which the dealer is able (after a preprocessing stage) to activate a particular access structure out of a given set and/or to allow the participants to reconstruct different secrets (in different time instants) by sending them the same broadcast message. In this paper we establish a formal setting to study secret sharing schemes of this kind. The security of the schemes presented is unconditional, since they are not based on any computational assumption. We give bounds on the size of the shares held by participants, on the size of the broadcast message, and on the randomness needed in such schemes.

TCS Journal 1996 Journal Article

New lower bounds on the cost of binary search trees

• Roberte De Prisco
• Alfredo De Santis

In this paper we provide new lower bounds on the cost C of binary search trees. The bounds are expressed in terms of the entropy H of the probability distribution, the number of elements and the probability that a search is successful. Most of our lower bounds are derived by means of a new technique which exploits the relation between trees and codes. Our lower bounds compare favorably with known limitations. We also provide an achievable upper bound on the Kraft sum generalized to the internal nodes of a tree. This improves on a previous result.

TCS Journal 1996 Journal Article

On the information rate of secret sharing schemes

• Carlo Blundo
• Alfredo De Santis
• Luisa Gargano
• Ugo Vaccaro

We derive new limitations on the information rate and the average information rate of secret sharing schemes for access structure represented by graphs. We give the first proof of the existence of access structures with optimal information rate and optimal average information rate less than 1 2 + ε, where ε is an arbitrary positive constant. We also consider the problem of testing if one of these access structures is a substructure of an arbitrary access structure and we show that this problem is NP-complete. We provide several general lower bounds on information rate and average information rate of graphs. In particular, we show that any graph with n vertices admits a secret sharing scheme with information rate Ω((log n)/n).

STOC Conference 1994 Conference Paper

How to share a function securely

• Alfredo De Santis
• Yvo Desmedt
• Yair Frankel
• Moti Yung

FOCS Conference 1994 Conference Paper

On Monotone Formula Closure of SZK

• Alfredo De Santis
• Giovanni Di Crescenzo
• Giuseppe Persiano
• Moti Yung

We investigate structural properties of statistical zero knowledge (SZK) both in the interactive and in the non-interactive model. Specifically, we look into the closure properties of SZK languages under monotone logical formula composition. This gives rise to new protocol techniques. We show that interactive SZK for random self reducible languages (RSR) (and for co-RSR) is closed under monotone Boolean operations. Namely, we give SZK proofs for monotone Boolean formulae whose atoms are statements about an SZK language which is RSR (or a complement of RSR). All previously known languages in SZK are in these classes. We then show that if a language L has a non-interactive SZK proof system then honest-verifier interactive SZK proof systems exist for all monotone Boolean formulae whose atoms are statements about the complement of L. We also discuss extensions and generalizations. >

TCS Journal 1994 Journal Article

The knowledge complexity of quadratic residuosity languages

• Alfredo De Santis
• Giovanni Di Crescenzo
• Guiseppe Persiano

Noninteractive perfect zero-knowledge (ZK) proofs are very elusive objects. In fact, since the introduction of the noninteractive model of Blum. (1988), the only perfect zero-knowledge proof known was the one for quadratic nonresiduosity of Blum. (1991). The situation is no better in the interactive case where perfect zero-knowledge proofs are known only for a handful of particular languages. In this work, we show that a large class of languages related to quadratic residuosity admits noninteractive perfect zero-knowledge proofs. More precisely, we give a protocol for the language of thresholds of quadratic residuosity. Moreover, we develop a new technique for converting noninteractive zero-knowledge proofs into round-optimal zero-knowledge proofs for an even wider class of languages. The transformation preserves perfect zero knowledge in the sense that, if the noninteractive proof we started with is a perfect zero-knowledge proof, then we obtain a round-optimal perfect zero-knowledge proof. The noninteractive perfect zero-knowledge proofs presented in this work can be transformed into 4-round (which is optimal) interactive perfect zero-knowledge proofs. Until now, the only known 4-round perfect ZK proof systems were the ones for quadratic nonresiduosity (Goldwasser et al. , 1989) and for graph nonisomorphism (Goldreich et al. , 1986) and no 4-round perfect zero-knowledge proof system was known for the simple case of the language of quadratic residues.

FOCS Conference 1992 Conference Paper

Zero-Knowledge Proofs of Knowledge Without Interaction (Extended Abstract)

• Alfredo De Santis
• Giuseppe Persiano

A zero-knowledge proof system of knowledge is a protocol between two parties called the prover and the verifier. The prover wants to convince the verifier that he 'knows' the proof of a given theorem without revealing any additional information. This is different from a zero-knowledge proof system of membership where the prover convinces the verifier only of the veridicity of the statement. Zero-knowledge proofs of knowledge are very useful tools in the design of secure protocols. Though, the concept of a proof of knowledge is a very subtle one and great care is needed to obtain a satisfying formalization. The authors investigate the concept of a zero-knowledge proof of knowledge with a non-interactive model. Here, the prover and the verifier share a short random string and the only communication allowed is from the prover to the verifier. Although this is a simpler model than the interactive one, still formalizing zero-knowledge proofs of knowledge is a delicate task. >

FOCS Conference 1988 Conference Paper

Learning Probabilistic Prediction Functions (Extended Abstract)

• Alfredo De Santis
• George Markowsky
• Mark N. Wegman

The question of how to learn rules, when those rules make probabilistic statements about the future, is considered. Issues are discussed that arise when attempting to determine what a good prediction function is, when those prediction functions make probabilistic assumptions. Learning has at least two purposes: to enable the learner to make predictions in the future and to satisfy intellectual curiosity as to the underlying cause of a process. Two results related to these distinct goals are given. In both cases, the inputs are a countable collection of functions which make probabilistic statements about a sequence of events. One of the results shows how to find one of the functions, which generated the sequence, the other result allows to do as well in terms of predicting events as the best of the collection. In both cases the results are obtained by evaluating a function based on a tradeoff between its simplicity and the accuracy of its predictions. >