The Asymptotic Capacity of Private Information Retrieval With Secure Storage Under Disjoint Colluding Sets

Le résumé fourni par la source

In this paper, we consider the problem of private information retrieval with secure storage (SS-PIR) under a setting with disjoint colluding sets, where the user wishes to privately retrieve one out ofKindependent messages that are securely stored acrossNservers. TheNservers are partitioned intoMdisjoint colluding sets, i.e., within them-th group,m∈[M], any set of up toTmcolluding servers cannot learn any information about the index of the desired message, and any set of up toXmcolluding servers cannot learn any information about theKmessages. The asymptotic capacity is defined as the maximum possible number ofq-ary symbols of the desired message that can be retrieved perq-ary downloaded symbol, in the limit as the number of messagesK→ ∞. We demonstrate that the asymptotic capacity of SS-PIR with disjoint colluding sets is the solution to a linear program parameterized by the server partition, privacy thresholdsTm, and security thresholdsXm. Our achievability scheme introduces a novel pre-decoding strategy built upon cross-subspace alignment (CSA) codes. In this strategy, instead of requiring the user to decode the message from all of the original CSA coded answer symbols, our approach allows certain servers to perform a local pre-decoding and return intermediate results that turn out to be more communication-efficient. This mechanism is the key to minimizing the download cost, allowing our scheme to match the information-theoretic converse and thereby establish the asymptotic capacity of SS-PIR with disjoint colluding sets.

Ce résumé expose les affirmations des auteurs. BNTIC ne l’interprète pas comme une validation indépendante des résultats.