ترغب بنشر مسار تعليمي؟ اضغط هنا

On the Access Complexity of PIR Schemes

57   0   0.0 ( 0 )
 نشر من قبل Yiwei Zhang
 تاريخ النشر 2018
  مجال البحث الهندسة المعلوماتية
والبحث باللغة English




اسأل ChatGPT حول البحث

Private information retrieval has been reformulated in an information-theoretic perspective in recent years. The two most important parameters considered for a PIR scheme in a distributed storage system are the storage overhead and PIR rate. The complexity of the computations done by the servers for the various tasks of the distributed storage system is an important parameter in such systems which didnt get enough attention in PIR schemes. As a consequence, we take into consideration a third parameter, the access complexity of a PIR scheme, which characterizes the total amount of data to be accessed by the servers for responding to the queries throughout a PIR scheme. We use a general covering codes approach as the main tool for improving the access complexity. With a given amount of storage overhead, the ultimate objective is to characterize the tradeoff between the rate and access complexity of a PIR scheme. This covering codes approach raises a new interesting coding problem of generalized coverings similarly to the well-known generalized Hamming weights.



قيم البحث

اقرأ أيضاً

Recently multi-access coded caching schemes with number of users different from the number of caches obtained from a special case of resolvable designs called Cross Resolvable Designs (CRDs) have been reported and a new performance metric called rate -per-user has been introduced cite{KNRarXiv}. In this paper we present a generalization of this work resulting in multi-access coded caching schemes with improved rate-per-user.
OR multi-access channel is a simple model where the channel output is the Boolean OR among the Boolean channel inputs. We revisit this model, showing that employing Bloom filter, a randomized data structure, as channel inputs achieves its capacity re gion with joint decoding and the symmetric sum rate of $ln 2$ bits per channel use without joint decoding. We then proceed to the many-access regime where the number of potential users grows without bound, treating both activity recognition and message transmission problems, establishing scaling laws which are optimal within a constant factor, based on Bloom filter channel inputs.
In this paper we introduce the two-user asynchronous cognitive multiple access channel (ACMAC). This channel model includes two transmitters, an uninformed one, and an informed one which knows prior to the beginning of a transmission the message whic h the uninformed transmitter is about to send. We assume that the channel from the uninformed transmitter to the receiver suffers a fixed but unknown delay. We further introduce a modified model, referred to as the asynchronous codeword cognitive multiple access channel (ACC-MAC), which differs from the ACMAC in that the informed user knows the signal that is to be transmitted by the other user, rather than the message that it is about to transmit. We state inner and outer bounds on the ACMAC and the ACC-MAC capacity regions, and we specialize the results to the Gaussian case. Further, we characterize the capacity regions of these channels in terms of multi-letter expressions. Finally, we provide an example which instantiates the difference between message side-information and codeword side-information.
67 - Biao He , An Liu , Nan Yang 2016
This paper proposes a new design of non-orthogonal multiple access (NOMA) under secrecy considerations. We focus on a NOMA system where a transmitter sends confidential messages to multiple users in the presence of an external eavesdropper. The optim al designs of decoding order, transmission rates, and power allocated to each user are investigated. Considering the practical passive eavesdropping scenario where the instantaneous channel state of the eavesdropper is unknown, we adopt the secrecy outage probability as the secrecy metric. We first consider the problem of minimizing the transmit power subject to the secrecy outage and quality of service constraints, and derive the closed-form solution to this problem. We then explore the problem of maximizing the minimum confidential information rate among users subject to the secrecy outage and transmit power constraints, and provide an iterative algorithm to solve this problem. We find that the secrecy outage constraint in the studied problems does not change the optimal decoding order for NOMA, and one should increase the power allocated to the user whose channel is relatively bad when the secrecy constraint becomes more stringent. Finally, we show the advantage of NOMA over orthogonal multiple access in the studied problems both analytically and numerically.
We study a deterministic approximation of the two-user multiple access wiretap channel. This approximation enables results beyond the recently shown $tfrac{2}{3}$ secure degrees of freedom (s.d.o.f.) for the Gaussian multiple access channel. While th e s.d.o.f. were obtained by real interference alignment, our approach uses signal-scale alignment. We show an achievable scheme which is independent of the rationality of the channel gains. Moreover, our result can differentiate between channel strengths, in particular between both users, and establishes a secrecy rate dependent on this difference. We can show that the resulting achievable secrecy rate tends to the s.d.o.f. for vanishing channel gain differences. Moreover, we extend the s.d.o.f. bound towards a general bound for varying channel strengths and show that our achievable scheme reaches the bound for certain channel gain parameters. We believe that our analysis is the first step towards a constant-gap analysis of the Gaussian multiple access wiretap channel.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا