Title: Private Information Retrieval at 1 bit/sec/Hz of the Unconstrained Capacity of the Gaussian MAC and Some Results on Covert Control of a Linear System

Time: 13:30-14:30 CEST, Wed Oct 23, 2024

Location: Systemet, B-huset 3rd floor, LiU Valla Campus, Linköping, Sweden

https://link.mazemap.com/bpxG7JDf 

Local Host: Onur Günlü, LiU ISY ICG Information Theory and Security Laboratory (ITSL), onur.gunlu@liu.se

Abstract: In Private Information Retrieval (PIR), there are N replicated non-communicating databases containing the same M messages, and a user who wishes to retrieve one of the messages without revealing the message's index to the databases. In most cases, one assumes orthogonal, error-free links between the user and the databases. In this talk, we will assume a shared medium between the user and the databases. Specifically, a block-fading Additive White Gaussian Noise Multiple Access Channel (AWGN MAC). We will review some previously known results on PIR in general, show how a separated coding scheme fails to achieve optimal performance in this case, then propose a joint channel-PIR coding scheme whose rate scales with both the number of databases N and the power P similarly to the channel capacity without the privacy constraint. Furthermore, the analysis reveals that the proposed scheme has only a finite gap from this unconstrained channel capacity: 1 bit/sec/Hz as N increases.

We will then turn to consider a different problem, that of covertly controlling a linear system. In this problem, Alice desires to control (stabilize or change the behaviour of) a linear system, while keeping an observer, Willie, unable to decide if the system is indeed being controlled or not. We will formally define the problem, under a model where Willie can only observe the system's output. Focusing on AR(1) systems, we will show that when Willie observes the system's output through a clean channel, an inherently unstable linear system can not be covertly stabilized. However, under some conditions on the parameters and observation time, an inherently stable linear system can be covertly controlled, in the sense of covertly changing its parameter or resetting its memory. Moreover, we will give positive and negative results for two important controllers: a minimal-information controller, where Alice is allowed to use only 1 bit per sample, and a maximal-information controller, where Alice is allowed to view the real-valued output. The results reveal an interesting interplay in covert control, between the amount of information used by the controller, control performance and covertness.

About the Speaker: Asaf Cohen received the B.Sc. (Hons.), M.Sc. (Hons.), and Ph.D. degrees from the Department of Electrical Engineering, Technion, Israel Institute of Technology, in 2001, 2003, and 2007, respectively. From 1998 to 2000, he was with the IBM Research Laboratory, Haifa, where he was working on distributed computing. Between 2007 and 2009 he was a Post-Doctoral Scholar at the California Institute of Technology, and between 2015–2016 he was a visiting scientist at the Massachusetts Institute of Technology. He is currently an Associate Professor and the Vice Chair for Teaching at the School of Electrical and Computer Engineering, Ben-Gurion University of the Negev, Israel. His areas of interest are information theory and coding, estimation, learning, and decision making. He received several honors and awards, including the Viterbi Post-Doctoral Scholarship, the Dr. Philip Marlin Prize for Computer Engineering in 2000, the Student Paper Award from IEEE Israel in 2006 and the Ben-Gurion University Excellence in Teaching award in 2014. He served as a Technical Program Committee for ISIT, ITW and VTC for several years, and as an Associate Editor at IEEE Transactions on Communications.

Asaf Cohen of the Ben-Gurion University of the Negev has visited the Information Theory and Security Laboratory (ITSL) within the Linköping University Information Coding Division (ICG) in Linköping, Sweden during September-October 2024.