Qiwen Wang

Qiwen Wang

Auto-generated profile, based on publicly available information

Qiwen Wang

Department of Information Science and Engineering, KTH Royal Institute of Technology, SE-100 44, Stockholm, Sweden

Research Focus & Metrics

Academic Career Length

12Years (2015-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
5 March 2019 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
QWQiwen Wang
Qiwen Wang
MSMikael Skoglund
Mikael Skoglund
A user wants to retrieve a file from a database without revealing the identity of the file retrieved to the operator of the database (server), which is known as the problem of private information retrieval (PIR). If it is further required that the user obtains no information about the other files in the database, the concept of symmetric private information retrieval (SPIR) is introduced to guarantee privacy for both parties. For SPIR, the server(s) need to access some randomness independent of the database, to protect the content of undesired files from the user. The information-theoretic capacity of SPIR is defined as the maximum number of information bits of the desired file retrieved per downloaded bit. In this paper, the problem of SPIR is studied for a distributed storage system with N servers (nodes), where all data (including the files and the randomness) are stored in a distributed way. Specifically, the files are stored by an (N,KC)-MDS storage code. The randomness is distributedly stored such that any KC servers store independent randomness information. We consider two scenarios regarding to the ability of the storage nodes to cooperate. In the first scenario considered, the storage nodes do not communicate or collude. It is shown that the SPIR capacity for MDS-coded storage (hence called MDS-SPIR) is 1-KCN, when the amount of the total randomness of distributed nodes (unavailable at the user) is at least KCN-KC times the file size. Otherwise, the MDS-SPIR capacity equals zero. The second scenario considered is the T-colluding SPIR problem (hence called TSPIR). Specifically, any T out of N servers may collude, that is, they may communicate their interactions with the user to guess the identity of the requested file. In the special case with KC=1, i.e., the database is replicated at each node, the capacity of TSPIR is shown to be 1-TN, with the ratio of the total randomness size relative to the file size be at least TN-T. For TSPIR with MDS-coded storage (called MDS-TSPIR for short), when restricted to schemes with additive randomness where the servers add the randomness to the answers regardless of the queries received, the capacity is proved to equal 1-KC+T-1N, with total randomness at least KC+T-1N-KC-T+1 times the file size. The MDS-TSPIR capacity for general schemes remains an open problem.

4 December 2018 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
QWQiwen Wang
Qiwen Wang
Hua SunHua Sun
Hua Sun
MSMikael Skoglund
Mikael Skoglund
We consider the problem of private information retrieval (PIR) with colluding servers and eavesdroppers (abbreviated as ETPIR). The ETPIR problem is comprised of K messages, N servers where each server stores all K messages, a user who wants to retrieve one of the K messages without revealing the desired message index to any set of T colluding servers, and an eavesdropper who can listen to the queries and answers of any E servers but is prevented from learning any information about the messages. The information theoretic capacity of ETPIR is defined to be the maximum number of desired message symbols retrieved privately per information symbol downloaded. We show that the capacity of ETPIR is C = (1 – E/N) (1 + T–E/N–E + … + ( T–E/N–E) K–1)–1 when E < T, and C = (1 – E/N) when E ≥ T. To achieve the capacity, the servers need to share a common random variable (independent of the messages), and its size must be at least E/N · 1/C symbols per message symbol. Otherwise, with less amount of shared common randomness, ETPIR is not feasible and the capacity reduces to zero. An interesting observation is that the ETPIR capacity expression takes different forms in two regimes. When E < T, the capacity equals the inverse of a sum of a geometric series with K terms and decreases with K; this form is typical for capacity expressions of PIR. When E ≥ T, the capacity does not depend on K, a typical form for capacity expressions of SPIR (symmetric PIR, which further requires data-privacy, i.e., the user learns no information about other undesired messages); the capacity does not depend on T either. In addition, the ETPIR capacity result includes multiple previous PIR and SPIR capacity results as special cases.

25 October 2018 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
QWQiwen Wang
Qiwen Wang
MSMikael Skoglund
Mikael Skoglund
We consider the problem of private information retrieval (PIR) and symmetric private information retrieval (SPIR) from replicated databases with colluding servers, in the presence of Byzantine adversaries and eavesdroppers. Specifically, there are K messages replicatively stored at N databases. A user wants to retrieve one message by communicating with the databases, without revealing the identity of the message retrieved. For T-colluding databases, any T out of N databases may communicate their interactions with the user to guess the identity of the requested message. We consider the situation where the communication system can be vulnerable to attachers, namely, there is an adversary in the system that can tap in on or even try to corrupt the communication. The capacity is defined as the maximum number of information bits of the desired message retrieved per downloaded bit. For SPIR, it is further required that the user learns nothing about the other K – 1 messages in the database. Three types of adversaries are considered: a Byzantine adversary who can overwrite the transmission of any B servers to the user; a passive eavesdropper who can tap in on the incoming and outgoing transmissions of any E servers; and a combination of both – an adversary who can tap in on a set of any E nodes, and overwrite the transmission of a set of any B nodes. The problems of SPIR with colluding servers and the three types of adversaries are named T-BSPIR, T-ESPIR and T-BESPIR respectively. We derive the capacities of the three secure SPIR problems. The results resemble those of secure network coding problems with adversaries and eavesdroppers. The capacity of T-colluding PIR with Byzantine adversaries is characterized in [1]. In this work, we consider T-colluding PIR with an eavedropper (named T-EPIR). We derive the T-EPIR capacity when E ≥ T; for the case where E ≤ T, we find an outer bound (converse bound) and an inner bound (achievability) on the optimal achievable rate.

21 March 2018 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
QWQiwen Wang
Qiwen Wang
SJSidharth Jaggi
Sidharth Jaggi
In highly dynamic wireless networks, communications face several challenges. In the first place, noise levels between nodes might be difficult to predict a priori. Besides, a Byzantine attacker hidden in the network, with knowledge of the network topology and observation of all transmissions, can choose arbitrary locations to inject corrupted packets. Considering that transmissions are usually in bits and hardware in wireless networks usually use modulation schemes with the size of modulation alphabet being powers of two, e.g. BPSK, QPSK, 16-QAM, 64-QAM etc., to address the above problem, we study coding for networks experiencing worst-case bit errors, and with network codes over binary extension fields. We demonstrate that in this setup prior network error-correcting schemes can be arbitrarily far from achieving the optimal network throughput. A new transform metric for errors under the considered model is proposed. Using this metric, we replicate many of the classical results from coding theory. Specifically, new Hammingtype, Plotkin-type, and Elias-Bassalygo-type upper bounds on the network capacity are derived. A commensurate lower bound is shown based on Gilbert-Varshamov(GV)-type codes for errorcorrection. The GV codes used to attain the lower bound can be non-coherent, that is, they require neither prior knowledge of the network topology nor network coding kernels. We also propose a computationally-efficient concatenation scheme. The rate achieved by our concatenated codes is characterized by a Zyablov-type lower bound. We provide a generalized minimumdistance decoding algorithm which decodes up to half the minimum distance of the concatenated codes. The end-to-end nature of our design enables our codes to be overlaid on the classical distributed random linear network codes. The other advantage of the end-to-end strategy over the link-by-link error-correction is that it reduces the computational cost at the internal nodes for performing error-correction.

17 May 2017 in IEEE Transactions on Information Theory
Verified
Journal Article
Open access
QWQiwen Wang
Qiwen Wang
SJSidharth Jaggi
Sidharth Jaggi
MMMuriel Medard
Muriel Medard
VCViveck R. Cadambe
Viveck R. Cadambe
MSMoshe Schwartz
Moshe Schwartz
The problem of one-way file synchronization, henceforth called “file updates”, is studied in this paper. Specifically, a client edits a file, where the edits are modeled by insertions and deletions (InDels). An old copy of the file is stored remotely at a data-centre, and is also available to the client. We consider the problem of throughput- and computationally-efficient communication from the client to the data-centre, to enable the data-centre to update its old copy to the newly edited file. Two models for the source files and edit patterns are studied: the random pre-edit sequence left-to-right random InDel (RPES-LtRRID) process, and the arbitrary pre-edit sequence arbitrary InDel (APES-AID) process. In both models, we consider the regime, in which the number of insertions and deletions is a small (but constant) fraction of the length of the original file. For both models, information-theoretic lower bounds on the best possible compression rates that enable file updates are derived (up to first order terms). Conversely, a simple compression algorithm using dynamic programming (DP) and entropy coding (EC), henceforth called DP-EC algorithm, achieves rates that are within constant additive gap (which diminishes as the alphabet size increases) to information-theoretic lower bounds for both models. For the RPES-LtRRID model, a dynamic-programming-run-length-compression (DP-RLC) algorithm is proposed, which achieves a compression rate matching the information-theoretic lower bound up to first order terms. Therefore, when the insertion and deletion probabilities are small (such that first order terms dominate), the achievable rate by DP-RLC is nearly optimal for the RPES-LtRRID model.

11 October 2015 in arXiv
Verified
Preprint
Open access
PDF file
QWQiwen Wang
Qiwen Wang
SJSidharth Jaggi
Sidharth Jaggi
The problem of coding for networks experiencing worst-case symbol errors is considered. We argue that this is a reasonable model for highly dynamic wireless network transmissions. We demonstrate that in this setup prior network error-correcting schemes can be arbitrarily far from achieving the optimal network throughput. A new transform metric for errors under the considered model is proposed. Using this metric, we replicate many of the classical results from coding theory. Specifically, we prove new Hamming-type, Plotkin-type, and Elias-Bassalygo-type upper bounds on the network capacity. A commensurate lower bound is shown based on Gilbert-Varshamov-type codes for error-correction. The GV codes used to attain the lower bound can be non-coherent, that is, they do not require prior knowledge of the network topology. We also propose a computationally-efficient concatenation scheme. The rate achieved by our concatenated codes is characterized by a Zyablov-type lower bound. We provide a generalized minimum-distance decoding algorithm which decodes up to half the minimum distance of the concatenated codes. The end-to-end nature of our design enables our codes to be overlaid on the classical distributed random linear network codes [1]. Furthermore, the potentially intensive computation at internal nodes for the link-by-link error-correction is un-necessary based on our design.