Change search
Link to record
Permanent link

Direct link
BETA
Publications (9 of 9) Show all publications
Wang, Q. & Skoglund, M. (2019). Symmetric Private Information Retrieval from MDS Coded Distributed Storage With Non-Colluding and Colluding Servers. IEEE Transactions on Information Theory, 65(8), 5160-5175
Open this publication in new window or tab >>Symmetric Private Information Retrieval from MDS Coded Distributed Storage With Non-Colluding and Colluding Servers
2019 (English)In: IEEE Transactions on Information Theory, ISSN 0018-9448, E-ISSN 1557-9654, Vol. 65, no 8, p. 5160-5175Article in journal (Refereed) Published
Abstract [en]

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 PIR (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, K-C)-MDS storage code. The randomness is distributedly stored such that any K-C 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 - K-C/N, when the amount of the total randomness of distributed nodes (unavailable at the user) is at least K-C/N-K-C 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 K-C = 1, i.e., the database is replicated at each node, the capacity of TSPIR is shown to be 1 - T/N, with the ratio of the total randomness size relative to the file size be at least T/N-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 - K-C+T-1/N, with total randomness at least K-C+T-1/N-K-C-T+1 times the file size. The MDS-TSPIR capacity for general schemes remains an open problem.

Place, publisher, year, edition, pages
Institute of Electrical and Electronics Engineers (IEEE), 2019
Keywords
Private information retrieval, capacity, colluding servers, distributed storage, MDS codes
National Category
Communication Systems
Identifiers
urn:nbn:se:kth:diva-255728 (URN)10.1109/TIT.2019.2903206 (DOI)000476740600035 ()2-s2.0-85069527144 (Scopus ID)
Note

QC 20190814

Available from: 2019-08-14 Created: 2019-08-14 Last updated: 2019-08-14Bibliographically approved
Wang, Q., Sun, H. & Skoglund, M. (2019). The -error capacity of symmetric PIR with byzantine adversaries. In: 2018 IEEE Information Theory Workshop, ITW 2018: . Paper presented at 2018 IEEE Information Theory Workshop, ITW 2018, 25 November 2018 through 29 November 2018. Institute of Electrical and Electronics Engineers Inc.
Open this publication in new window or tab >>The -error capacity of symmetric PIR with byzantine adversaries
2019 (English)In: 2018 IEEE Information Theory Workshop, ITW 2018, Institute of Electrical and Electronics Engineers Inc. , 2019Conference paper, Published paper (Refereed)
Abstract [en]

The capacity of symmetric private information retrieval with K messages, N servers (out of which any T may collude), and an omniscient Byzantine adversary (who can corrupt any B answers) is shown to be 1 − T +2 B N [1], under the requirement of zero probability of error. In this work, we show that by weakening the adversary slightly (either providing secret low rate channels between the servers and the user, or limiting the observation of the adversary), and allowing vanishing probability of error, the capacity increases to 1 − T + B N

Place, publisher, year, edition, pages
Institute of Electrical and Electronics Engineers Inc., 2019
Keywords
Information theory, Capacity increase, Error capacity, Low rates, Private information retrieval, Probability of errors, Errors
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
urn:nbn:se:kth:diva-248276 (URN)10.1109/ITW.2018.8613332 (DOI)2-s2.0-85062090056 (Scopus ID)9781538635995 (ISBN)
Conference
2018 IEEE Information Theory Workshop, ITW 2018, 25 November 2018 through 29 November 2018
Note

QC 20190408

Available from: 2019-04-08 Created: 2019-04-08 Last updated: 2019-04-08Bibliographically approved
Wang, Q. & Jaggi, S. (2018). End-to-End Error-Correcting Codes on Networks With Worst-Case Bit Errors. IEEE Transactions on Information Theory, 64(6), 4467-4479
Open this publication in new window or tab >>End-to-End Error-Correcting Codes on Networks With Worst-Case Bit Errors
2018 (English)In: IEEE Transactions on Information Theory, ISSN 0018-9448, E-ISSN 1557-9654, Vol. 64, no 6, p. 4467-4479Article in journal (Refereed) Published
Abstract [en]

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, and so on, 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 Hamming-type, 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 error-correction. 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 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. 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.

Place, publisher, year, edition, pages
Institute of Electrical and Electronics Engineers (IEEE), 2018
Keywords
Network error-correcting, worst-case errors, upper and lower bounds
National Category
Communication Systems
Identifiers
urn:nbn:se:kth:diva-230484 (URN)10.1109/TIT.2018.2817801 (DOI)000432983500032 ()2-s2.0-85044335364 (Scopus ID)
Funder
Knut and Alice Wallenberg Foundation
Note

QC 20180614

Available from: 2018-06-14 Created: 2018-06-14 Last updated: 2018-11-23Bibliographically approved
Wu, H., Wang, Q. & Flierl, M. (2018). Identification Rates for Block-correlated Gaussian Sources. In: Matthews, M B (Ed.), 2018 CONFERENCE RECORD OF 52ND ASILOMAR CONFERENCE ON SIGNALS, SYSTEMS, AND COMPUTERS: . Paper presented at 52nd Asilomar Conference on Signals, Systems, and Computers, OCT 28-NOV 01, 2018, Pacific Grove, CA (pp. 2114-2118). IEEE
Open this publication in new window or tab >>Identification Rates for Block-correlated Gaussian Sources
2018 (English)In: 2018 CONFERENCE RECORD OF 52ND ASILOMAR CONFERENCE ON SIGNALS, SYSTEMS, AND COMPUTERS / [ed] Matthews, M B, IEEE , 2018, p. 2114-2118Conference paper, Published paper (Refereed)
Abstract [en]

Among many current data processing systems, the objectives are often not the reproduction of data, but to compute some answers based on the data responding to sonic queries. The similarity identification task is to identify the items in a database which are similar to a given query item regarding to a certain metric. The problem of compression for similarity identification has been studied in [1]. Unlike classic compression problems, the focus is not on reconstructing the original data. Instead, the compression rate is determined by the desired reliability of the answers. Specifically, the information measure identification rate of a compression scheme characterizes the minimum compression rate that can be achieved which guarantees reliable answers with respect to a given similarity threshold. In this paper, we study the component-based quadratic similarity identification for correlated sources. The blocks are first decorrelated by Karhunen-Loeve transform. Then, the decorrelated data is processed by a distinct D-admissible system for each component. We derive the identification rate of component-based scheme for block correlated Gaussian sources. In addition, we characterize the identification rate of a special setting where any information regarding to the component similarity thresholds is unknown while only the similarity threshold of the whole scheme is given. Furthermore, we prove that block-correlated Gaussian sources are the "most difficult" to code under the special setting.

Place, publisher, year, edition, pages
IEEE, 2018
Series
Conference Record of the Asilomar Conference on Signals Systems and Computers, ISSN 1058-6393
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:kth:diva-252677 (URN)10.1109/ACSSC.2018.8645306 (DOI)000467845100373 ()2-s2.0-85062960125 (Scopus ID)978-1-5386-9218-9 (ISBN)
Conference
52nd Asilomar Conference on Signals, Systems, and Computers, OCT 28-NOV 01, 2018, Pacific Grove, CA
Note

QC 20190603

Available from: 2019-06-03 Created: 2019-06-03 Last updated: 2019-07-31Bibliographically approved
Wang, Q. & Skoglund, M. (2018). Linear symmetric private information retrieval for MDS coded distributed storage with colluding servers. In: 2017 IEEE Information Theory Workshop (ITW): . Paper presented at 2017 IEEE Information Theory Workshop, ITW 2017, 6 November 2017 through 10 November 2017 (pp. 71-75). Institute of Electrical and Electronics Engineers (IEEE)
Open this publication in new window or tab >>Linear symmetric private information retrieval for MDS coded distributed storage with colluding servers
2018 (English)In: 2017 IEEE Information Theory Workshop (ITW), Institute of Electrical and Electronics Engineers (IEEE), 2018, p. 71-75Conference paper, Published paper (Refereed)
Abstract [en]

The problem of symmetric private information retrieval (SPIR) from a coded database which is distributively stored among colluding servers is studied. Specifically, the database comprises K files, which are stored among N servers using an (N, M)-MDS storage code. A user wants to retrieve one file from the database by communicating with the N servers, without revealing the identity of the desired file to any server. Furthermore, the user shall learn nothing about the other K - 1 files in the database. In the T-colluding SPIR problem (hence called TSPIR), 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. We show that for linear schemes, the information-theoretic capacity of the MDS-TSPIR problem, defined as the maximum number of information bits of the desired file retrieved per downloaded bit, equals 1 - M+T-1/N, if the servers share common randomness (unavailable at the user) with amount at least M+T-1/N-M-T+1 times the file size. Otherwise, the capacity equals zero.

Place, publisher, year, edition, pages
Institute of Electrical and Electronics Engineers (IEEE), 2018
Series
EEE International Symposium on Information Theory - Proceedings
National Category
Telecommunications
Identifiers
urn:nbn:se:kth:diva-238280 (URN)10.1109/ITW.2017.8277997 (DOI)2-s2.0-85046363054 (Scopus ID)9781509030972 (ISBN)
Conference
2017 IEEE Information Theory Workshop, ITW 2017, 6 November 2017 through 10 November 2017
Note

QC 20181121

Available from: 2018-11-21 Created: 2018-11-21 Last updated: 2019-08-30Bibliographically approved
Wu, H., Wang, Q. & Flierl, M. (2018). PREDICTION-BASED SIMILARITY IDENTIFICATION FOR AUTOREGRESSIVE PROCESSES. In: 2018 IEEE GLOBAL CONFERENCE ON SIGNAL AND INFORMATION PROCESSING (GLOBALSIP 2018): . Paper presented at IEEE Global Conference on Signal and Information Processing (GlobalSIP), NOV 26-29, 2018, Anaheim, CA (pp. 266-270). IEEE
Open this publication in new window or tab >>PREDICTION-BASED SIMILARITY IDENTIFICATION FOR AUTOREGRESSIVE PROCESSES
2018 (English)In: 2018 IEEE GLOBAL CONFERENCE ON SIGNAL AND INFORMATION PROCESSING (GLOBALSIP 2018), IEEE , 2018, p. 266-270Conference paper, Published paper (Refereed)
Abstract [en]

The task of similarity identification is to identify items in a database which are similar to a given query item for a given metric. The identification rate of a compression scheme characterizes the minimum rate that can be achieved which guarantees reliable answers with respect to a given similarity threshold [1]. In this paper, we study a prediction-based quadratic similarity identification for autoregressive processes. We use an ideal linear predictor to remove linear dependencies in autoregressive processes. The similarity identification is conducted on the residuals. We show that the relation between the distortion of query and database processes and the distortion of their residuals is characterized by a sequence of eigenvalues. We derive the identification rate of our prediction-based approach for autoregressive Gaussian processes. We characterize the identification rate for the special case where only the smallest value in the sequence of eigenvalues is required to be known and derive its analytical upper bound by approximating a sequence of matrices with a sequence of Toeplitz matrices.

Place, publisher, year, edition, pages
IEEE, 2018
Series
IEEE Global Conference on Signal and Information Processing, ISSN 2376-4066
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:kth:diva-249832 (URN)10.1109/GlobalSIP.2018.8646407 (DOI)000462968100054 ()2-s2.0-85063103300 (Scopus ID)978-1-7281-1295-4 (ISBN)
Conference
IEEE Global Conference on Signal and Information Processing (GlobalSIP), NOV 26-29, 2018, Anaheim, CA
Note

QC 20190423

Available from: 2019-04-23 Created: 2019-04-23 Last updated: 2019-04-23Bibliographically approved
Wang, Q. & Skoglund, M. (2018). Secure Private Information Retrieval from Colluding Databases with Eavesdroppers. In: 2018 IEEE International Symposium on Information Theory (ISIT): . Paper presented at 2018 IEEE International Symposium on Information Theory, ISIT 2018, Vail, United States, 17 June 2018 through 22 June 2018 (pp. 2456-2460). Institute of Electrical and Electronics Engineers (IEEE)
Open this publication in new window or tab >>Secure Private Information Retrieval from Colluding Databases with Eavesdroppers
2018 (English)In: 2018 IEEE International Symposium on Information Theory (ISIT), Institute of Electrical and Electronics Engineers (IEEE), 2018, p. 2456-2460Conference paper, Published paper (Refereed)
Abstract [en]

The problem of private information retrieval (PIR) is to retrieve one message out of K messages replicated at N databases, without revealing the identity of the desired message to the databases. We consider the problem of PIR with colluding databases and eavesdroppers, named ETPIR. Specifically, any T out of N databases may collude, that is, they may communicate their interactions with the user to guess the identity of the requested message. An eavesdropper is curious to know the content of the messages and can tap in on the incoming and outgoing transmissions of any E databases with the user. The databases share some common randomness unknown to the eavesdropper and the user, and use the common randomness to generate the answers, such that the eavesdropper can learn no information about the K messages. The capacity is defined as the maximum retrieval rate, i.e. the number of information bits of the desired message retrieved per downloaded bit. In our previous work [1], we found that when Egeq T, the capacity equals 1-frac E N. In this work, we focus on the case when Eleq T. We find an outer bound (converse bound) and an inner bound (achievability) on the optimal achievable rate. The gap between the derived inner and outer bounds vanishes as the number of messages K tends to infinity.

Place, publisher, year, edition, pages
Institute of Electrical and Electronics Engineers (IEEE), 2018
Series
IEEE International Symposium on Information Theory - Proceedings, ISSN 2157-8095
National Category
Communication Systems
Identifiers
urn:nbn:se:kth:diva-234699 (URN)10.1109/ISIT.2018.8437848 (DOI)2-s2.0-85052432049 (Scopus ID)9781538647806 (ISBN)
Conference
2018 IEEE International Symposium on Information Theory, ISIT 2018, Vail, United States, 17 June 2018 through 22 June 2018
Note

QC 20180910

Available from: 2018-09-10 Created: 2018-09-10 Last updated: 2018-09-10Bibliographically approved
Wang, Q., Sun, H. & Skoglund, M. (2018). The epsilon-error Capacity of Symmetric PIR with Byzantine Adversaries. In: 2018 IEEE INFORMATION THEORY WORKSHOP (ITW): . Paper presented at IEEE Information Theory Workshop (ITW), NOV 25-29, 2018, Guangzhou, PEOPLES R CHINA (pp. 575-579). IEEE
Open this publication in new window or tab >>The epsilon-error Capacity of Symmetric PIR with Byzantine Adversaries
2018 (English)In: 2018 IEEE INFORMATION THEORY WORKSHOP (ITW), IEEE , 2018, p. 575-579Conference paper, Published paper (Refereed)
Abstract [en]

The capacity of symmetric private information retrieval with K messages, N servers (out of which any T may collude), and an omniscient Byzantine adversary (who can corrupt any B answers) is shown to be 1 - T+2B/N [1], under the requirement of zero probability of error. In this work, we show that by weakening the adversary slightly (either providing secret low rate channels between the servers and the user, or limiting the observation of the adversary), and allowing vanishing probability of error, the capacity increases to 1 - T+B/N.

Place, publisher, year, edition, pages
IEEE, 2018
Series
Information Theory Workshop, ISSN 2475-420X
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:kth:diva-252669 (URN)10.1109/ITW.2018.8613332 (DOI)000467849900116 ()2-s2.0-85062090056 (Scopus ID)978-1-5386-3599-5 (ISBN)
Conference
IEEE Information Theory Workshop (ITW), NOV 25-29, 2018, Guangzhou, PEOPLES R CHINA
Note

QC 20190610

Available from: 2019-06-10 Created: 2019-06-10 Last updated: 2019-06-10Bibliographically approved
Wu, H., Wang, Q. & Flierl, M. (2017). Tree-Structured Vector Quantization for Similarity Queries. In: Bilgin, A Marcellin, MW SerraSagrista, J Storer, JA (Ed.), 2017 Data Compression Conference (DCC): . Paper presented at Data Compression Conference (DCC), APR 04-07, 2017, Snowbird, UT (pp. 467-467). IEEE Computer Society
Open this publication in new window or tab >>Tree-Structured Vector Quantization for Similarity Queries
2017 (English)In: 2017 Data Compression Conference (DCC) / [ed] Bilgin, A Marcellin, MW SerraSagrista, J Storer, JA, IEEE Computer Society, 2017, p. 467-467Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
IEEE Computer Society, 2017
Series
IEEE Data Compression Conference, ISSN 1068-0314
National Category
Communication Systems
Identifiers
urn:nbn:se:kth:diva-243540 (URN)10.1109/DCC.2017.72 (DOI)000404240300077 ()978-1-5090-6721-3 (ISBN)
Conference
Data Compression Conference (DCC), APR 04-07, 2017, Snowbird, UT
Note

QC 20190208

Available from: 2019-02-08 Created: 2019-02-08 Last updated: 2019-02-08Bibliographically approved
Organisations
Identifiers
ORCID iD: ORCID iD iconorcid.org/0000-0001-9471-1409

Search in DiVA

Show all publications