Combinatorial structures for anonymous database search

Author

Stokes, Klara

Director

Bras Amorós, Maria

Date of defense

2011-10-18

Legal Deposit

T. 1799-2011

Pages

201 p.



Department/Institute

Universitat Rovira i Virgili. Departament d'Enginyeria Informàtica i Matemàtiques

Abstract

This thesis treats a protocol for anonymous database search (or if one prefer, a protocol for user-private information retrieval), that is based on the use of combinatorial configurations. The protocol is called P2P UPIR. It is proved that the (v,k,1)-balanced incomplete block designs (BIBD) and in particular the finite projective planes are optimal configurations for this protocol. The notion of n-anonymity is applied to the configurations for P2P UPIR protocol and the transversal designs are proved to be n-anonymous configurations for P2P UPIR, with respect to the neighborhood points of the points of the configuration. It is proved that to the configurable tuples one can associate a numerical semigroup. This theorem implies results on existence of combinatorial configurations. The proofs are constructive and can be used as algorithms for finding combinatorial configurations. It is also proved that to the triangle-free configurable tuples one can associate a numerical semigroup. This implies results on existence of triangle-free combinatorial configurations.

Keywords

Combinatorial configuration; partial linear space; Block design; Numerial semigroup; User-private information retrieval; Anonymous database search

Subjects

004 - Computer science and technology. Computing. Data processing; 51 - Mathematics; 519.1 - Combinatorial analysis. Graph theory

Documents

tesis_enquadernat.pdf

1.469Mb

 

Rights

ADVERTIMENT. L'accés als continguts d'aquesta tesi doctoral i la seva utilització ha de respectar els drets de la persona autora. Pot ser utilitzada per a consulta o estudi personal, així com en activitats o materials d'investigació i docència en els termes establerts a l'art. 32 del Text Refós de la Llei de Propietat Intel·lectual (RDL 1/1996). Per altres utilitzacions es requereix l'autorització prèvia i expressa de la persona autora. En qualsevol cas, en la utilització dels seus continguts caldrà indicar de forma clara el nom i cognoms de la persona autora i el títol de la tesi doctoral. No s'autoritza la seva reproducció o altres formes d'explotació efectuades amb finalitats de lucre ni la seva comunicació pública des d'un lloc aliè al servei TDX. Tampoc s'autoritza la presentació del seu contingut en una finestra o marc aliè a TDX (framing). Aquesta reserva de drets afecta tant als continguts de la tesi com als seus resums i índexs.

This item appears in the following Collection(s)