Esquemes per a compartir secrets

Abstract

Aquesta tesi ha estat destacada amb la menció de <br/>PREMI EXTRAORDINARI DE DOCTORAT en l'àmbit de MATEMÀTIQUES<br/>Curs 1997 - 98

A la present tesi ens hem ocupat fonamentalment de l'estudi matemàtic dels esquemes per a compartir secrets en les seves vessants de l'estudi de la taxa d'informació i de l'estudi dels esquemes segurs enfront l'acció de mentiders. Com a tema complementari hem estudiat la qüestió de l'arrel cúbica a l'anell dels enters mòdul m. Tots dos temes s'enquadren dins de la Criptologia.<br/><br/>Pel que fa l'estudi dels esquemes per a compartir secrets, els nostres objectius han estat la caracterització de les estructures ideals i la fitació de la taxa d'informació òptima per a certes famílies d'estructures d'accés. <br/><br/>La primera família estudiada ha estat la de les estructures definides per pesos i llindar. Hem trobat que totes es poden expressar mitjançant pesos i llindar naturals. Hem obtingut una caracterització completa de les de rang 2, és a dir, les que estan determinades per un graf que hem anomenat k-graf. Hem dissenyat un algorisme que les identifica a partir dels graus de cadascun dels vèrtexs i determina els pesos i llindar mínims. A partir de l'estructura d'aquests grafs hem determinat una fita inferior de la taxa d'informació òptima que és de l'ordre de 1/log n (amb n el número de participants), millorant la fita 1/2^{n/2} trobada amb l'únic esquema proposat fins ara per a aquestes estructures, degut a Shamir. A partir d'aquests resultats i mitjançant l'ús del dual d'una estructura hem extés els resultats anteriors a una nova família d'estructures. L'estudi general de les estructures definides per pesos i llindar de rang superior s'ha concentrat en trobar fites superiors i inferiors, especialment per les estructures definides per dos pesos. <br/><br/>La segona família que hem estudiat és la de les estructures bipartites. Per les estructures bipartites, hem aconseguit caracteritzar totalment les que són ideals. Aquestes són la família d'estructures de quasi-llindar. Aquesta caracterització de les estructures ideals fa que les estructures de quasi-llindar juguin un paper dins de les estructures bipartites anàleg al paper que juguen els grafs multipartits complets dins de les estructures definides per grafs. Així és equivalent dir que una estructura bipartita és ideal a dir que és de quasi-llindar o a dir que és pot definir amb un esquema d'espai vectorial o a dir que la seva taxa d'informació òptima és més gran que 2/3. Per les estructures bipartites descrivim tècniques típiques de recobriment per tal de trobar fites inferiors de la taxa d'informació. Determinem un algorisme que permet trobar una fita superior de la taxa d'informació. Justifiquem que aquestes fites són ajustades.<br/><br/>La següent família d'estructures que hem estudiat ha estat la de les estructures homogènies, obtenint resultats en la fitació inferior de la taxa d'informació. Hem proposat dues construccions d'esquemes per a compartir secrets per estructures homogènies basats en les tècniques de recobriments. Per avaluar les taxes d'informació hem definit el concepte de k-grau d'un participant en una estructura homogènia. Aquest paràmetre és la clau de tot l'estudi de les fites, de les comparacions entre elles i amb les conegudes fins ara. El resultat de la comparació indica que la segona d'elles ens dóna un esquema amb una taxa d'informació millor que la primera, però a canvi la primera utilitza un conjunt de secrets de mesura més realista. La comparació amb les proposades anteriorment mostra que les nostres són millors en la majoria dels casos. L'estudi de les fites superiors per les estructures homogènies l'hem encetat amb les de rang 3, trobant una primera fita superior per una subfamília d'estructures que és del mateix ordre que la fita inferior obtinguda per les nostres construccions. <br/> <br/>Pels esquemes segurs enfront l'acció de mentiders hem generalitzat els conceptes de seguretat per estructures de llindar al cas d'una estructura qualsevol, tant pel cas en el qual els mentiders no coneixen el secret, com pel cas que sí el coneixen. Hem trobat una fita superior de la taxa d'informació òptima per un esquema en el que una coalició de mentiders és detectada amb una certa probabilitat. Després d'aquest estudi general, hem proposat un esquema per a compartir secrets per a una estructura d'accés de tipus vectorial que detecta l'acció de coalicions de mentiders, que no coneixen el secret, amb una certa probabilitat. La taxa d'informació d'aquest esquema és 1/2, la qual és asímptòticament òptima. Per una estructura de llindar hem proposat un esquema que detecta l'acció de coalicions de mentiders (que sí que coneixen el secret) amb una certa probabilitat. Finalment hem trobat el primer esquema per a una estructura qualsevol que detecta l'acció de coalicions de mentiders (que no coneixen el secret) amb una certa probabilitat.<br/><br/>Pel que fa a l'arrel cúbica en el conjunt dels enters mòdul m, hem estudiat l'existència i número d'arrels. Hem generalitzat dos mètodes, dels més potents, pel càlcul de l'arrel quadrada per arrel cúbiques. Aquests són el mètode de Peralta basat en l'ús d'un anell auxiliar i el mètode de Tonelli-Shanks basat en l'ús de subgrups de Sylow. S'ha adjuntat algun comentari per les aplicacions criptogràfiques de les arrels cúbiques.

This thesis is mainly devoted to the study of information rate of secret sharing schemes as well as secret sharing schemes secures against the action of cheaters. As a complement we have studied the problem of cube roots in Z_m.<br/><br/>In the first part of our work we study some access structures in a combinatorial way and the boundness of the optimal information rate. We begin with weighted threshold access structures. We state that any of them can be defined with positive integer weights and threshold. We characterize all the rank 2 weighted threshold access structures as a k-graphs, finding minimum integer weights and threshold. We bound the optimal information rate using the complete multipartite covering technique. We extend the above results on characterization and computation of minimum weights and threshold to dual structures after proving the fact that the dual of a weighted threshold structure is a weighted threshold structure. <br/><br/>The second family of structures that we studied is the bipartite access structures. We characterize completely the bipartite access structures that can be realized by an ideal secret sharing scheme. We prove that in a bipartite access structure it is equivalent ideal structure, vector space structure and optimal information rate of the structure less than 2/3. Both upper and lower bounds on the optimal information rate of bipartite access structures are given. We also start the general study of multipartite access structure.<br/><br/>Using results on bipartite structures we study the information rate of secret sharing schemes whose access structure is defined by two weights and a threshold of arbitrary rank. Some upper and lower bounds are found. Case on more than two weights is considered too.<br/><br/>The last family of access structure that we have studied is the homogeneous access structure. We describe two constructions of secret sharing schemes for a such a general class of structures. The first one has a worst information rate than the second one, but on the other hand the size of the secret set is more moderate than the first one. We describe the comparison between our lower bounds on the optimal information rate and on the optimal average information rate as well as comparison with known upper bounds. The results are that our second one are better than the first one and that our bounds are better than the known bound almost for every structure.<br/><br/>We have started a study of the upper bounds on the optimal information rate for rank 3 homogenous access structures. We describe a structure that its upper bound is not so far than the lower bound obtained with our second construction.<br/><br/>Concerning to the extended capabilities we have studied the schemes secures against the action of cheaters. We have generalized the concepts of secure scheme and robust scheme to any access structure, that several authors have already defined only for threshold structures. We found that for a secure scheme the optimal information rate is upper bounded and we find the bound. We construct a 1/q-secure scheme (for q secrets) asymptotically optimal for a vector space access structure. We compare this scheme with the scheme of Ogata and Kurosawa.<br/> <br/>Our second scheme is robust realizing a (r,n) threshold structure with probability <= (2r-3)/(q-r). The information rate is 1/3. Finally we propose the first 1/q-secure scheme for any access structure.<br/><br/>We have generalized two of the fastest algorithms to take square roots to cube roots in Z_p. The first one is Peralta's algorithm, a probabilistic algorithm based on some properties of a ring. The non probabilistic part of the algorithm runs in log^3 p. The second one is Tonelli-Shanks' algorithm, a probabilistic method based on group theory which runs in log^4 p.