1. INTRODUCTION On the Data Expansion of the Huffman Compression Algorithm (2008)
Roberto De, Prisco, Alfredo De Santis
Fully Dynamic Secret Sharing Schemes \Lambda (2008)
Carlo Blundo, Antonella Cresti, Alfredo De Santis, Ugo Vaccaro
Abstract 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...
On the data expansion of the Huffman compression algorithm (2007)
Roberto De Prisco, Alfredo De Santis
this paper we study the maximum data expansion of Huffman codes. We provide some new properties of the maximum data expansion
Catastrophic Faults in Reconfigurable Systolic Linear Arrays (2007)
Roberto De Prisco, Alfredo De Santis
In regular architectures of identical processing elements, a widely used technique to improve the reconfigurability of the system consists of providing redundant processing elements and connections...
A Lower Bound on Encoding Length in Lossy Transmission (2007)
Alfredo De Santis, Barbara Masucci
Network heterogeneity has become a major issue and multi-media applications have to cope with interconnected networks consisting of many subnetworks of unevenly distributed resources. Information is...
On Optimal Binary Search Trees (2007)
Roberto De Prisco, Alfredo De Santis
We present a new linear time heuristic for constructing binary search trees. The analysis of the algorithm, by establishing an upper bound on the cost of the produced binary search trees, permits to...
A t-Private k-Database Private Information Retrieval Scheme (2007)
Carlo Blundo, Alfredo De Santis
A private information retrieval scheme enables a user to privately recover an item from a public accessible database. In this paper we present a private information retrieval scheme for k replicated...
LABORATORY FOR COMPUTER SCIENCE MIT/LCS/TM-536 (2007)
Hu Man Codes, Roberto De Prisco, Alfredo De Santis
On the redundancy achieved
MIT/LCS/TM-536 On the redundancy achieved (2007)
Huffman Codes, Roberto De Prisco, Roberto De Prisco, Alfredo De Santis, Alfredo De Santis
This document has been made available free of charge via ftp from the
New constructions for provably-secure time-bound hierarchical key assignment schemes (2007)
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...
Visual Cryptography Schemes with Optimal Pixel Expansion (2006)
Carlo Blundo Stelvio, Carlo Blundo, Stelvio Cimato, Alfredo De Santis
A visual cryptography scheme encodes a black & white secret image into n shadow images called shares which are distributed to the n participants. Such shares are such that only qualified subsets...
On Unconditionally Secure Distributed Oblivious Transfer ∗ (2006)
Carlo Blundo, Alfredo De Santis, Douglas Stinson
This paper is about the Oblivious Transfer in the distributed model proposed by M. Naor and B. Pinkas. In this setting a Sender has n secrets and a Receiver is interested in one of them. During a set...
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...
Provably-secure time-bound hierarchical key assignment schemes (2006)
Alfredo De Santis, Anna Lisa Ferrara, Barbara Masucci
Abstract A time-bound hierarchical key assignment scheme is a method to assign time-dependentencryption keys to a set of classes in a partially ordered hierarchy, in such a way that each class can...
Provably-secure time-bound hierarchical key assignment schemes (2006)
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 can compute...
Security of Public Key Cryptosystems based on Chebyshev Polynomials (2004)
Pina Bergamo, Alfredo De Santis, Ljupco Kocarev
Chebyshev polynomials have been recently proposed for designing public-key systems. Indeed, they enjoy some nice chaotic properties, which seem to be suitable for use in Cryptography. Moreover, they...
A simple algorithm for the constrained sequence problems (2004)
Francis Y. L. Chin, Alfredo De Santis, Anna Lisa Ferrara, N. L. Ho, S. K. Kim
Abstract In this paper we address the constrained longest common subsequence problem. Giventwo sequences X, Y and a constrained sequence P, a sequence Z is a constrained longestcommon subsequence for...
On Unconditionally Secure Distributed Oblivious Transfer (2003)
Carlo Blundo, Paolo D'Arco, Alfredo De Santis, Douglas Stinson
This paper is about the Oblivious Transfer in the distributed model recently proposed by M. Naor and B. Pinkas. In this setting a Sender has n secrets and a Receiver is interested in one of them....
New Results on Unconditionally Secure Distributed Oblivious Transfer (Extended Abstract) (2002)
Carlo Blundo, Paolo D'Arco, Alfredo De Santis, Douglas R. Stinson
This paper is about the Oblivious Transfer in the distributed model recently proposed by M. Naor and B. Pinkas. In this setting a Sender has n secrets and a Receiver is interested in one of them....
Alfredo De Santis, Giovanni Di Crescenzo, Oded Goldreich
The input to the Graph Clustering Problem consists of a sequence of integers m 1;:::; m t and a sequence of P t i=1 m i graphs. The question is whether the equivalence classes, under the graph...
On the Contrast in Visual Cryptography Schemes (1999)
Carlo Blundo, Alfredo De Santis, Douglas R. Stinson
A visual cryptography scheme is a method to encode a secret image SI into shadow images called shares such that certain qualified subsets of shares enable the "visual" recovery of...
On the Contrast in Visual Cryptography Schemes (1999)
Carlo Blundo, Alfredo De Santis, Douglas R. Stinson
A visual cryptography scheme is a method to encode a secret image SI into shadow images called shares such that certain qualified subsets of shares enable the "visual" recovery of...
Extended Capabilities for Visual Cryptography (1999)
Giuseppe Ateniese, Carlo Blundo, Alfredo De Santis, Douglas R. Stinson
An extended visual cryptography scheme, EVCS for short, for an access structure (\Gamma Qual ; \Gamma Forb ) on a set of n participants, is a technique to encode n images in such a way that when we...
Alfredo De Santis, Barbara Masucci
A (t; k; n; S) ramp scheme is a protocol to distribute a secret s chosen in S among a set P of n participants in such a way that: 1) sets of participants of cardinality greater than or equal to k can...
The Randomness Complexity of Private Computation (1999)
Carlo Blundo, Alfredo De Santis, Giuseppe Persiano, Ugo Vaccaro
We consider the classic problem of n honest but curious players with private inputs x_1, ..., x_n who wish to compute the value of a fixed function F(x_1, ..., x_n) in such way that at the end of the...
Contrast Optimal Threshold Visual Cryptography Schemes (1998)
Carlo Blundo, Alfredo De Santis, Douglas R. Stinson
A (k; n)-threshold visual cryptography scheme ((k; n)-threshold VCS, for short) is a method to encode a secret image SI into n shadow images called shares such that any k or more shares enable the...
Communication-Efficient Anonymous Group Identification (1998)
Alfredo De Santis, Giovanni Di Crescenzo, Giuseppe Persiano
Identification schemes allow a user to identify herself to a verifying authority in a secure way (i.e., without revealing her secret key). Group identification schemes allow a user to identify...
On Lower Bounds for the Redundancy of Optimal Codes (1998)
Roberto De Prisco, Alfredo De Santis
The problem of providing bounds on the redundancy of an optimal code for a discrete memoryless source in terms of the probability distribution of the source, has been extensively studied in the...
Tight Bounds on the Information Rate of Secret Sharing Schemes (1997)
Carlo Blundo, Alfredo De Santis, Roberto De Simone, Ugo Vaccaro
A secret sharing scheme is a protocol by means of which a dealer distributes a secret s among a set of participants P in such a way that only qualified subsets of P can reconstruct the value of s...
Randomness-Efficient Non-Interactive Zero Knowledge (Extended Abstract) (1997)
Extended Abstract, Alfredo De Santis, Pino Persiano
) Alfredo De Santis, 1 Giovanni Di Crescenzo, 2 Pino Persiano 1 1 Dipartimento di Informatica ed Applicazioni Universit`a di Salerno, 84081 Baronissi (SA), Italy E-mail: fads,giuperg@dia.unisa.it 2...
A new bound for the data expansion of Huffman codes (1997)
Roberto De Prisco, Alfredo De Santis
In this paper we prove that the maximum data expansion ffi of Huffman codes is upper bounded by ffi ! 1:39. This bound improves on the previous best known upper bound ffi ! 2. We also provide some...
Constructions and Bounds for Visual Cryptography (1996)
Giuseppe Ateniese, Carlo Blundo, Alfredo De Santis, Douglas R. Stinson
. A visual cryptography scheme for a set P of n participants is a method to encode a secret image SI into n images in such a way that any participant in P receives one image and only qualified...
Constructions and Bounds for Visual Cryptography (1996)
Giuseppe Ateniese, Carlo Blundo, Alfredo De Santis, Douglas R. Stinson
. A visual cryptography scheme for a set P of n participants is a method to encode a secret image SI into n images in such a way that any participant in P receives one image and only qualified...
Visual Cryptography for General Access Structures (1996)
Giuseppe Ateniese, Carlo Blundo, Alfredo De Santis, Douglas R. Stinson
A visual cryptography scheme for a set P of n participants is a method to encode a secret image SI into n shadow images called shares, where each participant in P receives one share. Certain...
Visual Cryptography for General Access Structures (1996)
Giuseppe Ateniese, Carlo Blundo, Alfredo De Santis, Douglas R. Stinson
A visual cryptography scheme for a set P of n participants is a method to encode a secret image SI into n shadow images called shares, where each participant in P receives one share. Certain...
Constructions and Bounds for Visual Cryptography (1996)
Giuseppe Ateniese, Carlo Blundo, Alfredo De Santis, Douglas R. Stinson
. A visual cryptography scheme for a set P of n participants is a method to encode a secret image SI into n images in such a way that any participant in P receives one image and only qualified...
On the Contrast in Visual Cryptography Schemes (1996)
Carlo Blundo, Alfredo De Santis, Douglas R. Stinson
A visual cryptography scheme is a method to encode a secret image SI into shadow images called shares such that certain qualified subsets of shares enable the "visual" recovery of the...
On the Contrast in Visual Cryptography Schemes (1996)
Carlo Blundo, Alfredo De Santis, Douglas R. Stinson
A visual cryptography scheme is a method to encode a secret image SI into shadow images called shares such that certain qualified subsets of shares enable the "visual" recovery of the...
On the redundancy achieved by Huffman codes (1996)
Roberto De Prisco, Alfredo De Santis
It has been recently proved that the redundancy r of any discrete memoryless source satisfies r 1 \Gamma H(p N ), where p N is the least likely source letter probability. This bound is achieved only...
New Lower Bounds on the Cost of Binary Search Trees (1996)
Roberto 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...
Visual Cryptography for General Access Structures (1996)
Giuseppe Ateniese, Carlo Blundo, Alfredo De Santis, Douglas R. Stinson
A visual cryptography scheme for a set P of n participants is a method to encode a secret image SI into n shadow images called shares, where each participant in P receives one share. Certain...
Extended Schemes for Visual Cryptography (1996)
Giuseppe Ateniese, Carlo Blundo, Alfredo De Santis, Douglas R. Stinson
An extended visual cryptography scheme, (\Gamma Qual ; \Gamma Forb ; m)-EVCS for short, with pixel "expansion" m, for an access structure (\Gamma Qual ; \Gamma Forb ) on a set of n...
On the Number of Random Bits in Totally Private Computations (1995)
Carlo Blundo, Alfredo De Santis, Ugo Vaccaro
Abstract. We consider the classic problem of n honest but curious players with private inputs x1; : : : ; xn who wish to compute the value of a fixed function f(x1; \Delta \Delta \Delta; xn) in such...
Perfectly-Secure Key Distribution for Dynamic Conferences (1995)
Carlo Blundo, Alfredo De Santis, Amir Herzberg, Shay Kutten, Ugo Vaccaro, Moti Yung
A key distribution scheme for dynamic conferences is a method by which initially an (off-line) trusted server distributes private individual pieces of information to a set of users. Later, each...
Extended Schemes for Visual Cryptography (1995)
Giuseppe Ateniese, Carlo Blundo, Alfredo De Santis, Douglas R. Stinson
An extended visual cryptography scheme, (\Gamma Qual ; \Gamma Forb ; m)-EVCS for short, with pixel "expansion" m, for an access structure (\Gamma Qual ; \Gamma Forb ) on a set of n...
Randomness in Distribution Protocols (1994)
Carlo Blundo, Ugo Vaccaro, Alfredo De Santis, Alfredo De Santis
Randomness is a useful computation resource due to its ability to enhance the capabilities of other resources. Its interaction with resources such as time, space, interaction with provers and its...
Fully Dynamic Secret Sharing Schemes (1994)
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...
On the redundancy achieved by Huffman codes (1994)
Roberto De Prisco, Alfredo De Santis
It has been recently proved that the redundancy r of any discrete memoryless source satisfies r 1\GammaH(p N ), where p N is the least likely source letter probability. We prove that this bound is...
On Monotone Formula Closure of SZK (1994)
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...
Tight Upper and Lower Bounds on the Path Length of Binary Trees (1993)
Alfredo De Santis, Giuseppe Persiano
Abstract. The external path length of a tree T is the sum of the lengths of the paths from the root to each external node. The maximal path length difference, \Delta, is the difference between the...
On the information rate of secret sharing schemes (1993)
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...
Size of Shares and Probability of Cheating in Threshold Schemes (1993)
Marco Carpentieri, Alfredo De Santis, Ugo Vaccaro, Alfredo De, Santis Ugo Vaccaro
In this paper we study the amount of secret information that must be given to participants in any secret sharing scheme that is secure against coalitions of dishonest participants in the model of...
New Lower Bounds on the Cost of Binary Search Trees (1993)
Roberto De Prisco, Alfredo De Santis
In this paper we provide new lower bounds on the cost of binary search trees. The bounds are expressed in terms of the entropy of the probability distribution, the number of elements and the...
Catastrophic Faults in Reconfigurable Linear Arrays of Processors (1993)
Roberto De Prisco, Alfredo De Santis
In regular architectures of identical processing elements, a widely used technique to improve the reconfigurability of the system consists of providing redundant processing elements and mechanisms of...
Noninteractive zero-knowledge (1991)
Alfredo De Santis, Giovanni Di Crescenzo, Rafail Ostrovsky, Giuseppe Persiano
Abstract. Non-Interactive Zero Knowledge (NIZK), introduced by Blum, Feldman, and Micali in 1988, is a fundamental cryptographic primitive which has attracted considerable attention in the last...
Noninteractive zero-knowledge (1991)
Alfredo De Santis, Giovanni Di Crescenzo, Rafail Ostrovsky, Giuseppe Persiano
Abstract. Non-Interactive Zero Knowledge (NIZK), introduced by Blum, Feldman, and Micali in 1988, is a fundamental cryptographic primitive which has attracted considerable attention in the last...
Non-Interactive Zero Knowledge (1991)
Manuel Blum, Alfredo De Santis, Silvio Micali, Giuseppe Persiano
We investigate the possibility of disposing of interaction between Prover and Verifier in a zeroknowledge proof if they share beforehand a short random string. Without any assumption, we prove that...
Noninteractive zero-knowledge (1991)
Alfredo De Santis, Giovanni Di Crescenzo, Giuseppe Persiano
Abstract. Non-Interactive Zero Knowledge (NIZK), introduced by Blum, Feldman, and Micali in 1988, is a fundamental cryptographic primitive which has attracted considerable attention in the last...
New Bounds on the Information Rate of Secret Sharing Schemes
Carlo Blundo, Alfredo De Santis, Antonio Giorgio Gaggia, Ugo Vaccaro
A secret sharing scheme permits a secret to be shared among participants in such a way that only qualified subsets of participants can recover the secret, but any non-qualified subset has absolutely...
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...