Maura Beth Paterson

A splitting BIBD is a type of combinatorial design that can be used to construct splitting authentication codes with good properties. In this paper we show that a design-theoretic approach is useful in the analysis of more general splitting authentication codes. Motivated by the study of algebraic manipulation detection (AMD) codes, we define the concept of a group generated splitting authentication code. We show that all group-generated authentication codes have perfect secrecy, which allows us to demonstrate that algebraic manipulation detection codes can be considered to be a special case of an authentication code with perfect secrecy. We also investigate splitting BIBDs that can be "equitably ordered". These splitting BIBDs yield authentication codes with splitting that also have perfect secrecy. We show that, while group generated BIBDs are inherently equitably ordered, the concept is applicable to more general splitting BIBDs. For various pairs $ (k, c) $, we determine necessary and sufficient (or almost sufficient) conditions for the existence of $ (v, k \times c, 1) $-splitting BIBDs that can be equitably ordered. The pairs for which we can solve this problem are $ (k, c) = (3, 2), (4, 2), (3, 3) $ and $ (3, 4) $, as well as all cases with $ k = 2 $.

In the classical model for (information theoretically secure) Private Information Retrieval (PIR) due to Chor, Goldreich, Kushilevitz and Sudan, a user wishes to retrieve one bit of a database that is stored on a set of ${n}$ servers, in such a way that no individual server gains information about which bit the user is interested in. The aim is to design schemes that minimise the total communication between the user and the servers. More recently, there have been moves to consider more realistic models where the total storage of the set of servers, or the per server storage, should be minimised (possibly using techniques from distributed storage), and where the database is divided into ${R}$ -bit records with ${R}>1$ , and the user wishes to retrieve one record rather than one bit. When ${R}$ is large, downloads from the servers to the user dominate the communication complexity and so the aim is to minimise the total number of downloaded bits. Work of Shah, Rashmi and Ramchandran shows that at least ${R}+1$ bits must be downloaded from servers in the worst case, and provides PIR schemes meeting this bound. Sun and Jafar have considered the download cost of a scheme, defined as the ratio of the message length ${R}$ and the total number of bits downloaded. They determine the best asymptotic download cost of a PIR scheme (as ${R}\rightarrow \infty $ ) when a database of ${k}$ messages is stored by ${n}$ servers. This paper provides various bounds on the download complexity of a PIR scheme, generalising those of Shah et al. to the case when the number ${n}$ of servers is bounded, and providing links with classical techniques due to Chor et al. The paper also provides a range of constructions for PIR schemes that are either simpler or perform better than previously known schemes. These constructions include explicit schemes that achieve the best asymptotic download complexity of Sun and Jafar with significantly lower upload complexity, and general techniques for constructing a scheme with good worst case download complexity from a scheme with good download complexity on average.

In the classical model for (information theoretically secure) Private Information Retrieval (PIR), a user wishes to retrieve one bit of a database that is stored on a set of $n$ servers, in such a way that no individual server gains information about which bit the user is interested in. The aim is to design schemes that minimise communication between the user and the servers. More recently, there have been moves to consider more realistic models where the total storage of the set of servers, or the per server storage, should be minimised (possibly using techniques from distributed storage), and where the database is divided into $R$-bit records with $R>1$, and the user wishes to retrieve one record rather than one bit. When $R$ is large, downloads from the servers to the user dominate the communication complexity and so the aim is to minimise the total number of downloaded bits. Shah, Rashmi and Ramchandran show that at least $R+1$ bits must be downloaded from servers in the worst case, and provide PIR schemes meeting this bound. Sun and Jafar determine the best asymptotic download cost of a PIR scheme (as $R\rightarrow\infty$), where this cost is defined as the ratio of the message length $R$ and the total number of bits downloaded. This paper provides various bounds on the download complexity of a PIR scheme, generalising those of Shah et al. to the case when the number $n$ of servers is bounded, and providing links with classical techniques due to Chor et al. The paper also provides a range of constructions for PIR schemes that are either simpler or perform better than previously known schemes, including explicit schemes that achieve the best asymptotic download complexity of Sun and Jafar with significantly lower upload complexity, and general techniques for constructing a scheme with good worst case download complexity from a scheme with good download complexity on average.