Combinatorial Configurations and User-Private Information Retrieval

Speaker: Klara Stokes (Universitat Rovira i Virgili, Catalonia)

Time: 4:00PM
Date: Mon 11th October 2010

Location: Mathematical Sciences Seminar Room

A combinatorial (v_r,b_k)-configuration is a family of points and a family of lines and a symmetric binary incidence relation such that each point is incident with precisely r of the b lines, each line is incident with precisely k of the v points, and two points can be incident with at most one line, or equivalently, two lines can be incident with at most one point. Here no geometric meaning is attached to the terms point and line. It has been proved that the set of parameters for which there exist combinatorial configurations can be given the structure of a numerical semigroup. Combinatorial configurations have been used in a peer-to-peer user-private information retrieval protocol protecting the privacy of the users of search engines. This talk will explain the role of combinatorical configurations in the above mentioned protocol and discuss some relations between the properties of the used configuration on one hand and the security of the protocol on the other.

(This talk is part of the Algebra/Claude Shannon Institute series.)