Chapter 14: PIR with Coded Storage and Colluding Databases

Learning Objectives

• Construct PIR schemes for $(N, r)$-MDS-coded storage and quantify the storage-rate trade-off
• State and apply the Tajeddine–El Rouayheb capacity for coded-storage PIR
• Extend PIR to $T$-colluding databases via the Sun–Jafar 2018 capacity formula
• Define symmetric PIR (SPIR) with two-sided privacy and prove the $1 - 1/N$ capacity
• Combine coded-storage and colluding constraints; recognize when joint capacity is open