Talk: Prof. Alex Sprintson (July 18, 2023 at 1:30 PM, Seminar room N2409)
Polynomial Codes for Private Information Retrieval
Prof. Alex Sprintson
Department of Electrical and Computer Engineering
Texas A&M University, College Station, USA.
The first part of the talk will focus on the problem of private information retrieval (PIR) with a Maximum Distance Separable (MDS) coded storage (a generalization of the replicated storage) and T-colluding servers, referred to as MDS-TPIR problem. We present a novel class of polynomial schemes for the MDS-TPIR problem. Toward this goal, first we established a significant connection between this problem and the problem of Secure Distributed Matrix Multiplication (SSDM) in which a user wants to compute the product of two matrices with the assistance of N servers without leaking any information about either of the matrices to any server. Through this connection, we construct polynomial codes for MDS-TPIR problem using a combinatorial tool called degree table, recently introduced for SDMM.
In the second part of the talk, we focus on a generalization of the multi-message Private Information Retrieval (PIR) problem in which the user needs to retrieve a subset of messages from a database replicated across N servers. The collection of all possible subsets that can be retrieved is represented by a hypergraph G(V,E). In this version of the PIR problem, the capacity (i.e., the maximum achievable ratio of the amount of information required by the user to the amount of information that needs to be downloaded from the servers) depends on the structure of the hypergraph G(V,E). Our research aims to establish the capacity for a large family of graphs of practical importance and develop capacity-achieving coding schemes for private subset retrieval.
Alex Sprintson is a principal at Network Systems and Security Research lab at Nokia Bell Labs and a faculty member in the Department of Electrical and Computer Engineering at Texas A&M University, College Station, where he conducts research on security and privacy, network coding, wireless networks, and distributed storage systems. Dr. Sprintson received the Wolf Award for Distinguished Ph.D. students, the Viterbi Postdoctoral Fellowship, the TAMU College of Engineering Outstanding Contribution Award, and the NSF CAREER award. From 2013 and 2019 he served as an Associate Editor of the IEEE Transactions on Wireless Communications. He has been a member of the Technical Program Committee for the IEEE Infocom 2006-2023 From Sept. 2018 to Sept. 2022, Dr. Sprintson served as a rotating program director at the US National Science Foundation (NSF).