Dottorato di Ricerca in Informatica, XII Ciclo,
Universita degli Studi di Salerno
Relazione
sull'attivita e le ricerche svolte durante il Dottorato
Dr.ssa Annalisa De Bonis
Corsi
La dottoressa Annalisa De Bonis ha frequentato i seguenti corsi:
Corso : Design and Analysis of Data Structures and Algorithm s II
Docente : Prof. Michael L. Fredman.
Durata : 40 ore.
Periodo : dal 29 Gennaio 1997 al 5 Maggio 1997.
Luogo : Rutgers University, NJ, USA.
Modalita esami : esercizi da svolgere assegnati con cadenza settimanale e test di meta
semestre e di ne semestre.
Superamento Esame : Avvenuto.
Corso : Computational Geometry.
Docente : Prof.ssa Diane Souvaine.
Durata : 40 ore.
Periodo : dal 29 Gennaio 1997 al 5 Maggio 1997.
Luogo : Rutgers University, NJ, USA.
Modalita esami : esercizi da svolgere assegnati con cadenza bisettimanale e test di meta
semestre e di ne semestre.
Superamento Esame : Avvenuto.
Corso : Semantica Operazionale e Denotazionale dei linguagg i di programmazione.
Docente : Prof. Rocco De Nicola (Universita di Firenze).
Durata : 20 ore.
Periodo : dal 6 al 15 Ottobre 1997.
Luogo : Universita di Salerno.
Modalita esami : esercizi da svolgere
Superamento Esame : Avvenuto.
Corso : Combinatorica per Informatici.
Docenti : Prof. U. Vaccaro (Universita di Salerno).
1
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.
Corso : Logica Fuzzy e Polivalente.
Docente : Pro. A. Di Nola e G. Gerla (Universita di Salerno).
Durata : 20 ore (in corso di svolgimento).
Periodo : dal 20 Ottobre 1998.
Luogo : Universita di Salerno.
Corso : Self-Stabilization.
Docenti : Prof. S. Dolev (Ben Gurion, Israel).
Durata : 6 ore.
Periodo : Dal 21 al 27 Giugno 1999.
Luogo : Scuola di Siena \Advanced Distributed Computing".
Corso : Cryptographic Protocols.
Docenti : Dr. C. Dwork (IBM Almaden, USA).
Durata : 6 ore.
Periodo : Dal 21 al 27 Giugno 1999.
Luogo : Scuola di Siena \Advanced Distributed Computing".
Modalita esame : Esercizi da svolgere.
Superamento esame : Avvenuto.
Corso : Locality Sensitive Distributed Computing.
Docenti : Prof. D. Peleg (Weizmann Institute, Israel).
Durata : 6 ore.
Periodo : Dal 21 al 27 Giugno 1999.
2
Luogo : Scuola di Siena \Advanced Distributed Computing".
Modalita esame : Esercizi da svolgere.
Superamento esame : Avvenuto.
Corso : Timed Distributed Computations.
Docenti : Prof. N. Santoro (Carleton University, Canada)
Durata : 6 ore.
Periodo : Dal 21 al 27 Giugno 1999.
Luogo : Scuola di Siena \Advanced Distributed Computing".
Modalita esame : Esercizi da svolgere.
Superamento esame : Avvenuto.
Corso : Topics in Theoretical Computer Science
Docenti : Prof. G. Persiano (Universita di Salerno)
Durata : 20 ore
Periodo : Marzo 2000
Luogo : Universita di Salerno
Corso : Public-Key Infrastructures.
Docenti : Prof. S. Micali and Prof. R. Rivest.
Durata : 8.5 ore.
Periodo : Dal 9 al 22 Luglio 2000.
Luogo : Scuola di Lipari \E-Commerce and On-Line Algorithms".
Corso : Payment Systems.
Docenti : Prof. M. Bellare.
Durata : 4.5 ore.
Periodo : Dal 9 al 22 Luglio 2000.
Luogo : Scuola di Lipari \E-Commerce and On-Line Algorithms".
Corso : E-commerce Primitives.
Docenti : Prof. T. Rabin and Prof. M. Yung.
Durata : 9 ore.
Periodo : Dal 9 al 22 Luglio 2000.
Luogo : Scuola di Lipari \E-Commerce and On-Line Algorithms".
Modalita esame : Esercizi da svolgere.
Superamento esame : Avvenuto.
3
Corso : On-Line Scheduling and Trading.
Docenti : Prof. A. Borodin.
Durata : 7.5 ore.
Periodo : Dal 9 al 22 Luglio 2000.
Luogo : Scuola di Lipari \E-Commerce and On-Line Algorithms".
Corso : On-Line Learning and Prediction.
Docenti : Prof. A. Blum.
Durata : 7.5 ore.
Periodo : Dal 9 al 22 Luglio 2000.
Luogo : Scuola di Lipari \E-Commerce and On-Line Algorithms".
Modalita esame : Esercizi da svolgere.
Superamento esame : Avvenuto.
Corso : On-Line Routing and Search.
Docenti : Prof. J. Kleinberg.
Durata : 7.5 ore.
Periodo : Dal 9 al 22 Luglio 2000.
Luogo : Scuola di Lipari \E-Commerce and On-Line Algorithms".
Seminari
La dottoressa Annalisa De Bonis ha partecipato ai seguenti seminari:
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.
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).
4
A 2-Approximation Algorithm for the Directed Multiway Cut Problem [J. S. Naor e L.
Zosin, FOCS '97]
Seminario tenuto il 27 Maggio 1998, presso l'Universita di Salerno, dalla dott.ssa Barbara
Masucci, Universita di Salerno
Succint Representation of Balanced Parantheses, Static Trees and Plan ar 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,
FOCS '96].
Seminario tenuto il 27 Maggio 1998, presso l'Universita di Salerno, dal dott. Paolo D'Arco,
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, num. 130, 1994].
Seminario tenuto il 17 Giugno 1998, presso l'Universita di Salerno, dal dott. Gianluca De
Marco, Universita di Salerno
Determining the Majority.
Seminario tenuto il 2 Novembre 1998, presso l'Universita di Salerno dal Prof. Martin
Aigner, Universita di Berlino
Fifth International Summer School on Distributed Computing:
Advanced Distributed Computting
tenutasi a Siena dal 21 al 27 Giugno 1999.
Nonlinear Pseudorandom Number Generators.
Seminarion tenuto il 19 Gennaio 2000 presso l'Universita di Salerno, dal Dr. Igor Shparlinsky, Department of Computing, Macquarie University, Australia.
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.
Convegni e Workshop
La dottoressa Annalisa De Bonis ha partecipato ai seguenti convegni:
5
Compression and Complexity of Sequences 1997.
Workshop tenutosi a Positano (SA) dal 11 al 13 giugno 1997.
The Fifth International Colloquium on Structural Information and Communication Complexity, SIROCCO '98.
Convegno tenutosi dal 22 al 24 Giugno 1998 ad Amal (SA)
The Fourth Annual International Computing and Combinatorics Conference, COCOON'98,
tenutosi dal 12 al 14 Agosto 1998 a Taipei, Taiwan, R.o.C.
The Sixth Italian Conference on Theoretical Computer Science, ICTCS'98, tenutosi dal 9
all'11 Novembre 1998 a Prato
Secure Communication Networks [SCN99]
tenutosi ad Amal il 16 e 17 Settembre 1999, organizzato dall'Univesrita di Salerno.
Workshop on Cryptography and Computational Number Theory [CCNT99]
tenutosi dal 22 al 26 Novembre 1999 a Singapore.
17th International Symposium on Theoretical Aspects of Computer Science, STACS 2000
[STACS 2000]
tenutosi dal 17 al 19 Febbraio a Lille, Francia.
2000 IEEE International Symposium on Information Theory, [ISIT 2000]
tenutosi dal 25 al 30 Giugno 2000 a Sorrento, Italia.
Workshop su Sistemi Distribuiti: Algoritmi, Architetture e Linguaggi, [WSDAAL 2000]
tenutosi dal 18 al 20 Settembre 2000 ad Ischia, Italia.
14th International Symposium on DIStributed Computing, [DISC 2000]
tenutosi dal 4 al 6 Ottobre 2000 a Toledo, Spagna.
Attivita di ricerca
La dottoressa Annalisa De Bonis ha svolto la sua attivita di ricerca nelle seguenti aree:
Algoritmi Combinatoriali di Ricerca
Crittograa e Sicurezza Dati
Algoritmi Combinatoriali di Ricerca
Rientrano in tale area i lavori [3, 11, 12, 13, 14, 10]. Nei lavori [12, 14] viene considerata una
generalizzazione del classico problema della moneta contraatta che consiste nell'individuare
all'interno di un insieme di n monete quella con peso inferiore al peso di tutte le altre. La
maggior parte dei lavori presentati in letteratura considerano il problema nel caso in cui il
dispositivo di ricerca consiste di una bilancia a due piatti con cui ogni volta si confrontano i
pesi di due sottoinsiemi di monete aventi uguale cardinalita. Nel modello da noi considerato il
dispositivo di ricerca e rappresentato da una bilancia che consente il confronto in parallelo dei
6
pesi di r (r 2) sottoinsiemi di monete. Gli articoli arontano lo studio del costo medio di
ricerca nel caso di distribuzione di probabilita uniforme sulle monete. In [14] viene individuato
un algoritmo adattivo ottimale per questo caso. Un algoritmo adattivo e un algoritmo in cui, ad
ogni passo, la scelta dei sottoinsiemi da pesare dipende dai risultati ottenuti ai passi precedenti.
In [12] viene invece individuata una soluzione mediante algoritmi non adattivi, ovvero algoritmi
in cui la sequenza delle pesate deve essere stabilita a priori e non puo in nessun modo dipendere
dai risultati delle pesate stesse. L'algoritmo presentato risulta essere ottimale per la maggior
parte dei valori input di n. Per i rimanenti valori di n, l'algoritmo utilizza un numero di test
molto vicino all'ottimo.
I lavori [3, 10, 11, 13] arontano e risolvono problemi di ricerca combinatoriale originatisi
nell'ambito della chimica e della biologia molecolare per il quale sono state proposte tecniche
particolari di group testing. Il classico problema del group testing consiste nel determinare
tutti i membri positivi di un insieme S di oggetti. A questo scopo, vengono eettuati test su
sottoinsiemi di S: Un test da esito negativo se il campione testato contiene almeno un elemento
positivo ed esito negativo in caso contrario. Nella pratica pero possono vericarsi situazioni piu
complesse. La prima applicazione del group testing e per lo screening di librerie di cloni con
prove di ibridizzazione. Motivati da problemi che attengono al mondo della biologia molecolare,
Farach et al. hanno introdotto un'interessante variazione del problema del group testing, dove,
in aggiunta alla categoria dei campioni positivi e a quella dei campioni negativi, vi e una terza
classe di campioni detti inibitori. In questo modello, che noi chiamiamo Group Testing con
Inibitori, un pool risulta positivo al test se e solo se contiene uno o piu campioni positivi e
non contiene alcun elemento inibitore. Tipicamente, gli inibitori corrispondono a impurita o
a campioni deteriorati che interferiscono con il test rendendo il risultato privo di signicato.
L'obiettivo consiste nell'individuare l'insieme dei campioni positivi usando il minor numero di
test. Farach et al. hanno presentato un lower bound al numero di test per questo problema e
fornito un algoritmo randomizzato che ottiene questo lower bound. In [11] abbiamo migliorato il
lower bound di Farach et al. nel caso in cui il numero di inibitori e almeno il doppio del numero
di campioni positivi. Nello stesso lavoro abbiamo anche fornito algoritmi deterministici ecienti
per il problema.
In [3, 10] viene considerata un'interessante generalizzazione del problema del group testing
introdotta recentemente da Damaschke. Nel modello di ricerca proposto da Damaschke l'input
consiste di un insieme di campioni di acqua, alcuni dei quali possono essere contaminati con
una certa sostanza chimica (tossica). L'obiettivo della ricerca e di individuare i campioni in
cui la concentrazione della sostanza contaminante e al di sopra di un certo valore. Per risolvere
questo problema si rende necessario poter stimare la concentrazione della sostanza contaminante
all'interno di un singolo campione. Il dispositivo usato per eettuare i test consiste di un indicatore a soglia che da responso positivo solo se la concentrazione del campione testato e maggiore o
uguale della soglia. I campioni testati sono ottenuti a partire dal campione originario mediante
opportune operazioni di diluzione o, una volta ottenuti campioni con diverse concentrazioni,
mischiando tra loro campioni diversi. Il costo di una strategia di ricerca per questo problema
e valutato in termini del numero di test, di operazioni di diluzione e di miscelaggio, e di unita
di acqua utilizzate nelle operazioni di diluzione. Damaschke ha dimostrato che il modello di
ricerca descritto puo essere visto come una particolare generalizzazione del problema del group
testing. Comunque, l'obiettivo principale del lavoro di Damaschke e di studiare il problema pre7
liminare di approssimare la concentrazione della sostanza contaminante all'interno di un dato
campione. La strategia di Damaschke funziona nell'ipotesi semplicativa che un campione possa
essere utilizzato per piu di un test (modello conservativo). In [3, 10] procediamo lungo la linea
di ricerca introdotta da Damascke, proponendo un algoritmo che utilizza un numero di test
inferiore a quello utilizzato dall'algoritmo proposto da Damaschke. Viene inoltre presentata una
famiglia di algoritmi, ognuno dei quali fornisce un diverso compromesso tra l'uso delle diverse
risorse coinvolte nel processo di ricerca. In [3, 10] viene anche considerato un modello di ricerca
piu realistico rispetto a quello di Damaschke, in cui il dispositivo di ricerca altera il campione
testato che non puo quindi essere riutilizzato. La soluzione del problema in questo modello
implica ovviamente l'uso di un maggior numero di unita di acqua e di operazioni di diluzione e
miscellaggio. Per questo modello di ricerca vengono presentati risultati analoghi a quelli ottenuti
per il modello conservativo.
Crittograa e Sicurezza Dati
Rientrano in tale area i lavori [1, 4, 5, 6, 7, 8, 9, 15, 16]. Nei lavori [1, 6, 8, 9, 15, 16]
vengono arontate delle questioni aperte relative agli schemi di crittograa visuale. Gli schemi
di crittograa visuale sono schemi per la condivisione di un'immagine segreta tra n partecipanti.
L'immagine viene codicata in n immagini ciascuna delle quali viene data ad un partecipante.
Gruppi qualicati di partecipanti possono recuperare l'immagine segreta mentre gruppi non
qualicati non hanno alcuna informazione sull'immagine codicata. Le immagini date ad un
gruppo di participanti vengono copiate su trasparenze. Se il gruppo e qualicato allora i suoi
partecipanti possono recuperare l'immagine semplicemente sovrapponendo le trasparenze ad essi
assegnate.
I lavori [1, 6] sono particolarmente incentrati sull'analisi della cosiddetta pixel expansion,
ovvero del numero di sottopixel necessari per codicare ciascun pixel dell'imagine originaria, che
e uno dei parametri maggiormente caratterizzanti uno schema di crittograa visuale. Nei lavori
[1, 6] vengono considerati schemi di crittograa visuale in cui i gruppi qualicati sono tutti quelli
di dimensione maggiore o uguale ad un certo intero ssato k. Uno schema di questo tipo e detto
schema di crittograa visuale a soglia (k; n): Nei lavori [1, 6] forniamo schemi a soglia, sia per
immagini in bianco e nero che per immagini a colori. Gli schemi per immagini bianche e nero
presentati in questi lavori vericano una particolare proprieta che assicura un'elevata qualita
dell'immagine ricostruita. I nostri schemi hanno pixel expansion inferiore a quella di tutti i
precedenti schemi che vericano questa proprieta. Nei lavori [1, 6] forniamo inoltre schemi a
soglia a colori (2; n) e (n; n) aventi pixel expansion migliore di quelli presentati precedentemente
in letteratura.
Nel seguito si fara riferimento esclusivamente a schemi di crittograa visuale per immagini
in bianco e nero.
Nei lavori [8, 9, 15, 16] arontiamo l'analisi della randomness degli schemi di crittograa
visuale ovvero del numero di random bit di cui occorre disporre per condividere un'immagine segreta tra n partecipanti. Il concetto di randomness degli schemi di crittograa visuale
e stato introdotto per la prima volta in [8]. Tutti i precedenti lavori di crittograa visuale
riguardavano soprattutto lo studio della pixel expansion e del contrasto (il contrasto misura la
\dierenza" tra pixel bianchi e neri nell'immagine ricostruita ed e quindi indicativa della qualita
dell'immagine ottenuta sovrapponendo le immagini di un insieme qualicato di partecipanti). In
8
[8] presentiamo un lower bound sulla randomness degli schemi di crittograa visuale a soglia e
costruzioni a randomness minima per schemi di crittograa visuale a soglia (2; n) e (k; k): Viene
poi fornita una caratterizzazione completa degli schemi (k; k) aventi sia minima randomness
che minima pixel expansion. Nello stesso lavoro forniamo anche varie tecniche di costruzione
di schemi di crittograa visuale per strutture di accesso generali, ovvero schemi in cui i gruppi
di partecipanti autorizzati a ricostruire l'immagine segreta non sono necessariamente tutti i
sottoinsiemi di partecipanti di dimensione k; ma possono essere sottoinsiemi qualsiasi degli n
partecipanti.
Nel lavoro [9] viene presentato una nuova tecnica per la determinazione di lower bound per
schemi di crittograa visuale per strutture di accesso generali e viene presentata una caratterizzazione degli schemi (k; k) a randomness minima vericanti una proprieta piu debole di quella
di minima pixel expansion.
Nel lavoro [15] viene eettuato uno studio delle relazioni esistenti tra schemi di crittograa
visuale e schemi per la condivisione di un segreto binario. Viene fornita una tecnica per trasformare qualsiasi schema per la condivisione di un segreto binario in uno schema di crittograa
visuale avente la stessa randomness dello schema di partenza. Questa tecnica ha anche consentito di costruire schemi a soglia (k; n) la cui randomness e molto vicina al lower bound stabilito
in [8].
Esistono forti connessioni tra crittograa visuale e combinatorica. Note strutture combinatoriali sottendono alla costruzione di molti schemi di crittograa visuale. Ad esempio, particolari
famiglie di Sperner sono alla base della costruzione sia di schemi di crittograa visuale a soglia
(2; n) ottimali rispetto alla pixel expansion che di schemi di crittograa visuale a soglia (2; n)
ottimali rispetto alla randomness. Un altro esempio e dato dalle matrici di Hadamard che sono
alla base della costruzione di schemi di crittograa visuale a soglia (2; n) ottimali sia rispetto
alla pixel expansion che al contrasto. Su tecniche tipicamente combinatoriali e anche basata la
derivazione dei limiti inferiori per la pixel expansion, la randomness e il contrasto degli schemi
di crittograa visuali.
Nei lavori [2, 4, 5, 7] viene studiato il problema del monitoraggio delle interazioni tra un
gruppo di server e di client. Lo scenario considerato consiste di un numero molto grande di server
e di client, e di un'agenzia di controllo il cui compito e di tenere il conto del numero di client che
visitano ciascun server. L'agenzia deve impedire che i server \gonno" il numero di visite ricevute
da ciascuno di essi. Naor e Pinkas hanno introdotto i metering scheme come sistema di protezione
contro i tentativi di imbroglio da parte dei server. Un uso dei metering scheme e per applicazioni
nell'ambito della pubblicita su rete che rappresenta una delle maggiori fonti di guadagno per
i siti web. Le somme richieste da un sito web per ospitare i messaggi pubblicitari dipendono
dal numero di client che visitano abitualmente il sito. Le agenzie pubblicitarie misurano la
popolarita dei siti web eettuando statistiche relative all'uso dei siti web. Per questo motivo, le
agenzie pubblicitarie dovrebbero essere in grado di impedire ai server (siti web) di imbrogliare sul
numero delle visite ricevute allo scopo di chiedere pagamenti piu elevati. Naor e Shamir hanno
presentato metering scheme che sono sicuri contro tentativi da parte dei server di imbrogliare
sul numero di visite ricevute. Nel modello considerato da Naor e Pinkas, un server viene pagato
dall'agenzia pubblicitaria solo se e in grado di dimostrare che e stato visitato almeno da un
certo numero h di client. In [5] e stata considerata una particolare generalizzazione di questo
9
modello che consente di stabilire con esattezza il numero di visite ricevute da ciascun server.
In questo modello ciascun server riceve un compenso diverso che dipende dal numero di visite
ricevute, diversamente a quanto succede nel modello di Naor e Pinkas in cui ciascun server
visitato da un numero di client maggiore o uguale di h riceve lo stesso compenso. I metering
scheme 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 essi
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. Per questo
motivo, il nostro studio si e concentrato sulla dimensione dell'informazione distribuita ai server
e ai client. Sono stati derivati lower bound sia sulla dimensione dell'informazione distribuita
ai server che su quella dell'informazione distribuita ai client ed e stato fornito uno schema che
ottiene questi lower bound.
In [4] viene considerata un'ulteriore generalizzazione del modello introdotto da Naor e Pinkas.
Questo nuovo modello associa a ciascun server una soglia distinta che varia dinamicamente nel
tempo. In ciascun intervallo di tempo l'agenzia paga un server S se e solo se in quell'intervallo
di tempo S e stato visitato da un numero di client maggiore o uguale del valore dalla soglia a lui
assegnata in quell'intervallo di tempo. Anche in questo caso sono stati derivati lower bound sulla
dimensione dell'informazione distribuita ai client dall'agenzia e dell'informazione distribuita ai
server dai client ed e stato fornito uno schema che ottiene questi lower bound.
Come gia detto, i metering scheme richiedono che una certa quantita di informazione venga
distribuita ai client e ai server. Data l'alta complessita di questo meccanismo di distribuzione
dell'informazione, risulta naturale considerare la possibilita di ottenere compromessi tra sicurezza dello schema e dimensione dell'informazione distribuita ai server e ai client. In [7] e
stata considerata questa possibilita ed e stato messo a punto uno schema in grado di ottenere
diversi tradeo tra sicurezza e complessita dell'informazione. Il nostro schema utilizza la quantita minima di informazione necessaria per garantire il livello di sicurezza pressato.
Bibliograa
[1] C. Blundo, A. De Bonis, e A. De Santis, \Improved schemes for visual cryptography",
sara pubblicato su Design, Codes, and Cryptography
[2] 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.
[3] A. De Bonis, L. Gargano, e U. Vaccaro, \Ecient Algorithms for Chemical Threshold
Testing Problems", accettato per pubblicazione su Theoretical Computer Science (Elsevier
Science, Amsterdam, Olanda)
[4] C. Blundo, A. De Bonis, B. Masucci, e D. R. Stinson, \Dynamic Multi-Threshold Metering
Schemes", sara pubblicato in Proceedings of SAC 2000
[5] C. Blundo, A. De Bonis, e B. Masucci, \Metering Schemes with Pricing", in Proceedings
of DISC 2000, 194{208
10
[6] C. Blundo e A. De Bonis, \New Constructions for Visual Cryptography", pubblicato in
Proceedings of The Sixth Italian Conference on Theoretical Computer Science, ICTCS '98,
Prato, Italia, Novembre 1998, P. Degano, U. Vaccaro, e G. Pirillo (Eds.), (World Scientic,
Singapore), (1998) 290{303
[7] A. De Bonis e B. Masucci, \An Information Theoretical Approach to Metering Schemes",
sara pubblicato in Proceedings of 2000 IEEE International Symposium on Information
Theory, Sorrento, Italia, 25 { 30 Giugno 2000
[8] A. De Bonis e A. De Santis, \Randomness in Visual Cryptography", pubblicato in Proceedings of 17th International Symposium on Theoretical Aspects of Computer Science,
STACS 2000, Lille, France, 17{19 Febbraio 2000, Horst Reichel e Sophie Tison (Eds.),
Lectures Notes in Computer Science (Springer{Verlag, Berlino, Germania), vol. 1770,
(2000) 626{638
[9] A. De Bonis e A. De Santis, \New Results on the Randomness of Visual Cryptography
Schemes", sara pubblicato in Proceedings of Workshop on Cryptography and Computational Number Theory, CCNT'99, Singapore, 22{26 Novembre 1999
[10] A. De Bonis, L. Gargano e U. Vaccaro, \Improved Algorithms for Chemical Threshold
Testing Problems", pubblicato in Proceedings of The Fourth Annual International Computing and Combinatorics Conference, COCOON'98, Taipei, Taiwan, R.o.C. Agosto 1998,
Wen{Lian Hsu and Ming{Yang Kao (Eds.), Lectures Notes in Computer Science (Springer{
Verlag, Berlino, Germania), vol. 1449, (1998), 127{136
[11] A. De Bonis e U. Vaccaro, \Improved Algorithms for Group Testing with
Inhibitors", Information Processing Letters, (Elsevier Science, Amsterdam, Olanda), vol.
67, (1998), 57-64
[12] A. De Bonis, \A Predetermined Algorithm for Detecting a Counterfeit Coin with MultiArms Balances" Discrete Applied Mathematics (Elsevier Science, Amsterdam, Olanda),
vol. 86, (1998), 181-200
[13] A. De Bonis, L. Gargano, e U. Vaccaro, \Group Testing with Unreliable Tests" - Information Sciences, (Elsevier Science, New York, U.S.A.), vol. 96, Issue 1-2, (1997), 1{14
[14] A. De Bonis, L. Gargano, e U. Vaccaro, \Optimal Detection of a Counterfeit Coin
with Multi-Arms Balances", Discrete Applied Mathematics (Elsevier Science, Amsterdam,
Olanda), vol. 61, (1995), 121{131
[15] A. De Bonis e A. De Santis, \Secret Sharing and Visual Cryptography Schemes (A Randomness Preserving Transformation)", sottomesso per pubblicazione
[16] A. De Bonis e A. De Santis, \On the Randomness in Visual Cryptography"
Data, 15 Novembre 2000
11