On linear secret sharing schemes and distributed crytographic protocols

Vanesa Daza Fernández

Published Jan 1, 2004• 0 citations

Abstract

Suposem que un conjunt de n participants vol calcular una determinada funcio (publica) de les seves entrades (secretes). De manera generica els protocols de computacio multipart s'encarreguen de garantir una solucio per a aquest tipus de situacions. Proposen protocols segurs on els participants executen conjuntament un protocol de manera distribuida que els permet obtenir, al final, el resultat de l'avaluacio de la funcio amb les seves entrades. A mes a mes es garanteixen alguns aspectes de seguretat, com la privacitat de les entrades dels participants aixi com l'exactitud del resultat, fins i tot si alguns participants del protocol es comporten de manera deshonesta. A finals dels anys 80 es van presentar les primeres solucions generals a aquest problema que garantien seguretat tot i que certes families de participants es comportessin de manera corrupta. Aquestes families estaven caracteritzades per un cert llindar t, de manera que la seguretat del protocol estava garantida nomes si menys de t participants eren corromputs. No va ser fins l'any 2000 que no es va presentar una solucio eficient per a resoldre aquest problema, permetent l'estructura mes general possible de participants per corrompre. La proposta relacionava la computacio multipart amb els esquemes lineals per a compartir secrets. En certa manera utilitzen la linealitat del esquemes lineals per a compartir secrets per a calcular la part lineal de la funcio. Pero per poder calcular qualsevol funcio es necessari poder avaluar la multiplicacio de manera distribuida entre el conjunt de participants. Aixi es com sorgeix el problema matematic de la multiplicacio dels esquemes lineals per a compartir secrets. En poques paraules, el problema consisteix en trobar protocols eficients que calculin el producte de dos secrets a partir dels fragments que cada participant te de cadascun dels secrets. Un dels punts clau de la seva proposta es la reduccio de la co

Related papers

Some issues in public key cryptography: hard-core rpedicates, distributed protocols and functional encryption

Carla Ràfols Salvador

Aquesta tesi presenta algunes contribucions en l'area dels fonaments de la criptografia i del xifrat funcional demostrablement segur. La primera contribucio es en l'area dels predicats hard-core i consisteix en donar una prova alternativa de la seguretat dels bits interns de la preimatge de les permutacions amb trampa m'es comuns utilizant la metodologia basada en decodificacio en llista d'Akavia, Goldwasser i Safra. La segona contribucio es un estudi mes detallat del problema de correccio d'errors del codi de Reed-Solomon a l'exponent, que sorgeix de manera natural en molts protocols criptografics de llindar. Mes generalment, estudiem el problema de correccio d'aquest codi quan esta xifrat amb una funcio unidireccional. Demostrem que la correccio d'errors eficient es possible quan la funcie unidireccional te certes propietats homomorfiques. Tambe donem evidencia parcial que indica que el nostre resultat es optim en el sentit que la correccio eficient quan el codi esta xifrat es dificil si la funcio unidireccional en questio no te aquestes propietats homomorfiques. Els nostres resultats estan inspirats en un treball anterior de Peikert del 2006. La tercera contribucio es en el domini del xifrat basat en identitats, en el qual demostrem que qualsevol esquema que sigui segur sota atacs de missatge en clar escollit selectius i que sigui anonim sota atacs adaptatius, tambe es segur contra atacs de missatge en clar escollit adaptatius. L'ultima contribucio es el disseny del primer esquema basat en atributs que produeix textos xifrats de mida constant i que admet politiques de xifrat de llindar no trivials. El nostre resultat esta inspirat en l'esquema de llindar dinamic de Delerablee i Pointcheval.

Jan 1, 20110 citations

Multipartite secret sharing schemes

Oriol Farràs

This thesis is dedicated to the study of secret sharing schemes, which are cryptographic methods to share information in a secure way. The topics that are considered in the thesis are two of the main open problems in secret sharing: the characterization of the ideal access structures and the optimization of the length of the shares for general access structures. These open problems are studied for multipartite secret sharing schemes. In these schemes the set of participants is divided into parts and the participants in each part have the same rights to obtain the secret. The results of the thesis are based on a new combinatorial property of secret sharing schemes, which is a connection between ideal multipartite secret sharing schemes and integer polymatroids. It provides new sufficient conditions and necessary conditions for an access structure to be ideal. Moreover, this connection is also used in the construction ideal linear multipartite secret sharing schemes. These results are useful for the study of multipartite access structures in which the number of parts is small in relation to the number of participants, and multipartite access structures in which the parts are related in a special way. This is the case of the family of hierarchical access structures, which are the ones in which the participants can be hierarchically ordered, and the family of tripartite access structures. Applying these results, the ideal access structures in these families are completely characterized. All the ideal multipartite secret sharing schemes presented in the literature are related to a particular family of integer polymatroids, the boolean ones. The analysis of these polymatroids leds to the find of new ideal multipartite secret sharing schemes. The optimization of the length of the shares is also studied for multipartite secret sharing schemes, in particular for the bipartite ones. The main results are a new method to find bound on the length of the shares that combines linear El tema d'aquesta tesi són els esquemes de compartició de secrets, uns mètodes criptogràfics que permeten fragmentar missatges de manera segura. En particular s'aborden dos dels principals problemes oberts en aquest camp: la caracterització de les estructures d'accés que admeten esquemes de compartició de secrets ideals i l'optimització de la llargada dels fragments en construccions per estructures d'accés generals. Aquests problemes oberts s'estudien per estructures d'accés multipartides, que són estructures en què el conjunt de participants està dividit en diferents parts i a cada part tots els participants tenen el mateix rol. Aquest plantejament resulta útil per estudiar famílies d'estructures d'accés en què el nombre de parts és petit i estructures en què hi ha alguna relació especial entre les parts, com les jeràrquiques i les compartmentades. L'eina principal d'aquest estudi és una nova propietat de les estructures ideals que es presenta en aquesta tesi, una connexió entre les estructures ideals multipartides i els polimatroides enters. A partir d'aquesta connexió s'obté una condició suficient i una de necessària perquè una estructura d'accés multipartida sigui ideal. Així, aquesta connexió permet discutir la idealitat de les estructures d'accés i també, en el cas que el polimatoride sigui representable, construir esquemes ideals a partir de les representacions. Aplicant aquests resultats s'obté un nou marc per descriure i analitzar mètodes per construir esquemes multipartits ideals. Com a resultat d'aquest estudi s'obté una caracterització completa de les estructures d'accés tripartides ideals i de les jeràrquiques ideals. Una estructura és jeràrquica si el conjunt de participants es pot ordenar de tal manera que si en un conjunt autoritzat es canvia un participant per un de jeràrquicament superior, el nou conjunt també és autoritzat. A partir d'aquest resultat s'obté una nova caracterització de les estructures de llindar amb pesos ideals. Després d'analitzar tots els esquemes de compartició de secrets ideals multipartits presentats fins l'actualitat, es mostra que tots ells estan relacionats amb una família molt senzilla de polimatroides enters, els booleans. A partir d'aquests polimatroides s'obté una nova família d'estructures ideals, les compartmentades, que inclouen diverses famílies estudiades prèviament. L'altre problema obert considerat a la tesi, l'estudi de l'optimització de la llargada dels fragments, es centra en les estructures bipartides. Combinant tècniques de programació lineal i polimatroides, es presenta un mètode per calcular fites en la llargada dels fragments per estructures d'accés no ideals que és vàlid per qualsevol estructura multipartida. A partir de tècniques algebraiques es presenten noves fites i una família d'esquemes bipartits òptims.

Jul 27, 20102 citations

General Secure Multi-party Computation from any Linear Secret-Sharing Scheme

Ronald Cramer, Ivan Damgård, Ueli M. Maurer

Lecture notes in computer scienceJan 1, 2000548 citations

On Multiplicative Linear Secret Sharing Schemes

Ventzislav Nikov, Svetla Nikova⋆, Bart Preneel A

Lecture notes in computer scienceJan 1, 20039 citations

Parallel Multi-party Computation from Linear Multi-secret Sharing Schemes

Zhifang Zhang, Mulan Liu, Liangliang Xiao

Lecture notes in computer scienceJan 1, 20054 citations

Probabilistic quantum metrology

B. Gendra

La Metrologia es el camp d’investigacio sobre les eines estadistiques i el disseny tecnologic dels aparells de mesura necessaris per inferir informacio precisa sobre parametres fisics. En un sistema fisic el soroll es inherent en ultima instancia amb el de les seves parts, i per tant en un nivell microscopic esta governat per les lleis de la fisica quantica. Les mesures quantiques son intrinsecament sorolloses i per tant limiten la precisio amb la qual es pot obtenir en qualsevol escenari de metrologia. El camp de la metrologia quantica esta dedicat a l’estudi d’aquests limits i al desenvolupament de noves eines per ajudar a superar-los, sovint fent us de les caracteristiques exclusivament quantiques com la superposicio o l'entrellacament.En el proces de disseny d’un protocol d’estimacio es necessari utilitzar una figura de merit per optimitzar el rendiment d’aquests protocols. Fins ara la majoria de plantejaments de metrologia quantica i els limits que en deriven han estat deterministes, es a dir, que estan optimitzats per tal de proporcionar una estimacio valida per a cadascun dels possibles resultats de la mesura i minimitzar-ne l’error promig entre el valor estimat i el real del parametre. Aquesta avaluacio dels protocols mitjancant el seu error promig es molt natural i convenient, pero pot haver-hi algunes situacions en que aixo no sigui suficient per a expressar l’us concret que se li donara al valor obtingut.Un punt central d’aquesta tesi es observar que resultats concrets d’una mesura poden proporcionar una estimacio amb una millor precisio que la mitjana. Perque aixo succeeixi hi ha d’haver altres resultats imprecisos que compensin la mitjana perque aquesta no violi els limits deterministes. En aquesta tesi hem escollit una figura de merit que re?ecteix la maxima precisio que es pot obtenir. Optimitzem la precisio d’un subconjunt de resultats senyalats, i quantifiquem la probabilitat d’obtenir-ne algun d’ells, o en altres paraules, la probabilitat que el protocol proporcioni una estimacio. Aixo pot ser entes com proposar una opcio addicional que esta sempre disponible per la mesura, a saber, la possibilitat de post-seleccionar els resultats i donar amb nomes certa probabilitat una resposta concloent. Aquests protocols probabilistics garanteixen una precisio minima pels resultats senyalats. En la mecanica quantica hi ha moltes maneres de poder llegir les dades d’un sistema quantic. Per tant, l’optimitzacio dels esquemes probabilistics no es pot reduir a la reinterpretacio de resultats a partir dels esquemes (determinsitic) de metrologia quantica canoniques, sino que implica la recerca de mesures quantiques completament diferents. Concretament, hem dissenyat protocols probabilistics per a l’estimacio de fases, direccions i de sistemes de referencia. Hem vist que la post-seleccio te dos efectes possibles: compensar una mala eleccio de l’estat inicial o contrarestar els efectes negatius del soroll presents en l’estat del sistema o en el proces de mesurament. En particular, trobem que afegir la possibilitat d’abstencio en l’estimacio de fases en presencia de soroll pot produir una millora en la precisio que supera la cota trobada per protocols deterministes. Trobem una cota que correspon a la millor precisio que es pot obtenir.

Nov 23, 20150 citations