Single-Server Client Preprocessing PIR with Space-Time Trade-off 2025 Eurocrypt

Single-Server Client Preprocessing PIR with Tight Space-Time Trade-off Zhikun Wang and Ling Ren University of Illinois at Urbana-Champaign Eurocrypt 2025, Madrid 1

?? = 0,1?? Private Information Retrieval [CKGS98] Server hosts a public database ? entries, each of ? bits User wishes to retrieve one entry Correctness: user retrieves the entry Privacy: server learns nothing ??[?] ? [?] 2

?? = 0,1?? Private Information Retrieval In the most standard setting where server stores only the unmodified database and client has no state server must scan entire database [BIM00] Ways to circumvent this lower bound Server preprocessing (doubly efficient PIR) Client preprocessing and stores hints ??[?] ? [?] 3

?? = 0,1?? Client Preprocessing PIR [PPY18, CK20, ] Offline: client privately fetches hints May involve downloading the entire database Online: client uses hints to make queries After sufficiently many queries, Client storage ? = ? Amortized server work ? = ? where ? hides large poly log?,? factors ? ? ??[?] ? [?] Hints 4

?? = 0,1?? Client Preprocessing PIR Lower bound: ?? = (?) [Yeo23] State-of-art practical scheme [RMS24] Client storage ? = ? ? ? Amortized server work ? = ? ? This work: ?? = ?(?) Assuming only OWF ??[?] ? [?] Hints 5

Large Client Storage of CK20 Paradigm Hints: parities of pseudorandom subset of size ? 1= DB 3 DB 8 DB 11 DB[15] 2= DB 5 DB 9 DB 11 DB[14] To query DB[?], client finds a hint whose subset ? contains ? 2= DB 5 DB 9 DB 11 DB[14] req = ? \ {?} ={5, 11, 14} DB[5], DB[11], DB[14] 6

Large Client Storage of CK20 Paradigm Hints: parities of pseudorandom subset of size ? 1= DB 3 DB 8 DB 11 DB[15] 2= DB 5 DB 9 DB 11 DB[14] To query DB[?], client finds a hint whose subset contains ? After the query, the used hint is deleted Will skip more subtle details (e.g., replenish a hint) 7

Large Client Storage of CK20 Paradigm Hints: parities of pseudorandom subset of size ? 1= DB 3 DB 8 DB 11 DB[15] 2= DB 5 DB 9 DB 11 DB[14] To query DB[?], client finds a hint whose subset contains ? With independent hints, need ? = ? ? hints so that every index appears at least once with all but exp ? probability 8

Structured Hints of [LP24] Organize the database as a square matrix, permute each row, column parties are hints Each entry appears exactly once, so ? = ? 2 1 0 3 DB[2] DB[1] DB[0] DB[3] 7 5 4 6 DB[7] DB[5] DB[4] DB[6] 11 8 9 10 DB[11] DB[8] DB[9] DB[10] 15 14 12 13 DB[15] DB[14] DB[12] DB[13] 1 2 3 Hint table 0 9

Structured Hints of [LP24] Database as matrix, permute each row, column parities as hints Querying an entry is similar as before ? {8,9,10,11} 2 1 0 3 req = {3,6,10 ?,13} 7 5 4 6 DB[3], DB[6], DB[r],DB[13] 11 8 9 10 15 14 12 13 0 1 2 3 3= DB[3] DB[6] DB[10] DB[13] 10

Structured Hints of [LP24] After a query, the hint table needs to be refreshed Every entry in the used hint is swapped with a random entry in its row Need to update the column parities need the swap entries 2 3 0 1 2 1 0 3 2 1 0 3 7 5 6 4 7 5 4 6 7 5 4 6 10 8 9 11 11 8 9 10 11 8 9 10 15 14 12 13 15 14 12 13 15 14 12 13 0 1 2 3 0 1 2 3 0 1 2 3 11

Two Major Downsides of [LP24] Need a second server to fetch swap entries Need ?(?) client storage for the (truly random) hint table 2 3 0 1 2 1 0 3 2 1 0 3 7 5 6 4 7 5 4 6 7 5 4 6 10 8 9 11 11 8 9 10 11 8 9 10 15 14 12 13 15 14 12 13 15 14 12 13 0 1 2 3 0 1 2 3 0 1 2 3 12

Our Technical Contributions Need a second server to fetch swap entries Need ?(?) client storage for the (truly random) hint table A single-server client preprocessing PIR using the matrix hint andpseudorandom permutations (hence ? ?client storage) 13

Step 1: Two-server to Single-server Introduce 1x empty space (treated as 0 in parity calculation) 2 1 0 3 2 1 0 3 7 5 4 6 7 5 4 6 11 8 9 10 11 8 9 10 15 14 12 13 15 14 12 13 Our hint table Hint table in [LP24] 14

Step 1: Two-server to Single-server Introduce 1x empty space (treated as 0 in parity calculation) Relocate used entry to random empty cell (instead of swapping) 2 1 0 3 2 1 0 3 7 5 4 6 7 6 5 4 11 8 9 10 11 8 9 10 15 14 12 13 15 14 12 13 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 15

Step 1: Two-server to Single-server: Security Each row stay permuted (across remaining columns) 2 1 0 3 2 1 0 3 7 5 4 6 7 6 5 4 11 8 9 10 11 8 9 10 15 14 12 13 15 14 12 13 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 16

Step 1: Two-server to Single-server: Efficiency Server work and bandwidth: ?( ?) amortized Offline phase costs ?(?) but amortized over ? online queries 2 1 0 3 2 1 0 3 7 5 4 6 7 6 5 4 11 8 9 10 11 8 9 10 15 14 12 13 15 14 12 13 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 17

Step 2: Sublinear Storage Need to get rid of the truly random permutations for rows A new data structure (one instance per row) that can Initialize entries to random positions Locate an entry (return its position) 2 1 0 3 Access an entry by position 7 5 4 6 Relocate entry to empty random position 11 8 9 10 and is space-efficient 15 14 12 13 18

The Data Structure using Small-domain PRP Small-domain Pseudorandom Permutation (PRP) [MR14]? and ? 1 ? 0 ,? 1 , ,?(? 1) are initial positions (? = ?) ? ? 1 , ,?(2?) will be used for relocations ? 0 1 2 3 4 5 6 7 8 9 ?(?) 4 5 1 7 3 8 2 9 0 6 Hint table row 2 4 0 1 3 0 1 2 3 4 5 6 7 8 9 19

The Data Structure using Small-domain PRP Small-domain Pseudorandom Permutation (PRP) [MR14]? and ? 1 ? 0 ,? 1 , ,?(? 1) are initial positions (? = ?) ? ? ,? ? + 1 ,?(2? 1) will be used for relocations ? 0 1 2 3 4 5 6 7 8 9 ?(?) 4 5 1 7 3 8 2 9 0 6 Hint table row 2 4 0 1 3 0 1 2 3 4 5 6 7 8 9 20

The Data Structure: Relocate ? ? + ? is the relocated position for ?-th consumed column ? 0 1 2 3 4 5 6 7 8 9 ?(?) 4 5 1 7 3 8 2 9 0 6 Hint table row 2 4 0 1 3 0 1 2 3 4 5 6 7 8 9 22

The Data Structure: Relocate ? ? + ? is the relocated position for ?-th consumed column ? 0 1 2 3 4 5 6 7 8 9 Store a list and a hash map for consumed columns ?(?) 4 5 1 7 3 8 2 9 0 6 Hint table row 2 4 0 1 3 2 1 0 1 2 3 4 5 6 7 8 9 23

The Data Structure: Relocate ? ? + ? is the relocated position for ?-th consumed column An empty spot may be consumed and will also be relocated ? 0 1 2 3 4 5 6 7 8 9 Store a list and a hash map for consumed columns ?(?) 4 5 1 7 3 8 2 9 0 6 Hint table row 2 4 0 1 3 2 1 9 0 1 2 3 4 5 6 7 8 9 24

The Data Structure: Relocate What if the position for relocation has already been consumed? ? 0 1 2 3 4 5 6 7 8 9 Store a list and a hash map for consumed columns ?(?) 4 5 1 7 3 8 2 9 0 6 Hint table row 2 4 0 1 3 2 1 9 7 0 1 2 3 4 5 6 7 8 9 25

The Data Structure: Relocate What if the position for relocation has already been consumed? Chase the relocation until finding an empty spot ? 0 1 2 3 4 5 6 7 8 9 Store a list and a hash map for consumed columns ?(?) 4 5 1 7 3 8 2 9 0 6 Hint table row 2 3 4 0 1 2 1 9 7 0 1 2 3 4 5 6 7 8 9 26

The Data Structure: Locate Locate(?): start from initial position ?(?), check if the position has been consumed, chase relocation until reaching an unconsumed ? 0 1 2 3 4 5 6 7 8 9 Store a list and a hash map for consumed columns ?(?) 4 5 1 7 3 8 2 9 0 6 Hint table row 2 3 4 0 1 2 1 9 7 0 1 2 3 4 5 6 7 8 9 27

The Data Structure: Locate Locate(?): start from initial position ?(?), check if the position has been consumed, chase relocation until reaching an unconsumed ? 0 1 2 3 4 5 6 7 8 9 Store a list and a hash map for consumed columns ?(?) 4 5 1 7 3 8 2 9 0 6 Hint table row 2 3 4 0 1 2 1 9 7 0 1 2 3 4 5 6 7 8 9 28

The Data Structure: Locate Locate(?): start from initial position ?(?), check if the position has been consumed, chase relocation until reaching an unconsumed ? 0 1 2 3 4 5 6 7 8 9 Store a list and a hash map for consumed columns ?(?) 4 5 1 7 3 8 2 9 0 6 Hint table row 2 3 4 0 1 2 1 9 7 0 1 2 3 4 5 6 7 8 9 29

The Data Structure: Access Access(?): check ? 1(?), backtrack until reaching an unconsumed position (empty) or an initial position (an entry) ? 0 1 2 3 4 5 6 7 8 9 Store a list and a hash map for consumed columns ?(?) 4 5 1 7 3 8 2 9 0 6 Hint table row 2 3 4 0 1 2 1 9 7 0 1 2 3 4 5 6 7 8 9 30

The Data Structure: Access Access(?): check ? 1(?), backtrack until reaching an unconsumed position (empty) or an initial position (an entry) ? 0 1 2 3 4 5 6 7 8 9 Store a list and a hash map for consumed columns ?(?) 4 5 1 7 3 8 2 9 0 6 Hint table row 2 3 4 0 1 2 1 9 7 0 1 2 3 4 5 6 7 8 9 31

The Data Structure: Access Access(?): check ? 1(?), backtrack until reaching an unconsumed position (empty) or an initial position (an entry) ? 0 1 2 3 4 5 6 7 8 9 Store a list and a hash map for consumed columns ?(?) 4 5 1 7 3 8 2 9 0 6 Hint table row 2 3 4 0 1 2 1 9 7 0 1 2 3 4 5 6 7 8 9 32

Properties of the Data Structure Correctness: Locate (Access) follow (reverse) relocation paths Security: entries are pseudorandomly distributed in unconsumed positions due to relocations Time: amortized ?(1) PRP calls per Locate/Access Space: list of up to ? consumed columns, shared by all rows 34

Summary First single-server client preprocessing PIR with client storage ? and amortized server work ? = ? ?/? when entry size ? = (log?) Matches the ?? = ? lower bound Relies only on OWF (PRP) Communication is ? ? , best among OWF-based schemes Client computation ? ? PRP calls, expensive in practice 35

References Benny Chor, Eyal Kushilevitz, Oded Goldreich, and Madhu Sudan. Private information retrieval. JACM 1998. Amos Beimel, Yuval Ishai, and Tal Malkin. Reducing the servers computation in private information retrieval: PIR with preprocessing. Crypto 2000. Sarvar Patel, Giuseppe Persiano, and Kevin Yeo. Private stateful information retrieval. CCS 2018. Henry Corrigan-Gibbs and Dmitry Kogan. Private information retrieval with sublinear online time. Eurocrypt 2020. Ling Ren, Muhammad Haris Mughees, and I Sun. Simple and Practical Amortized Sublinear Private Information Retrieval using Dummy Subsets. CCS 2024. Kevin Yeo. Lower bounds for (batch) PIR with private preprocessing. Eurocrypt 2023. Arthur Lazzaretti and Charalampos Papamanthou. Single Pass Client-Preprocessing Private Information Retrieval. Usenix Security 2024. Ben Morris and Phillip Rogaway. Sometimes-Recurse shuffle: almost-random permutations in logarithmic expected time. Eurocrypt 2014. 36