1.1 Un primo approccio: lo schema a soglia (2,2)

In questa prima parte ci occuperemo di immagini composte solo da pixel bianchi e pixel neri, dove, nei lucidi, il bianco sarà inteso come trasparente.

Una soluzione naive al problema, per uno schema a soglia (2,2), potrebbe essere la seguente:

• un pixel bianco dell'immagine originale viene codificato con un pixel bianco in entrambe le share;
• un pixel nero dell'immagine originale viene codificato con un pixel bianco in una share ed uno nero nell'altra.

Figura 2 - Approccio naive per uno schema a soglia (2,2)

Si noti che, con tale soluzione, un pixel bianco può essere codificato in un unico modo, mentre per un pixel nero le possibili codifiche sono due: la scelta di quale codifica usare per i pixel neri è, per ogni pixel, casuale.

La soluzione descritta, però, dà origine ad uno schema non sicuro, in quanto su ognuna delle due share sono presenti sufficienti informazioni per recuperare gran parte dell'immagine originale. Infatti si osservi che un gruppo di pixel bianchi nell'immagine originale viene codificato con un gruppo di pixel bianchi nelle due share, mentre un gruppo di pixel neri viene codificato con un gruppo di pixel eterogenei, in quanto il bianco e il nero sono equamente distribuiti.

Figura 3 - Esempio di applicazione della soluzione naive

Una soluzione sicura è data dallo schema, proposto da Naor e Shamir [8], in cui un pixel p viene rappresentato, nella sua versione codificata, da due sottopixel:

• se p è bianco, la coppia di sottopixel usata nella codifica è uguale per le due share, in modo da ottenere, dalla sovrapposizione, una coppia in cui un sottopixel è bianco e l'altro è nero;
• se p è nero, la coppia di sottopixel utilizzata in una share è complementare a quella utilizzata nell'altra share, in modo che la sovrapposizione generi una coppia formata da due sottopixel neri.

Figura 4 - Schema a soglia (2,2)

In tal caso, un qualsiasi pixel (bianco o nero che sia) può essere codificato in due modi diversi: la scelta di quale codifica usare è, per ogni pixel, casuale.

La soluzione appena descritta è un caso particolare del più generico schema di crittografia visuale (VCS, Visual Cryptography Scheme) che rappresenta un pixel p con m sottopixel. Il parametro m viene detto espansione del pixel.

La sicurezza di questo schema è dovuta al fatto che, osservando una coppia di sottopixel in una share, non è possibile risalire al colore del corrispondente pixel nell'immagine originale.

Infatti tale coppia sarà costituita da un sottopixel bianco ed un sottopixel nero, indipendentemente dal colore del pixel originale.

Si noti che la rappresentazione di un pixel con due sottopixel dà luogo ad un'immagine di dimensione doppia (in altezza o in larghezza) rispetto all'immagine originale, il che corrisponde ad una deformazione dell'immagine stessa.

Figura 5 - Applicazione di uno schema a soglia con m=2

Oltre alla deformazione dell'immagine, tale tecnica comporta anche una perdita di contrasto, poiché un pixel nero verrà rappresentato da due sottopixel neri, ma un pixel bianco verrà rappresentato da un sottopixel bianco ed uno nero (la vicinanza dei due sottopixel appare, all'occhio umano, come una sorta di grigio).

In un VCS il contrasto dell'immagine ricostruita dalla sovrapposizione delle share è indicato dal parametro . Nell'esempio descritto in Figura 4 (riproposto in Figura 6) il valore del pixel nero è 1 (in quanto tutti i sottopixel sono neri), mentre il valore del pixel bianco è ½ (in quanto la metà dei sottopixel è nera). Il parametro è, quindi, uguale ad 1 - ½ = ½.

La perdita di contrasto dell'immagine ricostruita rispetto all'originale è indicata dal valore 1-; il VCS ottimale dovrebbe massimizzare per ridurre al minimo la perdita di contrasto.

Figura 6 - Contrasto nello schema (2,2)

Si mostra un ulteriore esempio di schema a soglia (2,2) che differisce dal precedente per il valore di m, che in questo caso è uguale a 4.

Figura 7 - Schema a soglia (2,2) con m=4

In Figura 7 sono mostrate tutte le possibili codifiche per i pixel bianchi e neri.

Tale soluzione può essere utile per mantenere le proporzioni dell'immagine originale, benché l'immagine ricostruita risulti quattro volte più grande. Come si può notare dalla Figura 7, sovrapponendo i pixel delle due share otteniamo, per un pixel nero, 4 sottopixel neri, mentre per un pixel bianco, 2 sottopixel neri e 2 sottopixel bianchi.
Anche in tal caso il contrasto è ½, come pure la perdita di contrasto.

Riepilogando, i principali parametri di un VCS sono:

• m, espansione del pixel. Si desidera minimizzare questo parametro per ridurre lo spazio occupato dall'immagine;
• , contrasto nell'immagine ricostruita. Si desidera massimizzare questo parametro per ridurre al minimo la perdita di contrasto (1-). Il valore teorico massimo di questo parametro è 1, benché Naor e Shamir [8] abbiano dimostrato che uno schema funzionante ha un contrasto massimo pari a ½. Lo schema a soglia (2,2) ha, quindi, un contrasto ottimale.