COMPARTICIÓN DE SECRETOS EN CRIPTOGRAFÍA
Jo ge Villa San o
s,
Ca
I
es Pad ó Laimón y Ge mán Sáez Mo eno
P o eso es de/ Dp o. de Ma emá ica Aplicada y Telemá ica.
Uni e si a Po/i ecnica de Ca a/unya
e-mail:[email p o ec ed]
En la c ip og a
í
a clásica, an o en el ámbi o de cla e
púb
li
ca
co
mo en el de cl
a e
p i ada, los p o
oco
los
c ip og
á
i
cos
cuen an
só
lo
co
n dos pa icipan es: el po-
seedo de la
in
o mación o
i
ginal y el
ece
p o de dicha
in o mación.
En la ac ualidad,
co
n el d
esa
o
ll
o de las ed
es
in o
má
i
cas
y la n
eces
idad de
seg
u idad y p i
ac
idad
esp
ec
o a la
in
o mación que
és
as c
u
sa
n,
se
e
qui
e e
el u
so
de
p o
oco
l
os
qu
e in
o
luc
en un
núm
e o m
ayo
de pa icipan
es
[D
es88
]. Un ejemplo
se
ncillo es la
ea
lización de
una
co
n
e encia a
es
en la
qu
e se
equie a p i
ac
idad.
Po o a pa e, la in o mación sec e a no es gene ada
exclusi amen e
po
pe sonas ísicas sino
po
e
mp
esas o
en idades. En es e úl imo caso, no es á cla o que la
e
spon-
sabilidad
so
b
e la
in
o mación s
ec
e a gene ada pueda o
de
ba
ecae
so
b e una úni
ca
pe
so
na. Po ejemplo, cual-
q
ui
e mo imien o
imp
o an e de
ca
pi al en una e
mp
esa
debe ía eque i la pa icipación de a ios empl
ea
dos.
1.
ESQUEMAS PARA COMPARTIR
SECRETOS
U n
es
quema pa a compa
i
sec e os
es
un p o
oco
lo
c
ip
og
á
i
co
en el que, como su no
mb
e indica. se di ide
un
de
e minado sec e o en
ag
men os que se epa en
en e los pa icipa
n
es. Po ejemplo, el sec e o po
d
ía se
la
cla e
de
acceso
a una cuen a ban
ca
i
a.
Es e epa o de
in
o mación se
ea
li
za de modo que:
(1) sólo cie os
co
njun os de pa
i
cipa
n
es
au o iza-
dos pu
ede
n
eco
ns ui el sec e o o
i
g
in
a
l.
(2) un conjun o de pa
i
cipan
es
no au
o
izado no
puede ob ene in o mación alguna so
b
e el sec e o o igi-
nal.
De la segun
da
condición
se
desp en
de
que
el sec e-
o no
se
di ide li e almen e en agmen os sino que los
agme
n
os en
ega
dos a
ca
da pa icipan e
es
ul an de la
ejecución de un al
go
i mo más so is
i
cado.
Asimismo
, la
econs
u
cc
ión
de
l sec e o no
cons
is
i
á en la yux aposi-
ción de los agmen os de lo pa icipan es sino en la
ejecución de cie o algo i mo cu
yas
en adas sean los
agme
n
os an e
i
o es.
..
R
AMAS
DE
E
STU
DI
ANTES
DEL
I
EEE
Los p ime os esquemas
pa
a
co
mpa i sec e os
u
e on in oducidos en 1979 po
Sh
a
mi
en [Sha79] y po
Bl
ac
kl
ey en [
Bl
a79].
El
p ime o de e
ll
os
es
á
ba
sado en
in e polación polinómi
ca
sob e un cue po ini o. Dado un
sec e o k, e oma un polino
mi
o sec e o p de g ado no
supe io a
-
J, al
que
p O) = k. A c
ada
uno
de
los n
Un
p o ocolo debe se
ob
us o an o en e a
pe sonas ex e nas al mismo
como en e a usos ilíci os
de la in o mación
epa ida
pa ici pan es, que se
ca
a
c
e iza po cie o núme o
~
,
""
O,
se
le asigna el
ag
men o
S¡ = p(
~
).
Se puede
demo
s a
que
si se eúne una
ca
n idad
igual o mayo que pa icipan es, exis e un único polinomio
p de g a
do
in
e
i
o a { que pa
se
po
los pun os
(
~
¡
,S)
co
es
pondien
es
a dichos pa icipan e
s.
Además, el se-
c e o o
i
ginal coincide con p
O).
Po o a pa e. dado un
co
njun o con menos de 1
pa icipan es, exis en
a
ios polinomios q que pasan po
los pun os (
~
,
.S)
co
es
pondien es a
di
chos pa icipan es
y q(O) oma odos los alo es posibl
es
con la mjsma
ecuencia. Así, odos los alo es posibl
es
del sec e o k
esul an e
quip
obables, y los pa
i
cipan
es
i
enen la
mi
sma
in
o mación so
b
e el sec e o que cualquie pe
so
na ajena
al p o ocolo.
Es e ipod
ees
quem
ase
n los que
seex
ige un núme o
mínimo de pa icipan
es
pa a
eco
ns ui el sec e o se
d
enom
inan esquemas de umb a
l.
Es os esquemas no son
los únicos exis e
n
es pe o
sí
los más ampliamen e
es
udia-
dos.
2.
ESQUEMAS ROB
US
TOS FRENTE
A MENTIROSOS
En el mundo de la c
i
p og a ía. un p o ocolo debe se
obus o an o en e a pe sonas ex e nas al
mi
smo
co
mo
e
n
e a usos
il
íc
i
os
de
la
in
o mación epa id
a_
53
Po ejemplo, un pa icipan e de un esquema pa a
compa i sec e os pod ía in en a engaña a o os sumi-
nis ando un agmen o inco ec o du an e el p oceso de
econs ucción. Si el esquema no cuen a con un algo i mo
de e i icación de los agmen os, se econs uye un
sec e o inco ec o. En el caso peo , con el agmen o
co ec o y el sec e o inco ec o, el pa icipan e amposo
pod ía ecupe a po sí mismo el sec e o o iginal. Es o es
exac amen e el incon enien e del esquema de Sha ni .
Un
pa icipan e
de
un esquema
pa a compa i sec e os pod ía
in en a engaña a o os
suminis ando un agmen o
inco ec o du an e el p oceso
de
econs ucción
Una mane a de do a de cie a obus ez al esquema
de Sha ni es además de epa i el sec e o o iginal
k,
epa i
po un p ocedimien o análogo su cuad ado F. Así, a cada
pa icipan e se le o o gan los agmen os
Si
y i co espon-
dien es espec i amen e a k
ya
F.
En el p oceso de econs ucción, se ecupe an am-
bos sec e os
k]
y k2• Si odos los pa icipan es son hon a-
dos, esul a
k]
= k Y k2 = k2• En caso con a io, con al a
p obabilidad sucede á que
k/
"" k2, Y los pa icipan es
deduci án que el sec e o
k]
econs uido no es álido. Po
o a pa e, un pa icipan e no puede (sal o casualidad
imp obable) modi ica sus agmen os S y
1.
de modo que
J J
se cumpla
la
elación
k]
2 = k2, sin conoce p e iamen e los
agmen os de
-1
pa icipan es más.
Es a mejo a del esquema de Shami ue in oducida
po Pad ó en [Pad96].
Exis en o os equisi os de obus ez más se e os
que el an e io que, po ejemplo, consiguen llega a iden-
i ica al pa icipan e amposo a pa i de los agmen os
suminis ados [Ca 95]. En gene al, cuan o más obus o es
un esquema pa a compa i sec e os, mayo esul a el
amaño de los agmen os epa idos a los pa icipan es. En
el esquema de Pad ó, el amaño de los agmen os es el
doble del amaño del sec e o. Se puede demos a que es e
amaño es casi el mínimo posible [Oga96].
Los esquemas pa a compa i sec e os pueden apa-
ece
como
un
componen e
de
o os
p o ocolos
c ip og á icos como la gene ación compa ida de i mas
digi ales o la e i icación compa ida de la au en icidad de
un documen o [Soe90, F a95]. En ambos casos se é i a
54
concen a oda la esponsabilidad de un ac o de e minado
en una única pe sona.
O a aplicación de los esquemas pa a compa i sec e-
os se halla en los sis emas de o ación elec ónica, en los que
la ape u a de la u na equie e la econs ucción de una cla e
sec e a compa ida en e los miemb os de la mesa elec o al.
3. SEGURIDAD COMPUTACIONAL
VS. INCONDICIONAL
Además de los esquemas pa a compa i sec e os
desc i os an e io men e y denominados incondicional-
men e segu os, exis e una e sión menos es ic a de los
mismos, denominados compu acionalmen e segu os.
Las exigencias de un esquema al son:
(1) sólo cie os conjun os de pa icipan es au o iza-
dos pueden econs ui el sec e o o iginal.
(2) un conjun o de pa icipan es no au o izado no
puede ob ene in o mación alguna sob e el sec e o o igi-
nal, usando los ecu sos compu acionales ac uales.
En es e ipo de esquemas se asume la exis encia de
una unción unidi eccional, es deci , calculable con
ela i a acilidad y cuya in e sa no se puede calcula a
pa i de los ecu sos compu acionales ac uales. Un ejem-
plo de unción unidi eccional es la exponenciación (x) =
E '
en un cue po ini o.
Po ejemplo, dado el agmen o
Si
en egado a cada
pa icipan e en un esquema incondicionalmen e segu o,
podemos publica
Si
=
(
S) sin e ela el alo conc e o de
si"
De es e modo, si un pa icipan e in en a da un agmen-
o also S*i' és e se ía inmedia amen e de ec ado dado que
Si
"" (s').
Los esquemas compu acionalmen e segu os son,
en gene al, más e sá iles que los incondicionalmen e
segu os dado que pe mi en añadi dinámicamen e pa ici-
pan es sin ene que modi ica los agmen os epa idos,
así como eu iliza los agmen os pa a compa i un segun-
do sec e o [Cac95, Gh097].
Pa a las mismas p es aciones, los agmen os de un
esquema compu acionalmen e segu o ienen meno ama-
ño que los agmen os de un esquema incondicionalmen e
segu o.
Po úl imo, la segu idad compu acional demues a
se su icien e pa a las aplicaciones p ác icas.
4.
CRIPTOGRAFIA VISUAL
Recien emen e se ha in oducido una gene alización
de los esquemas pa a compa i sec e os que se conoce
como c ip og a ía isual [Na094]. En es e caso, an o el
-"
,.
BÜI'."NN" ODICIE~ll i
1997
ji
:
sec e o compa ido como los agmen os que se en egan
a los pa icipan es son imágenes en blanco y neg o.
La
es icción que se in oduce es que en el p oceso de
econs ucción los agmen os se supe ponen como si
ue an anspa encias. Es deci , el esul ado de supe pone
dos imágenes es la «OR» lógica pun o a pun o
de
ambas,
conside ando el colo neg o (opaco) como «1» y el colo
blanco ( anspa en e) como
«O»
lógico.
Desde el pun o de is a de esquemas pa a compa i
sec e os, lo que se hace es descompone la imagen sec e a
en un conjun o de bi s, cada uno co espondien e a un pixel
de la imagen. Cada bi se epa e independien emen e de
los demás bi s de
la
imagen, de modo que los agmen os
ienen un amaño ijo de m bi s po pixel o iginal.
De
es e
modo, los agmen os equie en una esolución mayo que
la imagen sec e a o iginal.
La
econs ucción po supe posición de los ag-
men os no es exac a pe o el ojo humano es capaz de
dis ingui la imagen o iginal si es a no es excesi amen e
eca gada.
La
en aja de es e p o ocolo es que el algo i mo
de econs ucción no equie e ealiza cálculo alguno.
BIBLIOGRAFÍA
[Bei94] A.
BEIMEL
y B.
CROR
«ln e ac ion inkey dis ibu ion
schemes» Ad ances in C yp ology, C yp o '93
444-457 (1994)
[Bla79] G.R.
BLAKLEY
«Sa egua ding c yp og aphickeys»
AFIPS Con e ence P oceedings 48 313-317 (1979)
[Cac95] C.
CACHIN
y C.
BOYD
«On-line
sec e
sha ing»
C yp og aphy
and
Coding,
lMA
'96
190-198
(1995)
[Ca 95] M.
CARPEl l" IERJ
«A pe ec h eshold sec e sha ing
scheme o iden i y chea e s» Design, Codes and
C yp og aphy5183-187(1995)
[Des88] Y.
DESMEDT
«Socie y
and
g oup
o ien ed
c yp og aphy: A new concep » Ad ances·
in
C yp ology,C yp o '87120-127 (1988)
[F a95] M.K.
FRANKLlNY
M.K.
REITER«
Ve i iable signa u e
sha ing» Ad ances in C yp ology, EUROCRYPT
'9550-63 (1995)
[Gh097] H.
GRODOSI,
l
PIEPRZYK,
G.R.
CHAUDRRY
y l
SEBERRY
«How o p e en chea ing in Pinch's
scheme» Elec onics Le e s 33 (1997) 1453-1454
[Na094] M.
NAOR
y A.
SHAMIR
«Visual c yp og aphy»
Ad ances in C yp ology, EUROCRYPT
'941-12
(1994)
[Oga96] W.
OGATA
y
K.
KUROSAWA
«Op imum Sec e
Sha ing
Scheme
Secu e
agains
Chea ing»
Ad ances in C yp ology, EUROCRYPT
'96
200-
211(1996)
[Pad96]
C.
PADRÓ,
G.
SÁEZ
y
lL.
VILLAR
«De ec ion
o
chea e s in ec o space sec e sha ing schemes»
P oc.
o
he 1 s ln . Con . on he Theo y and Appl.
o C yp ology, PRAGOCRYPT'96 (1996) 359-369
[Sha79] A.
SHAMIR
«How o sha e a sec e » Commun.
o
heACM22612-613 (1979)
[Soe90] M.
DE
SOETE,
1.1.
QUISQUATER
y
K.
VEDDER
«A
signa u e
wi h
sha ed
e i ica ion
scheme»
Ad ancesinC yp ology,C yp o '89253-262 (1990)
VENTANA AL CAMPUS
Inaugu amos en es e núme o una sección en
la
cual a a emos emas elacionados con el Campus.
Os in i amos a colabo a en iando ues as suge encias a
la
edición
de
la e is a.
Como
ya
sabéis, una de las ca ac e ís icas del Campus N o d de
la
UPC es la exis encia de un cen o come cial que
es á si uado en e los edi icios C3, C4 y B4. Es e hecho, an habi ual en las uni e sidades del es o del mundo, se es á
ep oduciendo en los nue os campus, como el de
la
Au ónoma y el de la Vall d'Heb on, pe o en ninguno de es os casos
se
ha
conseguido una in eg ación u bana como en el caso de
La
CUP.
Se o ecen se icios de odo ipo, unos más di ec amen e elacionados con la ida es udian il (Sel Se ice
PoliMenu, la lib e ía écnica Díaz de San os, coope a i a de papele íaAbacus, Coope a i a de Publicaciones del Campus
No d CPET), y o os que nos ayudan a encon a más cómoda y ag adable nues a es ancia en el campus, pe mi iéndonos
aho a nos el incómodo ayec o al cen o de la ciudad (como puede se el RACC, una óp ica, una peluque ía, o icinas
banca ias, agencias de iajes, se icio de o ocopias, se icio de limpieza, se icio de mensaje ía, una ienda de depo es,
es au an es y un quiosco).
La
in ención de los ges o es de
La
CUP
ha sido siemp e la de mejo a la calidad de ida en el Campus. Como hemos
podido ap ecia , no solo nos han ace cado los se icios come ciales, sino que ambién pa icipan en las ac i idades
cul u ales y sociales, apoyando las inicia i as de los es udian es, ya sea pa a ealiza ies as, e is as, cong esos, e c.
En
pa e, g acias a ellos se man iene el espí i u uni e si a io, an necesa io pa a desconec a de la u ina es udian il.
La
CUP
pone a disposición de los es udian es (que en el ondo somos sus clien es) un despacho a donde podemos
acudi siemp e que su ja cualquie p oblema con locales de
La
CUP, o engamos alguna suge encia o queja al espec o
( eco demos el caso del Nyam-Nyam). Desde aquí os animamos a descub i lo que
La
CUP
nos o ece,
no
sólo
sus
come cios,
sino
ambién
su
apoyo
a
nues as
inicia i as
.
•
RAMAS
DE
ESTUDIANTES
DEL
IEEE 55