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 accessing the contents of any T databases. It is shown that the minimum message size (sometimes also referred to as the sub-packetization factor) is significantly, in fact exponentially, lower than previously believed. More precisely, when K > T/ gcd(N, T) where K is the total number of messages in the system and gcd(·, ·) means the greatest common divisor, we establish, by providing both novel code constructions 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/TIT.2020.2977073 | IEEE Transactions on Information Theory |
Keywords | Field | DocType |
Data storage,information retrieval,privacy | Discrete mathematics,Converse,Separable space,Least common multiple,Greatest common divisor,Private information retrieval,Mathematics,Database,Message size | Journal |
Volume | Issue | ISSN |
66 | 8 | 0018-9448 |
Citations | PageRank | References |
1 | 0.35 | 0 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ruida Zhou | 1 | 3 | 3.44 |
| Chao Tian | 2 | 86 | 21.64 |
| Hua Sun | 3 | 294 | 28.30 |
| Tie Liu | 4 | 683 | 26.79 |