Name
Title | ||
|---|---|---|
Capacity-Achieving Private Information Retrieval Codes from MDS-Coded Databases with Minimum Message Size |
Abstract | ||
|---|---|---|
We consider constructing capacity-achieving linear codes with minimum message size for private information retrieval (PIR) from N non-colluding databases, where each message is coded using maximum distance separable (MDS) codes, such that it can be recovered from reading the contents of any T databases. It is shown that the minimum message size (sometimes also referred to as the sub-packetization level) is significantly, in fact exponentially, lower than previously believed. More precisely, when K > T/ gcd(N, T) where K is the total number of message in the system and gcd(·,·) means the greatest common divisor, we establish, by providing both a novel code construction and a matching converse, the minimum message size as lcm(N -T, T), where lcm(·,·) means the least common multiple. On the other hand, when K is small, we show that it is in fact possible to design codes with a message size even smaller than lcm(N - T, T). |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1109/ISIT.2019.8849542 | 2019 IEEE International Symposium on Information Theory (ISIT) |
Keywords | DocType | ISSN |
MDS-coded databases,minimum message size,capacity-achieving linear codes,maximum distance separable codes,novel code construction,capacity-achieving private information retrieval codes,noncolluding databases,PIR,greatest common divisor,matching converse,least common multiple | Conference | 2157-8095 |
ISBN | Citations | PageRank |
978-1-5386-9292-9 | 1 | 0.37 |
References | Authors | |
0 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ruida Zhou | 1 | 3 | 3.44 |
| Chao Tian | 2 | 86 | 21.64 |
| Tie Liu | 3 | 785 | 61.15 |
| Hua Sun | 4 | 294 | 28.30 |