Author name cluster

Roberto De Prisco

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

8 papers

2 author rows

TCS Journal 2024 Journal Article

Efficient and reliable post-quantum authentication

Paolo D'Arco
Roberto De Prisco
Angel Perez del Pozo

In this paper we propose a new lightweight authentication protocol which is efficient, reliable and, properly instantiated, suitable for the post-quantum world. It is a two-level protocol, which supports unbounded message transmission. It can be useful in several settings, from the standard sender-receiver setting, to unreliable multicast and broadcast communication in networks with resource-constrained devices. The key ideas underlying our design are mainly three: the hash-chaining method, some techniques used in MAC-based authentication protocols for multicast communication, and the use of the Guy Fawkes signatures. To our knowledge, our protocol is the first one that solves the unbounded number of message transmission issue in unreliable settings. It does not lose efficiency and introduces only a constant-size overhead in message transmission, compared to solutions assuming a bounded number of message transmissions. We rigorously model the adversarial setting and show that our protocol satisfies the definition, leveraging on standard assumptions. Apart from the technical contribution, along the line, we also point out the relevance of ideas and techniques developed in the past in the area of efficient authentication, in order to provide new authentication schemes, ready for the post-quantum world.

Details DOI

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.

Details DOI

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.

Details

TCS Journal 2016 Journal Article

Secure computation without computers

Paolo D'Arco
Roberto De Prisco

The design of secure protocols which can be used without the aid of a computer and without cryptographic knowledge is an interesting and challenging research task. Indeed, protocols enjoying these features could be useful in a variety of settings where computers cannot be used or where people feel uncomfortable to interact with or trust a computer. In this paper we make a step in such a direction: we propose a novel method for performing secure two-party computations that, apart from the setup phase, requires neither a computing machinery nor cryptographic knowledge. By merging together in a suitable way two beautiful ideas of the 80's and the 90's, Yao's garbled circuit construction and Naor and Shamir's visual cryptography, respectively, we enable Alice and Bob to securely evaluate a function f ( ⋅, ⋅ ) of their inputs, x and y, through a pure physical process. Indeed, once Alice has prepared a set of properly constructed transparencies (for this activity a computer is useful), Bob computes the function value f ( x, y ) by applying a sequence of simple steps which require the use of a pair of scissors, superposing transparencies, and the human visual system. Our construction builds on Kolesnikov's gate evaluation secret sharing schemes.

Details DOI

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.

Details DOI

TCS Journal 2009 Journal Article

On designing truthful mechanisms for online scheduling

Vincenzo Auletta
Roberto De Prisco
Paolo Penna
Giuseppe Persiano

We study the online version of the scheduling problem Q ∥ C max involving selfish agents, considered by Archer and Tardos in [A. Archer, E. Tardos, Truthful mechanisms for one-parameter agents, in: Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science (FOCS), 2001, pp. 482–491], where jobs must be scheduled on m related machines, each of them owned by a different selfish agent. We present a general technique for transforming competitive online algorithms for Q ∥ C max into truthful online mechanisms with a small loss of competitiveness. We also investigate the issue of designing new online algorithms from scratch so as to obtain efficient competitive mechanisms, and prove some lower bounds on a class of “natural” algorithms. A “direct” use of such natural algorithms to construct truthful mechanisms yields only trivial upper bounds for the case of two machines. Finally, we consider mechanisms with verification, introduced by Nisan and Ronen [N. Nisan, A. Ronen, Algorithmic mechanism design, in: Proceedings of the 31st Annual ACM Symposium on Theory of Computing, STOC, 1999, pp. 129–140], for offline scheduling problems. We present the first constant-competitive online truthful mechanism with verification for any number of machines.

Details DOI

TCS Journal 2000 Journal Article

Revisiting the paxos algorithm

Roberto De Prisco
Butler Lampson
Nancy Lynch

The paxos algorithm is an efficient and highly fault-tolerant algorithm, devised by Lamport, for reaching consensus in a distributed system. Although it appears to be practical, it seems to be not widely known or understood. This paper contains a new presentation of the paxos algorithm, based on a formal decomposition into several interacting components. It also contains a correctness proof and a time performance and fault-tolerance analysis. The formal framework used for the presentation of the algorithm is provided by the Clock General Timed Automaton (Clock GTA) model. The Clock GTA provides a systematic way of describing timing-based systems in which there is a notion of “normal” timing behavior, but that do not necessarily always exhibit this “normal” timing behavior.

Details DOI

TCS Journal 1995 Journal Article

Minimal path length of trees with known fringe

Roberto De Prisco
Giuseppe Parlati
Giuseppe Persiano

In this paper we continue the study of the path length of trees with known fringe as initiated by Klein and Wood (1989) and De Santis and Persiano (1994). We compute the path length of the minimal tree with given number of leaves N and fringe Δ for the case Δ ⩾ N/2. This complements the result of De Santis and Persiano (1994) that studied the case Δ ⩽ N/2. Our methods also yield a linear time algorithm for constructing the minimal tree when Δ ⩾ N/2.

Details DOI