Dottorato di Ricerca in Informatica, XII Ciclo,
Universita degli Studi di Salerno
Relazione sull'Attivita e le Ricerche
svolte durante il Dottorato dalla
Dott.ssa Barbara Masucci
Corsi
La dott.ssa Barbara Masucci ha frequentato i seguenti corsi:
Corso : Introduzione al Network Programming.
Docenti : Dr. V. Scarano e Dr. G. Cattaneo (Universita di Salerno).
Durata : 20 ore.
Periodo : Maggio { Luglio 1997.
Luogo : Universita di Salerno.
Modalita esame : Progetti individuali.
Superamento esame : Avvenuto.
Corso : Sicurezza dei Sistemi Distribuiti.
Docente : Prof. A. Lioy (Politecnico di Torino).
Durata : 10 ore.
Periodo : Settembre 1997.
Luogo : Scuola di Benevento GII 1997.
Modalita esame : Questionari.
Superamento esame : Avvenuto.
Corso : Ingegneria degli Algoritmi.
Docente : Prof. G. Italiano (Universita di Venezia).
Durata : 10 ore.
Periodo : Settembre 1997.
Luogo : Scuola di Benevento GII 1997.
Modalita esame : Esercizi da svolgere.
Superamento esame : Avvenuto.
Corso : Architettura dei Computer ad Elevate Prestazioni.
Docenti : Prof. A. Mazzeo e Ing. Mazzocca (Universita di Napoli II).
Durata : 10 ore.
1
Periodo : Settembre 1997.
Luogo : Scuola di Benevento GII 1997.
Corso : Linguaggi di Interrogazione per Basi di Dati: Espressivita contro Facilita d'Uso.
Docente : Prof. D. Sacca (Universita della Calabria).
Durata : 10 ore.
Periodo : Settembre 1997.
Luogo : Scuola di Benevento GII 1997.
Corso : Valutazione delle Prestazioni dei Sistemi Informatici.
Docente : Prof. G. Serazzi (Politecnico di Milano).
Durata : 10 ore.
Periodo : Settembre 1997.
Luogo : Scuola di Benevento GII 1997.
Corso : Semantica Operazionale e Denotazionale dei Linguaggi di Programmazione.
Docente : Prof. Rocco De Nicola (Universita di Firenze).
Durata : 20 ore.
Periodo : Ottobre 1997.
Luogo : Universita di Salerno.
Modalita esami : Esercizi da svolgere in gruppo.
Superamento esame : Avvenuto.
Corso : Combinatorica per Informatici.
Docenti : Prof. U. Vaccaro (Universita di Salerno).
Durata : 20 ore.
Periodo : Novembre 1997 { Gennaio 1998.
Luogo : Universita di Salerno.
Modalita esame : Esercizi da svolgere.
Superamento esame : Avvenuto.
Corso : Algoritmi Avanzati.
Docente : Prof. G. Persiano e Dr. V. Auletta (Universita di Salerno).
Durata : 20 ore.
Periodo : Febbraio { Giugno 1998.
Luogo : Universita di Salerno.
Modalita esame : Seminari.
Superamento esame : Avvenuto.
2
Corso : Security Evaluation of Cryptosystems.
Docente : Prof. A. Shamir (Weizmann Institute, Israel).
Durata : 8 ore.
Periodo : Luglio 1998.
Luogo : Scuola di Lipari Distributed Systems and Security.
Corso : Basic Cryptographic Primitives.
Docenti : Prof. P. Rogaway (Univ. California) e Dr. R. Gennaro (IBM Research Center).
Durata : 8 ore.
Periodo : Luglio 1998.
Luogo : Scuola di Lipari Distributed Systems and Security.
Modalita esame : Esercizi da svolgere.
Superamento esame : Avvenuto.
Corso : Zero Knowledge Protocols.
Docente : Prof. S. Micali (M.I.T.) e Prof. A. De Santis (Universita di Salerno).
Durata : 8 ore.
Periodo : Luglio 1998.
Luogo : Scuola di Lipari Distributed Systems and Security.
Modalita esame : Esercizi da svolgere.
Superamento esame : Avvenuto.
Corso : Distributed Data Structures.
Docente : Prof. Y. Afek (Tel Aviv University).
Durata : 8 ore.
Periodo : Luglio 1998.
Luogo : Scuola di Lipari Distributed Systems and Security.
Modalita esame : Esercizi da svolgere.
Superamento esame : Avvenuto.
Corso : Scalable Distributed Systems.
Docente : Prof. L. Shrira (Brandeis University).
Durata : 8 ore.
Periodo : Luglio 1998.
Luogo : Scuola di Lipari Distributed Systems and Security.
Corso : Concurrency in Distributed Systems.
Docente : Prof. M. Herlihy (Brown University).
3
Durata : 8 ore.
Periodo : Luglio 1998.
Luogo : Scuola di Lipari Distributed Systems and Security.
Corso : Logica Fuzzy e Polivalente.
Docente : Prof. A. Di Nola e G. Gerla (Universita di Salerno).
Durata : 20 ore.
Periodo : Ottobre { Dicembre 1998.
Luogo : Universita di Salerno.
Superamento esame : Avvenuto.
Corso : Self-Stabilization.
Docenti : Prof. S. Dolev (Ben Gurion, Israel).
Durata : 6 ore.
Periodo : Giugno 1999.
Luogo : Scuola di Siena Advanced Distributed Computing.
Corso : Cryptographic Protocols.
Docente : Prof. C. Dwork (IBM Almaden, USA).
Durata : 6 ore.
Periodo : Giugno 1999.
Luogo : Scuola di Siena Advanced Distributed Computing.
Modalita esame : Esercizi da svolgere.
Superamento esame : Avvenuto.
Corso : Locality Sensitive Distributed Computing.
Docente : Prof. D. Peleg (Weizmann Institute, Israel).
Durata : 6 ore.
Periodo : Giugno 1999.
Luogo : Scuola di Siena Advanced Distributed Computing.
Modalita esame : Esercizi da svolgere.
Superamento esame : Avvenuto.
Corso : Timed Distributed Computations.
Docente : Prof. N. Santoro (Carleton University, Canada).
Durata : 6 ore.
Periodo : Giugno 1999.
Luogo : Scuola di Siena Advanced Distributed Computing.
4
Modalita esame : Esercizi da svolgere.
Superamento esame : Avvenuto.
Corso : Combinatorial Designs.
Docente : Prof. D. Stinson (University of Waterloo, Canada).
Durata : 30 ore.
Periodo : Settembre { Dicembre 1999.
Luogo : University of Waterloo, Canada.
Corso : Applied Cryptography.
Docente : Prof. A. J. Menezes (University of Waterloo, Canada).
Durata : 30 ore.
Periodo : Gennaio { Aprile 2000.
Luogo : University of Waterloo, Canada.
Corso : Introduction to Quantum Information Processing.
Docente : Prof. M. Mosca (University of Waterloo, Canada).
Durata : 30 ore.
Periodo : Gennaio { Aprile 2000.
Luogo : University of Waterloo, Canada.
Seminari e Presentazioni
La dott.ssa Barbara Masucci ha partecipato ai seguenti seminari:
Approximating Total Flow Time on Parallel Machines.
Seminario tenuto il 7 Marzo 1997 presso l'Universita di Salerno dal Dr. Stefano Leonardi,
Universita \La Sapienza" di Roma.
Visual Authentication and Identication.
Seminario tenuto il 19 Marzo 1997 presso l'Universita di Salerno dal Prof. Moni Naor,
The Weizman Institute of Science, Israele.
Extremal Problems under Divisibility or Intersection Constraints.
Seminario tenuto il 24 Marzo 1997 presso l'Universita di Salerno dal Prof. Levon Khachatrian, Dipartimento di Matematica dell'Universita di Bielefeld (Germania) ed Istituto di
Matematica dell'Accademia Armena delle Scienze.
Codes with Bounded Synchronization Delay.
Seminario tenuto il 9 Aprile 1997 presso l'Universita di Salerno dalla Prof.ssa Veronique
Bruyere, Universita di Mons, Belgio.
5
Weak Random Sources, Hitting Sets, and BPP Simulations.
Seminario tenuto il 5 Giugno 1997 presso l'Universita di Salerno dal Dr. Luca Trevisan,
University of Geneva, Svizzera.
Exact Analysis of Exact Change.
Seminario tenuto il 14 Luglio 1997 presso l'Universita di Salerno dal Dr. Yair Frankel,
CertCo, New York, USA.
Supporti alla Programmazione di Architetture Parallele.
Seminario tenuto il 6 Settembre 1997 presso la Facolta di Ingegneria di Benevento dal
Gruppo di Ricerca sull'Informatica Distribuita del DIS, Universita di Napoli \Federico
II".
Linguaggi Visuali.
Seminario tenuto il 9 Settembre 1997 presso la Facolta di Ingegneria di Benevento dal
Gruppo di Ricerca di Interfacce e Sistemi del DIA, Universita di Salerno.
Soft Computing per Riconoscimento di Immagini.
Seminario tenuto il 10 Settembre 1997 presso la Facolta di Ingegneria di Benevento dal
Gruppo di Ingegneria del Software della Facolta di Ingegneria di Benevento.
Interpretazione Astratta.
Seminario tenuto il 15 Settembre 1997 presso l'Universita di Salerno dal Prof. Giorgio
Levi, Universita di Pisa.
Verica di Programmi ed Interpretazione Astratta.
Seminario tenuto il 16 Settembre 1997 presso l'Universita di Salerno dal Prof. Giorgio
Levi, Universita di Pisa.
Machine Building as an Alternative to End User Programming.
Seminario tenuto il 18 Settembre 1997 presso l'Universita di Salerno dal Prof. L. Bottaci,
Universita di Hull (UK).
CGI-BIN e Sicurezza.
Seminario tenuto il 23 Ottobre 1997 presso l'Universita di Salerno dal Dr. Vittorio Scarano,
Universita di Salerno.
Succint Representation of Balanced Parantheses, Static Trees and Planar Graphs, [I. Munro
e V. Raman, FOCS '97].
Seminario tenuto il 27 Maggio 1998, presso l'Universita di Salerno, dalla dott.ssa Manuela
Montangero, Universita di Salerno.
Randomized Algorithms for Perfect Matching, [K. Mulmuley, U. Vazirani, e V. Vazirani,
Combinatorica, 1996].
Seminario tenuto il 27 Maggio 1998, presso l'Universita di Salerno, dal dott. Paolo D'Arco,
Universita di Salerno.
6
The Competitive Analysis of Risk Taking with Applications to Online Trading, [S. al-Binali,
FOCS '97].
Seminario tenuto il 17 Giugno 1998, presso l'Universita di Salerno, dalla dott.ssa Annalisa
De Bonis, Universita di Salerno.
On Line Routing in All Optical Network, [Y. Bartal e S. Leonardi, ICALP '97].
Seminario tenuto il 17 Giugno 1998, presso l'Universita di Salerno, dal dott. Ferdinando
Cicalese, Universita di Salerno.
On-Line Load Balancing, [Y. Azar, A. Z. Broder, e A. R. Karlin, Theoretical Computer
Science n. 130, 1994].
Seminario tenuto il 17 Giugno 1998, presso l'Universita di Salerno, dal dott. Gianluca De
Marco, Universita di Salerno.
Image Density is Complete for Non-Interactive Statistical Zero-Knowledge.
Seminario tenuto l'11 Luglio 1998, nell'ambito della Scuola di Lipari dal Dr. Giovanni Di
Crescenzo, University of California San Diego.
New Ecient and Secure Protocols for Veriable Signature Sharing and Other Applications.
Seminario tenuto l'11 Luglio 1998, nell'ambito della Scuola di Lipari, dal dott. Dario
Catalano, Universita di Catania.
Fast and Robust Digital Stream Authentication with On Line Witnesses.
Seminario tenuto l'11 Luglio 1998, nell'ambito della Scuola di Lipari, dal Prof. Francesco
Bergadano, Universita di Torino.
Reassuring Crypto-Protocol Parties by Theorem Proving.
Seminario tenuto l'11 Luglio 1998, nell'ambito della Scuola di Lipari, dal dott. Giampaolo
Bella, University of Cambridge (UK).
Steganographic File System, [R. Anderson and A. Shamir, 2nd Workshop on Information
Hiding, 1998].
Seminario tenuto il 6 Ottobre 1998, presso l'Universita di Salerno, dal dott. Paolo D'Arco,
Universita di Salerno.
Determining the Majority.
Seminario tenuto il 2 Novembre 1998, presso l'Universita di Salerno dal Prof. Martin
Aigner, Universita di Berlino.
Servizi Scalabili su Architetture Distribuite.
Seminario tenuto l'8 Gennaio 1999 presso l'Universita di Salerno dal Dr. Vittorio Scarano,
Universita di Salerno.
JSEB: Uno Strumento per la Scalabilita su Web.
Seminario tenuto il 15 Gennaio 1999 presso l'Universita di Salerno dal Dr. Vittorio
Scarano, Universita di Salerno.
7
Insegnare Hypertext ed Hypermedia sul WWW.
Seminario tenuto il 22 Gennaio 1999 presso l'Universita di Salerno dal Dr. Vittorio
Scarano, Universita di Salerno.
Recent Developments in the Theory of Codes.
Seminario tenuto il 22 Gennaio 1999 presso l'Universita di Salerno dalla Dr. Veronique
Bruyere, Universita di Mons, Belgio.
RPC come Supporto alla Progettazione ed allo Sviluppo di Applicazioni per la Rete.
Seminario tenuto il 29 Gennaio 1999 presso l'Universita di Salerno dal Dr. Vittorio
Scarano, Universita di Salerno.
La Storia di un Fallimento di Successo: Java.
Seminario tenuto il 5 Febbraio 1999 presso l'Universita di Salerno dal Dott. Vittorio
Scarano, Universita di Salerno.
RMI: Il Supporto Java per il Calcolo Distribuito.
Seminario tenuto il 12 Febbraio 1999 presso l'Universita di Salerno dal Dr. Vittorio
Scarano, Universita di Salerno.
Alcune Caratteristiche del Linguaggio Java.
Seminario tenuto il 19 Febbraio 1999 presso l'Universita di Salerno dal Dr. Vittorio
Scarano, Universita di Salerno.
Gestire con Java l'Accesso ad un Database Oracle.
Seminario tenuto il 26 Febbraio 1999 presso l'Universita di Salerno dal Dr. Vittorio
Scarano, Universita di Salerno.
Fuzzy Subgroups and Similarities.
Seminario tenuto l'1 Marzo 1999 presso l'Universita di Salerno dal Prof. Antonio Di Nola,
Universita di Salerno.
Estensione della Teoria dell'Unicazione mediante Similarita .
Seminario tenuto l'1 Marzo, 1999 presso l'Universita di Salerno dal Prof. Antonio Di Nola,
Universita di Salerno.
Automi non Classici.
Seminario tenuto l'1 Marzo 1999 presso l'Universita di Salerno dal Prof. Antonio Di Nola,
Universita di Salerno.
RMI come Protocollo di Supporto per la Programmazione Distribuita: Vizi Privati e Pubbliche Virtu .
Seminario tenuto il 16 Marzo 1999 presso l'Universita di Salerno dal Dr. Vittorio Scarano,
Universita di Salerno.
Kleptography: Using Cryptography against Cryptography.
Seminario tenuto il 26 Marzo 1999, presso l'Universita di Salerno dal Dott. Moti Yung,
Columbia University e CertCo, USA.
8
Visual Cryptography using Colors.
Seminario tenuto il 26 Marzo 1999 presso l'Universita di Salerno dal Dr. Roberto De
Prisco, Universita di Salerno.
Kleptography: Using Cryptography against Cryptography.
Seminario tenuto il 29 Marzo 1999 presso l'Universita di Salerno dal Dr. Moti Yung,
Columbia University e CertCo, USA.
Fuzzy Logic in Control Systems: Fuzzy Logic Controllers.
Seminario tenuto il 31 Marzo 1999 presso l'Universita di Salerno dal Prof. Giangiacomo
Gerla, Universita di Salerno.
Sistemi di Ragionamento Approssimato: Sistemi Esperti Fuzzy e Fuzzy Controller.
Seminario tenuto il 31 Marzo 1999 presso l'Universita di Salerno dal Prof. Giangiacomo
Gerla, Universita di Salerno.
Un Approccio basato sulla Logica Fuzzy per la Selezione di Stereotipi usati nei Sistemi
Ipermediali.
Seminario tenuto il 31 Marzo 1999 presso l'Universita di Salerno dal Prof. Giangiacomo
Gerla, Universita di Salerno.
Database Relazionali e Relazioni Fuzzy.
Seminario tenuto il 31 Marzo 1999 presso l'Universita di Salerno dal Prof. Giangiacomo
Gerla, Universita di Salerno.
Applicazioni Fuzzy su DSP.
Seminario tenuto il 31 Marzo 1999 presso l'Universita di Salerno dal Prof. Giangiacomo
Gerla, Universita di Salerno.
Cenni di Geometria Fuzzy: Aree e Perimetri.
Seminario tenuto il 31 Marzo 1999 presso l'Universita di Salerno dal Prof. Giangiacomo
Gerla, Universita di Salerno.
XML e la Integrazione HTML e XML.
Seminario tenuto il 13 Aprile 1999 presso l'Universita di Salerno dal Dr. Vittorio Scarano,
Universita di Salerno.
Java: Il Package java.awt.
Seminario tenuto il 21 Aprile 1999 presso l'Universita di Salerno dal Dr. Vittorio Scarano,
Universita di Salerno.
List Partitions.
Seminario tenuto il 6 Maggio 1999 presso l'Universita di Salerno dal Prof. Pavol Hell,
Simon Fraser University.
Lower and Upper Bounds on the Broadcasting and Gossiping Time of Restricted Protocols.
Seminario tenuto il 20 Maggio 1999 presso l'Universita di Salerno dal Dr. Michele Flammini, Universita dell'Aquila.
9
Error Resilient Data Compression.
Seminario tenuto il 19 Luglio 1999 presso l'Universita di Salerno dal Prof. James Storer,
Brandeis University.
Nonlinear Generators of Pseudo Random Numbers.
Seminario tenuto il 14 Settembre 1999 presso il Centre for Applied Cryptographic Research,
University of Waterloo, Canada, dal Dr. Igor Shparlinski, Macquarie University, Australia.
Secure Communication in Broadcast Channels.
Seminario tenuto il 20 Settembre 1999 presso il Centre for Applied Cryptographic Research,
University of Waterloo, Canada, dal Dr. Yongge Wang, University of Waterloo, Canada.
Secret and Public-Key Cryptosystems from Finite Groups.
Seminario tenuto il 27 Settembre 1999 presso il Centre for Applied Cryptographic Research,
University of Waterloo, Canada, dal Prof. Spyros Magliveras, University of Nebraska,
USA.
A Combinatorial Approach to (T,M,S)-Nets.
Seminario tenuto il 4 Ottobre 1999 presso il Centre for Applied Cryptographic Research,
University of Waterloo, Canada, dal Prof. Bill Martin, University of Winnipeg, Canada.
Ideal Arithmetic and Infrastructure of a Purely Cubic Function Field.
Seminario tenuto il 18 Ottobre 1999 presso il Centre for Applied Cryptographic Research,
University of Waterloo, Canada, dalla Prof. Renate Scheidler, University of Delaware,
USA.
Certication of Secure RSA Keys.
Seminario tenuto il 25 Ottobre 1999 presso il Centre for Applied Cryptographic Research, University of Waterloo, Canada, dal Dr. Steven Galbraith, University of Waterloo,
Canada.
Some Open Problems relating to the Elliptic Curves Discrete Logarithm Problem.
Seminario tenuto il 1 Novembre 1999 presso il Centre for Applied Cryptographic Research, University of Waterloo, Canada, dal Dr. Steven Galbraith, University of Waterloo,
Canada.
State-of-the Art in Implementing Algorithms for the (ordinary) Discrete Logarithm Problem.
Seminario tenuto il 1 Novembre 1999 presso il Centre for Applied Cryptographic Research, University of Waterloo, Canada, dal Dr. Reynald Lercier, Centre d'Electronique
de L'Armement, France.
Recent Developments in Hyperelliptic Curve Cryptography.
Seminario tenuto il 1 Novembre 1999 presso il Centre for Applied Cryptographic Research,
University of Waterloo, Canada, dal Dr. Andreas Stein, University of Waterloo, Canada.
10
The Parallelized Kangaroo Method.
Seminario tenuto il 1 Novembre 1999 presso il Centre for Applied Cryptographic Research,
University of Waterloo, Canada, dalla Dr. Edlyn Teske, University of Waterloo, Canada.
Capabilities and Limitations of Quantum Computers.
Seminario tenuto il 1 Novembre 1999 presso il Centre for Applied Cryptographic Research,
University of Waterloo, Canada, dal Prof. Michele Mosca, University of Waterloo, Canada.
Practice-Oriented Provable Security.
Seminario tenuto il 2 Novembre 1999 presso il Centre for Applied Cryptographic Research,
University of Waterloo, Canada, dal Prof. Mihir Bellare, University of California at San
Diego, USA.
Secure Design of Discrete Log Signature Schemes.
Seminario tenuto il 2 Novembre 1999 presso il Centre for Applied Cryptographic Research,
University of Waterloo, Canada, dal Prof. Jacques Stern, Ecole Normale Superieure,
France.
How Secure is the Die-Hellman Protocol?
Seminario tenuto il 2 Novembre 1999 presso il Centre for Applied Cryptographic Research,
University of Waterloo, Canada, dal Dr. Stefan Wolf, ETH Zentrum, Switzerland.
DHAES: An Encryption Scheme based on the Die-Hellman Problem.
Seminario tenuto il 2 Novembre 1999 presso il Centre for Applied Cryptographic Research,
University of Waterloo, Canada, dal dott. Michel Abdalla, University of California at San
Diego, USA.
Key Establishment Protocols and the Die-Hellman Problem.
Seminario tenuto il 2 Novembre 1999 presso il Centre for Applied Cryptographic Research,
University of Waterloo, Canada, dal Dr. Simon Blake-Wilson, Certicom Corp., Canada.
Authenticating Streamed Data in the Presence of Random Packet Loss.
Seminario tenuto il 3 Novembre 1999 presso il Centre for Applied Cryptographic Research,
University of Waterloo, Canada, dal dott. Philippe Golle, Stanford University, USA.
Fast Exponentiation Methods.
Seminario tenuto il 3 Novembre 1999 presso il Centre for Applied Cryptographic Research,
University of Waterloo, Canada, dal Dr. Dan Gordon, IDA Centre for Communication
Research, USA.
Ecient Implementation of Koblitz Curves and Generalized Mersenne Arithmetic.
Seminario tenuto il 3 Novembre 1999 presso il Centre for Applied Cryptographic Research,
University of Waterloo, Canada, dal Dr. Jerome Solinas, National Security Agency, USA.
Implementation Options for Finite Field Arithmetic for Elliptic Curve Cryptosystems.
Seminario tenuto il 3 Novembre 1999 presso il Centre for Applied Cryptographic Research,
University of Waterloo, Canada, dal Dr. Christof Paar, Worcester Polytechnic Institute,
USA.
11
Ecient Multiplication on Curves having an Endomorphism of Norm 1.
Seminario tenuto il 3 Novembre 1999 presso il Centre for Applied Cryptographic Research,
University of Waterloo, Canada, dal Dr. Robert Gallant, Certicom Corp., Canada.
Combinatorial Methods for Traceability.
Seminario tenuto l'8 Novembre 1999 presso il Centre for Applied Cryptographic Research,
University of Waterloo, Canada, dal Prof. Douglas Stinson, University of Waterloo,
Canada.
Spooky Action at a Distance.
Seminario tenuto il 15 Novembre 1999 presso il Centre for Applied Cryptographic Research,
University of Waterloo, Canada, dal Dr. Alain Tapp, University of Waterloo, Canada.
New Designs for Binary Sequences with Low Correlation and Large Linear Span.
Seminario tenuto il 29 Novembre 1999 presso il Centre for Applied Cryptographic Research,
University of Waterloo, Canada, dalla Prof. Guang Gong, University of Waterloo, Canada.
Selected Topics in Lucas-Based Primality Testing.
Seminario tenuto il 6 Dicembre 1999 presso il Centre for Applied Cryptographic Research,
University of Waterloo, Canada, dalla Dr. Siguna Muller, University of Klagenfurt, Austria.
Virtual Private Networks .
Seminario tenuto il 17 Gennaio 2000 presso il Centre for Applied Cryptographic Research,
University of Waterloo, Canada, dal Dr. Ken Giuliani, University of Waterloo, Canada.
Optimizing Baby Step-Giant Step Methods.
Seminario tenuto il 24 Gennaio 2000 presso il Centre for Applied Cryptographic Research,
University of Waterloo, Canada, dalla Dr. Edlyn Teske, University of Waterloo, Canada.
A Cryptographic Application of Certain Cubic Plane Curves.
Seminario tenuto il 7 Febbario 2000 presso il Centre for Applied Cryptographic Research,
University of Waterloo, Canada, dal Dr. Mark Bauer, University of Illinois, USA.
Ecient Signed-Digit Representation Used in Cryptography.
Seminario tenuto il 14 Febbraio 2000 presso il Centre for Applied Cryptographic Research,
University of Waterloo, Canada, dal Dr. Huapeng Wu, University of Waterloo, Canada.
Enumeration and Criteria for Cyclically Shift-Distinct GMW Sequences.
Seminario tenuto il 21 Febbraio 2000 presso il Centre for Applied Cryptographic Research,
University of Waterloo, Canada, dalla Prof. Guang Gong, University of Waterloo, Canada.
On the Interpolation Attacks on Block Ciphers.
Seminario tenuto il 28 Febbraio 2000 presso il Centre for Applied Cryptographic Research,
University of Waterloo, Canada, dal Dr. Amr Youssef, University of Waterloo, Canada.
Non-Interactive Public-Key Cryptography.
Seminario tenuto il 6 Marzo 2000 presso il Centre for Applied Cryptographic Research, University of Waterloo, Canada, dal Dr. Michael Jacobson, University of Waterloo, Canada.
12
A Cryptographic Key Exchange Technique Using Real Quadratic Fields.
Seminario tenuto il 7 Marzo 2000 presso il Centre for Applied Cryptographic Research, University of Waterloo, Canada, dal Prof. Hugh Williams, University of Manitoba, Canada.
Finite Field Computation Using Redundant Basis.
Seminario tenuto il 13 Marzo 2000 presso il Centre for Applied Cryptographic Research,
University of Waterloo, Canada, dal Dr. Huapeng Wu, University of Waterloo, Canada.
Speeding up the Arithmetic of Hyperelliptic Curves.
Seminario tenuto il 20 Marzo 2000 presso il Centre for Applied Cryptographic Research,
University of Waterloo, Canada, dal Dr. Andreas Stein, University of Waterloo, Canada.
Fast Arithmetic on Hyperelliptic Koblitz Curves.
Seminario tenuto il 27 Marzo 2000 presso il Centre for Applied Cryptographic Research,
University of Waterloo, Canada, dalla dott.ssa Tanja Lange, TU Braunschweig, Germany.
Solving the Pell Equation.
Seminario tenuto il 3 Aprile 2000 presso il Centre for Applied Cryptographic Research, University of Waterloo, Canada, dal Prof. Hugh Williams, University of Manitoba, Canada.
Quantum Computation and Quantum Information.
Seminario tenuto il 26 Aprile 2000 presso il Centre for Applied Cryptographic Research,
University of Waterloo, Canada, dal Dr. Michael Neilsen, University of Queensland.
Linear Key{Predistribution Schemes.
Seminario tenuto il 5 Luglio 2000 presso l'Universita di Salerno, dal Prof. Carles Padro ,
Universitat Politecnica de Catalunya.
Linear Secret Sharing Schemes with Multiplication.
Seminario tenuto il 31 Ottobre 2000 presso l'Universita di Salerno, dalla dott.ssa Vanesa
Daza, Universitat Politecnica de Catalunya.
La dott.ssa Barbara Masucci ha tenuto i seguenti seminari:
The Secure Metering Problem: Models, Schemes and Analysis.
Seminario tenuto il 22 Novembre 1999 nell'ambito del ciclo \Cryptography Seminars",
presso il Centre for Applied Cryptographic Research, University of Waterloo, Canada.
On Secret Set Schemes.
Seminario tenuto il 31 Gennaio 2000 nell'ambito del ciclo \Cryptography Seminars", presso
il Centre for Applied Cryptographic Research, University of Waterloo, Canada.
An Information Theoretical Approach to Metering Schemes.
Seminario tenuto il 26 Giugno 2000 nell'ambito del \2000 IEEE International Symposium
on Information Theory - ISIT 2000", Sorrento (Italy).
Dynamic Multi{Threshold Metering Schemes.
Seminario tenuto il 14 Agosto 2000 nell'ambito del \Seventh Annual Workshop on Selected
Areas in Cryptography - SAC 2000", Waterloo (Canada).
13
A Computationally Secure Metering Scheme with Pricing.
Seminario tenuto il 18 Settembre 2000 nell'ambito del \Workshop su Sistemi Distribuiti:
Algoritmi, Architetture e Linguaggi - WSDAAL 2000", Ischia (NA).
Metering Schemes for General Access Structures.
Seminario tenuto il 5 Ottobre 2000 nell'ambito del \6th European Symposium on Research
in Computer Security - ESORICS 2000", Toulouse (France).
Convegni e Workshop
La dott.ssa Barbara Masucci ha partecipato ai seguenti convegni:
Compression and Complexity of SEQUENCES 1997.
Convegno tenutosi dall' 11 al 13 Giugno 1997 a Positano (SA).
Informatica e Pubblica Amministrazione.
Workshop tenutosi l' 11 e il 12 Settembre presso la Facolta di Ingegneria di Benevento,
nell'ambito della Scuola di Dottorato GII 1997.
Fifth International Colloquium on Structural Information and Communication Complexity
- SIROCCO '98.
Convegno tenutosi dal 22 al 24 Giugno 1998 ad Amal (SA).
The Third Workshop on Elliptic Curve Cryptography (ECC '99).
Workshop tenutosi dall' 1 al 3 Novembre 1999 presso University of Waterloo, Waterloo,
Ontario, Canada.
2000 IEEE International Symposium on Information Theory - ISIT 2000.
Convegno tenutosi dal 25 al 30 Giugno 2000 a Sorrento (NA).
Seventh Annual Workshop on Selected Areas in Cryptography - SAC 2000.
Workshop tenutosi il 14 e 15 Agosto 2000 presso University of Waterloo, Waterloo, Ontario,
Canada.
Workshop su Sistemi Distribuiti: Algoritmi, Architetture e Linguaggi - WSDAAL 2000.
Workshop tenutosi dal 18 al 20 Settembre 2000 a Ischia (NA).
Sixth European Symposium on Research in Computer Security - ESORICS 2000.
Convegno tenutosi dal 4 al 6 Ottobre 2000 a Toulouse, France.
Scuole
La dott.ssa Barbara Masucci ha partecipato alle seguenti scuole:
Scuola di Dottorato \GII 1997", tenutasi a Benevento dal 3 al 15 settembre 1997, organizzata dalla Facolta di Ingegneria di Benevento, Universita di Salerno.
14
Tenth International School for Computer Science Researchers: \Distributed Systems and
Security", tenutasi a Lipari dal 5 al 18 Luglio 1998, organizzata dall'Universita di Catania.
5th International Summer School on Distributed Computing: \Advanced Distributed Computing", tenutasi alla Certosa di Pontignano, Siena, dal 21 al 27 Giugno 1999, organizzata
dall'Universita di Siena.
Attivita di ricerca
La dott.ssa Barbara Masucci ha svolto ricerca nell'ambito delle seguenti tematiche:
Priority Encoding Transmission Schemes (PET)
Multi{Secret Sharing Schemes
Randomness in Distributed Protocols
Secret Set Schemes
Metering Schemes
Commitment Schemes
Priority Encoding Transmission Schemes (PET) In molte applicazioni multimediali
lunghi messaggi vengono trasmessi attraverso reti eterogenee, cioe costituite da canali con capacita e velocita dierenti. Ciascun messaggio non viene trasmesso come una unita, ma suddiviso
in piccoli pacchetti, che vengono inviati sulla rete indipendentemente l'uno dall'altro. Una volta
spediti, alcuni pacchetti possono arrivare immediatamente a destinazione, ma altri (totalmente
arbitrari) possono essere persi o distrutti a causa di condizioni globali della rete, come overow
dei buer, congestione ed altre cause. Ad un certo punto il destinatario non puo piu aspettare
i pacchetti e deve cercare di recuperare la maggior parte possibile del messaggio originale dai
pacchetti ricevuti.
Uno schema PET (Priority Encoding Transmission) (fk ; P; M g =1 ) e un protocollo per
trasmettere ` messaggi M1 ; :::; M , sotto forma di jP j pacchetti di bit, attraverso una rete eterogenea, in modo che il messaggio M puo essere recuperato da almeno k pacchetti ricevuti.
In [14] e stato analizzato il caso in cui l'insieme dei Spacchetti trasmessi
e costituito da vari
T
sottoinsiemi avente intersezione non vuota, cioe P = =1 P e =1 P 6= ;, in modo che il
messaggio M puo essere recuperato da almeno k pacchetti in P . Chiaramente tali schemi
generalizzano PET. In particolare in [14] e stato provato un limite inferiore per la lunghezza
totale della codica, ovvero per la taglia complessiva dei pacchetti, nel caso in cui ` = 2. Il
signicato di tale limite e il seguente: nel caso della trasmissione contemporanea di due messaggi,
anche se alcuni pacchetti portano informazione comuni ad entrambi, non e possibile risparmiare
sulla lunghezza totale della codica. Questo vuol dire che non e possibile fare di meglio che
considerare schemi PET singoli, separati e indipendenti, per i due messaggi.
i
i
i
;:::;`
`
i
i
`
i
i
i
15
`
i
i
i
i
Multi{Secret Sharing Schemes Uno schema di condivisione del segreto e una tecnica per
condividere un segreto tra un insieme P di partecipanti in modo che solo i sottoinsiemi abilitati
di P , mettendo insieme le loro informazioni, possono ricostruire il segreto, mentre i sottoinsiemi
di P non abilitati a ricostruire il segreto non hanno alcuna informazione su esso. Gli schemi
di condivisione del segreto sono utili in tutte le azioni che richiedono la cooperazione tra varie
persone, come il lancio di un missile, l'apertura di una cassetta valori, etc...
Ci sono molte applicazioni pratiche, in particolare quelle associate alla gestione di chiavi
crittograche, in cui si ha la necessita di condividere vari segreti tra lo stesso insieme di partecipanti. Ad esempio si consideri la seguente situazione, proposta da Simmons: Vi e una base
militare in cui ciascun missile ha un dierente codice di abilitazione al lancio. Cio di cui si ha
bisogno, quindi, e un algoritmo in cui gli stessi pezzi di informazione possano essere utilizzati
per ricostruire i dierenti codici di abilitazione.
Uno dei principali problemi, legato all'implementazione degli schemi di condivisione del segreto, e quello di analizzare la quantita di informazioni distribuite ai partecipanti, dato che la
sicurezza di un sistema diminuisce con l'aumentare delle informazioni da tenere segrete.
Uno schema per la condivisione multipla di segreti e un protocollo per condividere un certo
numero di segreti, arbitrariamente relati, tra un insieme P di partecipanti. In [6] sono stati
analizzati tre dierenti modelli per la condivisione multipla di segreti e sono state analizzate
le relazioni tra tali modelli. Tali schemi sono stati formalizzati mediante strumenti di teoria
dell'informazione, che hanno consentito una descrizione semplice e compatta. In [6] e stato
provato che se e uno schema per la condivisione multipla di segreti rispetto a una ssata distribuzione di probabilita sull'insieme dei segreti, allora e anche uno schema per la condivisione
multipla di segreti rispetto a qualsiasi altra distribuzione di probabilita su tale insieme. Inoltre
sono state provate alcune limitazioni sulla taglia dell' informazione distribuita ai partecipanti
per varie strutture d'accesso, ed e stata provata l'ottimalita di tali limitazioni, cioe sono stati
mostrati i protocolli soddisfacenti tali limitazioni con l'eguaglianza.
In molte situazioni pratiche non e possibile distribuire ai partecipanti tutta le informazioni
segrete di cui essi hanno bisogno per avere una sicurezza perfetta. In tali situazioni vengono
utilizzati dei particolari schemi di condivisione dei segreti, detti schemi ramp. Uno schema
ramp (t; k; n; S ) e un protocollo per distribuire un segreto s, scelto in S , tra un insieme P di
n partecipanti, in modo che: 1) insiemi di partecipanti con cardinalita maggiore o uguale di k
possono ricostruire il segreto s; 2) insiemi di partecipanti con cardinalita minore o uguale di t
non hanno alcuna informazione su s, mentre 3) insiemi di partecipanti con cardinalita maggiore
di t e minore di k possono avere \qualche" informazione su s.
In [12] sono stati analizzati schemi ramp multipli, che sono protocolli per condividere piu
segreti tra un insieme P di partecipanti, usando dierenti schemi ramp. In particolare in tale
lavoro e stato provato un limite inferiore per la grandezza delle share distribuite ai partecipanti.
Il signicato di tale limite e il seguente: se ogni schema singolo in uno schema ramp multiplo e
ottimale rispetto alle informazioni distribuite ai partecipanti, allora anche lo schema complessivo
lo e . Pertanto il protocollo che distribuisce minori informazioni ai partecipanti e quello che
consiste nel considerare dierenti schemi ramp singoli, uno per ciascun segreto, e nel distribuire
a ciascun partecipante una share da ogni schema.
16
Randomness in Distributed Protocols In crittograa ci sono varie situazioni in cui e ne-
cessario generare numeri e stringhe binarie casuali, etc. Ad esempio, per garantire la sicurezza di
qualsiasi crittosistema, le chiavi crittograche devono essere scelte in un certo spazio delle chiavi,
e l'uso di una sorgente naturale di bit casuali, come una moneta onesta o una sorgente radioattiva,
e assolutamente essenziale. Pertanto negli ultimi anni vari sforzi sono stati eettuati per ridurre
il numero di bit casuali utilizzati da algoritmi probabilistici e per analizzare l'ammontare di bit
casuali necessari per raggiungere una certa performance. La misura piu naturale e generale per
l'ammontare di bit casuali e rappresentata dall'entropia di Shannon della sorgente che genera
i bit casuali, dato che l'entropia di una variabile casuale X , ovvero di una sorgente casuale
senza memoria, e approssimativamente uguale al numero medio di lanci di una moneta onesta
necessari per simulare le uscite di X .
Vari ricercatori hanno analizzato l'ammontare dei bit casuali necessari per la realizzazione
di schemi per la condivisione dei segreti.
In [12] e stato provato un limite inferiore per la randomness del dealer in schemi ramp
multipli, ovvero per la quantita di bit casuali necessari per generare le share, conoscendo i
segreti. Il signicato di tale limite e il seguente: se ogni schema singolo in uno schema ramp
multiplo e ottimale rispetto al numero di bit casuali utilizzati, allora anche lo schema complessivo
lo e. Pertanto il protocollo che utilizza il minor numero di bit casuali e quello che consiste nel
considerare dierenti schemi ramp singoli, uno per ciascun segreto, e nel distribuire a ciascun
partecipante una share da ogni schema.
In [8] e stato analizzato l'ammontare di bit casuali necessari per la realizzazione di schemi
per la condivisione multipla di segreti. Data una m-tupla di strutture d'accesso (una struttura
d'accesso e una specica di tutti i sottoinsiemi di P in grado di ricostruire il segreto), viene
fornito un limite inferiore per il numero di bit casuali necessario per realizzare uno schema di
condivisione multipla di segreti per la m-tupla in questione. Il limite inferiore e espresso in
termini di un parametro combinatoriale che dipende solo dalle strutture d'accesso e non dal
particolare schema utilizzato. Inne, viene fornita una completa caratterizzazione delle coppie
di strutture d'accesso, e per ciascuna coppia viene fornito il limite inferiore ottimale al numero
di bit casuali necessari per realizzare uno schema per tale coppia.
In [7] e stato fornito un limite inferiore per il numero di bit casuali necessari per realizzare
schemi a soglia dinamici, ovvero schemi in cui il dealer e in grado, dopo una fase di inizializzazione, di consentire ad insiemi di partecipanti, aventi una data cardinalita , la ricostruzione
di dierenti segreti, semplicemente mandando loro un messaggio di broadcast. Il limite fornito e ottimo, dato che esiste un protocollo che realizza uno schema a soglia dinamico, che usa
esattamente lo stesso numero di bit casuali.
Secret Set Schemes Ci sono varie situazioni nella comunicazione su reti, in cui e importante
mantenere segreta la destinazione di un messaggio. Ad esempio, in particolare nelle comunicazione in broadcast (reti locali, reti basate su trasmissione in pacchetti, satelliti, etc), in cui lo
stesso messaggio trasmesso da una sorgente puo essere ricevuto da dierenti stazioni di destinazione, puo essere necessario mantenere segreta l'informazione sulla destinazione. Per risolvere
il problema della segretezza riguardo alla destinazione di un messaggio, alcuni ricercatori hanno
introdotto il concetto di insieme segreto, un costrutto utile per la comunicazione in presenza di
partecipanti maliziosi. In [13] vengono studiati schemi per la realizzazione di insiemi segreti,
17
in cui un dealer consente ai partecipanti di testare la loro appartenenza in un insieme semplicemente mandando loro un messaggio di broadcast. In tali schemi qualunque partecipante,
guardando il messaggio di broadcast puo stabilire se appartiene o no all'insieme segreto, ma non
ha alcuna informazione sull'appartenenza di un altro partecipante all'insieme segreto. In [13]
viene prima presentato un modello incondizionatamente sicuro (la cui sicurezza non e basata su
alcuna assunzione computazionale) per la realizzazione di un insieme segreto, e vengono forniti
limiti inferiori sulla quantita di informazione da fornire ai partecipanti, sulla taglia del messaggio
di broacast (l' insieme segreto cifrato) e sul numero di bit casuali necessari per realizzare uno
schema per insiemi segreti. Tali limiti sono stretti, in quanto viene fornito un protocollo che
li raggiunge con eguaglianza. Inoltre vengono considerati schemi multipli per insiemi segreti.
Viene provato che il modo migliore per costruire schemi di tale tipo consiste nel combinare insieme vari schemi singoli. In particolare, se ciascuno schema singolo e ottimale, anche lo schema
multiplo risultante sara ottimale. Inne, vengono considerati schemi computazionali per insiemi
segreti e viene provato che tali schemi esistono se e solo se esistono crittosistemi simmetrici sicuri.
Metering Schemes La crescente popolarita di Internet e del World Wide Web sta dionendo
una serie di applicazioni orientate al commercio, tra cui la pubblicita .
Secondo gli ultimi dati forniti dalle societa americane di rilevazione, gli investimenti pubblicitari sul Web hanno superato i 2 miliardi di dollari nel secondo quadrimestre del 2000. Per
quanto riguarda l'Italia, una ricerca condotta nel 1999 dalla Iab Italia (Internet Advertising
Bureau, l'associazione che raggruppa i piu' importanti operatori della pubblicita online in Italia
e charter italiano dell'Internet Advertising Bureau) e dalla Price WaterhouseCoopers (la piu
grande organizzazione internazionale di servizi professionali) ha mostrato che tale settore ha
raggiunto i 60 miliardi di lire nel 1999.
Gli inserzionisti necessitano di un metodo per misurare l'ecacia della pubblicita, in base al
quale stabilire il prezzo da pagare per il servizio. Tale ecacia viene misurata in base al numero
di accessi da parte di client al server che ospita la pubblicita .
L'usuale metodo statistico di scelta di campioni, attualmente utilizzato per eettuare misure
su altri media come TV e radio, e appropriato quando c'e un numero relativamente piccolo di
canali tra cui l'utente puo scegliere. Ma questo non e di certo il caso del web, che ore milioni
di pagine da visitare.
I metodi esistenti per tale controllo sul web si basano tutti sull'onesta del server e utilizzano
dei moduli software per monitorare l'attivita del sito. Chiaramente, in situazioni in cui sono
coinvolti forti interessi commerciali non ci si puo dare dell'onesta di un server, che avrebbe tutto
l'interesse a falsare i dati per guadagnare una maggiore quantita di denaro. Pertanto sarebbe
necessario un sistema che consenta agli inserzionisti di pagare il prezzo pattuito soltanto se le
pagine web contenenti la pubblicita sono state visitate un certo numero di volte.
Negli scorsi anni ci sono stati vari tentativi di risolvere il problema del controllo degli accessi,
dato che manca uno standard relativo a tale processo. I primi a considerare il problema del
controllo degli accessi in modo formale sono stati Franklin e Malkhi [16]. Essi hanno fornito
soluzioni poco soddisfacenti dal punto di vista della sicurezza, ovvero schemi in cui client corrotti
possono aiutare i server a falsicare le loro prove. Tali schemi, pertanto, risultano poco adabili
in ambiti in cui ci sono forti interessi commerciali.
Naor e Pinkas [18] sono stati i primi a fornire schemi sicuri, in cui server che hanno avuto
18
meno di un certo numero di visite non sono in grado di provare il contrario, neanche tramite
l'aiuto di altri server complici, o tramite le informazioni fornite da client corrotti. Inoltre essi
hanno fornito varie costruzioni per sistemi di controllo degli accessi, basati su ecienti tecniche
crittograche.
Lo scenario considerato da Naor e Pinkas [18] e il seguente: abbiamo n client, m server e
un'agenzia di verica il cui compito e quello di misurare l'interazione tra client e server, ovvero
stabilire quante volte un server e stato visitato dai client. Se un server viene visitato da almeno
h client, dove h e un parametro ssato a priori ed identico per tutti i server, allora e in grado di
provare matematicamente questo fatto all' agenzia di verica mostrandogli una prova, costruita
in base alle informazioni che ciascun client ha fornito durante l'interazione con esso. Invece,
un server che ha ricevuto meno di h visite non e in grado di convincere l'agenzia del contrario,
ovvero non e in grado di fornire la prova.
Gli schemi di metering comportano la distribuzione di informazione ai client e ai server. I
client ricevono informazione dall'agenzia di controllo e cedono parte di questa informazione ai
server che visitano. Questa informazione e poi utilizzata dai server per fornire all'agenzia la
prova del numero di visite ricevute da ciascuno di essi. Ovviamente, l'informazione distribuita
ai server e ai client determina un certo \overhead" sulla comunicazione complessiva del sistema.
Pertanto, e importante costruire schemi in cui questo \overhead" e il minimo possibile. Il problema di ottenere limitazioni sulla taglia delle informazioni distribuite a client e server negli schemi
di metering e uno dei problemi di base nell'area. Si considerino le seguenti osservazioni: Innanzitutto, la sicurezza di un sistema tende a degradare con l'aumentare dell'informazione da tenere
segreta, ovvero l'informazione distribuita ai client. Inoltre, i client che partecipano al processo
di monitoraggio non ricevono alcun denaro dall'agenzia di controllo, e quindi l'informazione loro
distribuita dovrebbe essere la minima possibile.
Negli schemi di metering considerati da Naor e Pinkas [18] un server che ha ricevuto meno
del pressato numero di visite da parte di client e' nella stessa situazione di un server che non
ha ricevuto alcuna visita. In [11], allo scopo di fornire un compromesso tra ecienza e sicurezza,
sono stati considerati schemi in cui server che hanno ricevuto meno di un certo numero di visite
ottengono qualche informazione sulla prova anche se non sono capaci di ricostruirla completamente. Tale perdita di sicurezza comporta una maggiore ecienza, in quanto la quantita di
informazione distribuita diminuisce. Schemi di tale tipo sono utili nelle applicazioni pratiche in
cui un server viene pagato solo se dimostra di aver avuto un numero molto elevato di accessi.
Negli schemi di metering considerati da Naor e Pinkas [18] la soglia, costituente il minimo
numero di visite da parte dei client necessario a ciascun server per computare la prova, e ssata
ed e la stessa per ogni server e per ogni time frame. Questa e una situazione accettabile solo
quando c'e una relazione a lungo termine tra l'agenzia di controllo e i server. Allo scopo di
ottenere un sistema di misura dinamico, in [5] sono stati considerati schemi di metering in cui
la soglia e diversa per ciascun server e puo cambiare dinamicamente nel tempo.
Allo scopo di avere un piu essibile sistema di pagamento, utile nelle situazioni in cui l'agenzia
di controllo ha necessita di conoscere il numero esatto di visite ricevute da un server, in [2, 4, 3]
e stato considerato il seguente scenario: Abbiamo due soglie l e h, dove l h ed ogni server
puo essere in tre situazioni dierenti: Se viene visitato da al piu l client allora non riceve alcun
pagamento. Se invece viene visitato da almeno h client riceve l'intera somma pattuita. In una
situazione del genere c'e bisogno di schemi di metering in cui sia possibile avere prove dierenti
19
per ciascun valore compreso tra ` + 1 and h. In particolare, in [2] sono stati considerati schemi
incondizionatamente sicuri (non basati su alcuna assunzione computazionale), mentre in [3]
sono stati considerat schemi la cui sicurezza e basata su assunzioni di tipo computazionale (in
particolare, sull'assunzione di Die-Hellman w sul problema del logaritmo discreto in un campo
nito).
In [17] sono stati considerati schemi per il controllo degli accessi in cui durante la fase di
costruzione della prova l'agenzia di verica collabora con i server. Tali schemi sono piu ecienti
di quelli considerati in [2] in quanto la complessita di distribuzione dell'informazione e minore.
Lo svantaggio i tali schemi e che richiedono che ci sia comunicazione tra server e agenzia di
verica durante tutto il processo.
I sistemi di misurazione considerati negli schemi di metering presenti in letteratura consistono
di semplici soglie. In altre parole, tali sistemi di misura sono in grado di distinguere tra due
casi: o il server ha ricevuto il numero di visite richiesto oppure no. In [15] e stata considerato
uno scenario piu generale, in cui i client sono divisi in un certo numero di sottoinsiemi pressati,
chiamati insiemi qualicati, e l'agenzia di controllo e interessata a sapere se un server e stato
visitato da tutti i client costituenti un insieme qualicato. L'insieme degli insiemi qualicati viene
detto struttura d'accesso. In particolare sono state considerate due strutture d'accesso che hanno
interessanti applicazioni pratiche, le strutture multilevel e compartmented. Ad esempio, schemi
di metering che realizzano tali strutture possono essere utilizzati per misurare l'interazione tra
un server e un particolare gruppo di client.
In tutti i lavori citati gli schemi di metering sono stati analizzati dal punto di vista incondizionatamente sicuro e sono stati derivati limiti inferiori sull'informazione distribuita a client e
server. In particolare in [17] e stato anche valutato l'ammontare di bit casuali utilizzati.
Commitment Schemes Gli schemi di commitment furono introdotti da Blum [1] nel 1982.
In uno schema di commitment abbiamo un trasmettente, Alice, e un ricevente, Bob. Lo schema e
costituito da un protocollo commit e un protocollo reveal. Per fare commitment di un valore x
a Bob, Alice usa il protocollo commit e manda una informazione y0 a Bob. A questo punto Bob
non e in grado di avere alcuna informazione sul valore di cui Alice ha fatto il commitment, ma
potra utilizzare l'informazione y0 per scoprirlo in seguito. Alice utilizzera il protocollo reveal
per rivelare il valore x0 di cui ha fatto il commitment. Bob accettera tale valore solo se risultera
essere consistente con l'informazione y0 ricevuta durante il protocollo commit.
Le proprieta informali che uno schema di commitment dovrebbe soddisfare sono le seguenti:
o
Correctness: Se entrambi i partecipanti sono onesti e seguono i protocolli, durante il protocollo reveal Bob scoprira il valore x0 di cui Alice ha fatto il commitment.
Concealing
Bob non ha alcuna informazione sul valore di x0 durante il protocollo commit.
Binding
Dopo il protocollo commit c'e un unico valore x0 che Bob dovrebbe accettare
durante il protocollo reveal (cioe Alice non puo cambiare idea sul valore di
cui ha fatto il commitment).
20
Gli schemi di commitment sono stati studiati da vari ricercatori recentemente. In particolare,
e stato provato in [10] che non esiste uno schema di commitment incondizionatamente sicuro
quando i partecipanti sono solo Alice e Bob. Pertanto, i ricercatori si sono concentrati su schemi
in cui la sicurezza incondizionata e parziale e sono stati proposti schemi in cui la potenza di
calcolo di Alice o Bob e polinomialmente limitata. Tali schemi sono detti computationally binding
o computationally concealing, rispettivamente.
Rivest [19] ha proposto uno scenario che prevede la presenza di una terza parte data, Ted,
che si occupa dell'inizializzazione del sistema. Nel suo schema Ted e onesto e comunica con Alice
e Bob tramite canali privati. L'attivita di Ted si limita solo alla fase di inizializzazione, in cui
Ted fornisce informazioni ad Alice e Bob.
In [9] viene provato che il protocollo proposto da Rivest non rispetta la proprieta di concealing. Infatti, per particolari scelte del valore di cui fare commitment, Bob e in grado di scoprire
immediatamente qual'e il valore di cui Alice ha fatto commitment, senza avere l'informazione
fornita dal protocollo reveal. In [9] viene fornita una versione modicata del protocollo di Rivest
che rispetta la proprieta di concealing. Inoltre, in [9] viene presentato un modello matematico
formale per la descrizione di schemi di commitment incondizionatamente sicuri e vengono analizzate le proprieta di correctness e binding. In particolare, viene provato che in tali schemi
c'e sempre una piccola probabilita che Alice inganni Bob, facendo commitment di un valore,
e rivelandogliene uno dierente. Inne, in [9] vengono provati vari bound sulla probabilita di
inganno e vengono presentate costruzioni in cui tale probabilita e minimale. Inoltre, vengono
considerate le relazioni tra schemi di commitment e ane resolvable designs.
Attivita di Ricerca all'Estero
La dott.ssa Barbara Masucci si e recata presso il Centre for Applied Cryptographic Research,
University of Waterloo, Ontario, Canada, dal 1 Settembre 1999 al 30 Aprile 2000 per svolgere
attivita di ricerca con il Prof. Douglas R. Stinson.
Bibliograa
[1] M. Blum, \Coin Flipping by Telephone: a Protocol for Solving Impossible Problems", in
24th IEEE Spring Computer Conference, pp. 133{137, IEEE Press, 1982.
[2] C. Blundo, A. De Bonis, e B. Masucci, \Metering Schemes with Pricing", in Proceedings del 14th International Symposium on DIStributed Computing - DISC 2000, Toledo,
Spagna, 4 - 6 Ottobre 2000, M. Herlihy (Ed.), Lecture Notes in Computer Science, Vol.
1914, pp. 194{208, Springer Verlag, 2000.
[3] C. Blundo, A. De Bonis, e B. Masucci, \A Computationally Secure Metering Scheme with
Pricing", in Proceedings del Workshop su Sistemi Distribuiti: Algoritmi, Architetture e
Linguaggi - WSDAAL 2000, Ischia, 18 - 20 Settembre 2000.
[4] C. Blundo, A. De Bonis, e B. Masucci, \Optimal Pricing on the Web", sottomesso per
pubblicazione, Maggio 2000.
[5] C. Blundo, A. De Bonis, B. Masucci, e D. R. Stinson, \Dynamic Multi{Threshold Metering
Schemes", in Proceedings del Seventh Annual Workshop on Selected Areas in Cryptogra-
21
[6]
[7]
[8]
[9]
[10]
[11]
[12]
[13]
[14]
[15]
[16]
[17]
[18]
[19]
phy - SAC 2000, Waterloo, Canada, 14 - 15 Agosto 2000, sara pubblicato in Lecture Notes
in Computer Science, 2001.
C. Blundo, A. De Santis, G. Di Crescenzo, A. Giorgio Gaggia, B. Masucci, e U. Vaccaro,
\Secret Sharing of Many Secrets", sottomesso per pubblicazione, 1999.
C. Blundo e B. Masucci, \A Note on the Randomness in Dynamic Threshold Schemes",
Journal of Computer Security, Vol. 7, No. 1, pp. 73{85, 1999.
C. Blundo e B. Masucci, \Randomness in Multi{Secret Sharing Schemes", Journal of
Universal Computer Science, Vol. 5, No. 7, pp. 367{389, 1999.
C. Blundo, B. Masucci, D.R. Stinson, e R. Wei, \Constructions and Bounds for Unconditionally Secure Commitment Schemes", Cryptology ePrint Archive: Report 2000/043 e
Technical Report CORR 2000-46, Centre for Applied Cryptographic Research, University of Waterloo. Sottomesso per pubblicazione, Novembre 2000.
I. Damgard, J. Kilian e L. Salvail, \On the (Im)possibility of Basing Oblivious Transfer
and Bit Commitment on Weakened Security Assumptions", in Proceedings di Crypto '99,
Lecture Notes in Computer Science, Vol. 1592, pp. 56{73, 1999.
A. De Bonis e B. Masucci, \An Information Theoretical Approach to Metering Schemes",
in Proceedings di 2000 IEEE International Symposium on Information Theory - ISIT 2000,
Sorrento, Italia, 25 - 30 Giugno 2000.
A. De Santis e B. Masucci, \Multiple Ramp Schemes", IEEE Transactions on Information
Theory, Vol. 45, No. 5, pp. 1720{1728, 1999.
A. De Santis e B. Masucci, \On Secret Set Schemes", Information Processing Letter, Vol.
74, Issue 5-6, pp. 243{251, 2000.
A. De Santis e B. Masucci, \A Lower Bound on the Encoding Length in Lossy Transmission", Information Sciences, No. 116, pp. 129{146, 1999.
B. Masucci e D. R. Stinson, \Metering Schemes for General Access Structures", in Proceedings del 6th European Symposium on Research in Computer Security - ESORICS
2000, Toulouse, Francia, 4 - 6 Ottobre 2000, F. Cuppens, Y. Deswarte, D. Gollmann,
M.Waidner (Eds.), Lecture Notes in Computer Science, Vol. 1895, pp. 72{87, Springer
Verlag, 2000.
M. K. Franklin and D. Malkhi, \Auditable Metering with Lightweight Security", Financial
Cryptography '97, 1997.
B. Masucci e D. R. Stinson, \Ecient Metering Schemes with Pricing", sottomesso per
pubblicazione, Gennaio 2000. Technical Report CORR 2000-06, Centre for Applied
Cryptographic Research, University of Waterloo.
M. Naor and B. Pinkas, Secure and Ecient Metering, in \Advances in Cryptology - EUROCRYPT '98", Lecture Notes in Computer Science, Vol. 1403, Springer-Verlag, Berlin,
pp. 576{590, 1998.
R.L. Rivest, \Unconditionally Secure Commitment and Oblivious Transfer Schemes using
Concealing Channels and a Trusted Initializer", preprint.
22