Assistant Professor in Computer Science in the CSE department at UTA.
@article{Chou2024Multiuser, author = {Chou, R\'emi and Bloch, Matthieu R.}, journal = {IEEE Transactions on Information Theory}, title = {Multiuser Commitment over Noisy Channels}, year = {2025}, month = nov, number = {11}, pages = {1557-9654}, volume = {71}, doi = {10.1109/TIT.2025.3608081}, eprint = {2411.05987}, groups = {NSF1955401}, howpublished = {accepted to \emph{IEEE Transactions on Information Theory}} }
Consider a sequence Xn of length n emitted by a Discrete Memoryless Source (DMS) with unknown distribution pX. The objective is to construct a lossless source code that maps Xn to a sequence Yˆm of length m that is indistinguishable, in terms of Kullback-Leibler divergence, from a sequence emitted by another DMS with known distribution pY. The main result is the existence of a coding scheme that performs this task with an optimal ratio m/n equal to H(X)/H(Y), the ratio of the Shannon entropies of the two distributions, as n goes to infinity. The coding scheme overcomes the challenges created by the lack of knowledge about pX by relying on a sufficiently fine estimation of H(X), followed by an appropriately designed type-based source coding that jointly performs source resolvability and universal lossless source coding. The result recovers and extends previous results that either assume pX or pY uniform, or pX known. The price paid for these generalizations is the use of common randomness with vanishing rate, whose length roughly scales as the square root of n. By allowing common randomness strictly larger than the square root of n but still negligible compared to n, a constructive low-complexity encoding and decoding counterpart to the main result is also provided for binary sources by means of polar codes.
@article{Chou2018, author = {Chou, R\'emi A. and Bloch, Matthieu and Yener, Aylin}, journal = ieee_j_it, title = {Universal Covertness for Discrete Memoryless Sources}, year = {2021}, month = aug, number = {8}, pages = {1557-9654}, volume = {67}, doi = {10.1109/TIT.2021.3091381}, eprint = {1808.05612}, file = {:2021-Chou-IEEETransIT-Universal Covertness for Discrete Memoryless Sources.pdf:PDF}, howpublished = {accepted to \emph{IEEE Transactions on Information Theory}} }
We design polar codes for empirical coordination and strong coordination in two-node networks. Our constructions hinge on the fact that polar codes enable explicit low-complexity schemes for soft covering. We leverage this property to propose explicit and low-complexity coding schemes that achieve the capacity regions of both empirical coordination and strong coordination for sequences of actions taking value in an alphabet of prime cardinality. Our results improve previously known polar coding schemes, which (i) were restricted to uniform distributions and to actions obtained via binary symmetric channels for strong coordination, (ii) required a non-negligible amount of common randomness for empirical coordination, and (iii) assumed that the simulation of discrete memoryless channels could be perfectly implemented. As a by-product of our results, we obtain a polar coding scheme that achieves channel resolvability for an arbitrary discrete memoryless channel whose input alphabet has prime cardinality.
@article{Chou2016a, author = {Chou, R\'emi A. and Bloch, Matthieu R. and Kliewer, Joerg}, journal = ieee_j_it, title = {Empirical and Strong Coordination via Soft Covering with Polar Codes}, year = {2018}, issn = {0018-9448}, month = jul, number = {7}, pages = {5087-5100}, volume = {64}, doi = {10.1109/TIT.2018.2817519}, eprint = {1608.08474}, groups = {Coordination of networks, Polar codes}, howpublished = {accepted to \emph{IEEE Transactions on Information Theory}} }
We study the problem of achieving strong secrecy over wiretap channels at negligible cost, in the sense of maintaining the overall communication rate of the same channel without secrecy constraints. Specifically, we propose and analyze two source-channel coding architectures, in which secrecy is achieved by multiplexing public and confidential messages. In both cases, our main contribution is to show that secrecy can be achieved without compromising communication rate and by requiring only randomness of asymptotically vanishing rate. Our first source-channel coding architecture relies on a modified wiretap channel code, in which randomization is performed using the output of a source code. In contrast, our second architecture relies on a standard wiretap code combined with a modified source code termed uniform compression code, in which a small shared secret seed is used to enhance the uniformity of the source code output. We carry out a detailed analysis of uniform compression codes and characterize the optimal size of the shared seed.
@article{Chou2014b, author = {Chou, R\'emi A. and Vellambi, B. N. and Bloch, M. R. and Kliewer, J.}, journal = ieee_j_it, title = {Coding Schemes for Achieving Strong Secrecy at Negligible Cost}, year = {2017}, issn = {0018-9448}, month = mar, number = {3}, pages = {1858-1873}, volume = {63}, creationdate = {2014-06-15T00:00:00}, doi = {10.1109/TIT.2016.2645225}, eprint = {1508.07920}, groups = {Wiretap channels}, keywords = {channel coding;cryptography;message authentication;multiplexing;source coding;telecommunication security;asymptotically vanishing rate randomness;confidential messages;modified source code;modified wiretap channel code;multiplexing;optimal size characterization;public messages;shared secret seed;source code output uniformity enhancement;source-channel coding architectures;strong secrecy problem;uniform compression code;Channel models;Decoding;Encoding;Multiplexing;Physical layer;Security;Virtual private networks;Wiretap channel;multiplexing;physical-layer security;source coding}, owner = {mattbloch} }
We develop a low-complexity polar coding scheme for the discrete memoryless broadcast channel with confidential messages under strong secrecy and randomness constraints. Our scheme extends previous work by using an optimal rate of uniform randomness in the stochastic encoder, and avoiding assumptions regarding the symmetry or degraded nature of the channels. The price paid for these extensions is that the encoder and the decoders are required to share a secret seed of negligible size and to increase the block length through chaining. We also highlight a close conceptual connection between the proposed polar coding scheme and a random binning proof of the secrecy capacity region.
@article{Chou2014d, author = {Chou, R\'emi A. and Bloch, Matthieu R}, journal = ieee_j_it, title = {Polar Coding for the Broadcast Channel with Confidential Messages: A Random Binning Analogy}, year = {2016}, issn = {0018-9448}, month = may, number = {5}, pages = {2410-2429}, volume = {62}, creationdate = {2014-10-31T00:00:00}, doi = {10.1109/TIT.2016.2539145}, eprint = {1411.0281}, file = {:2016-Chou-IEEETransIT.pdf:PDF}, groups = {Polar codes, Wiretap codes}, keywords = {Channel models;Decoding;Degradation;Encoding;Random variables;Security;Stochastic processes;Polar codes;physical-layer security;random binning;strong secrecy;wiretap channel}, owner = {mattbloch} }
Practical implementations of secret-key generation are often based on sequential strategies, which handle reliability and secrecy in two successive steps, called reconciliation and privacy amplification. In this paper, we propose an alternative approach based on polar codes that jointly deals with reliability and secrecy. Specifically, we propose secret-key capacityachieving polar coding schemes for the following models: (i) the degraded binary memoryless source (DBMS) model with rateunlimited public communication, (ii) the DBMS model with oneway rate-limited public communication, (iii) the 1-to-m broadcast model and (iv) the Markov tree model with uniform marginals. For models (i) and (ii) our coding schemes remain valid for nondegraded sources, although they may not achieve the secret-key capacity. For models (i), (ii) and (iii), our schemes rely on preshared secret seed of negligible rate; however, we provide special cases of these models for which no seed is required. Finally, we show an application of our results to secrecy and privacy for biometric systems. We thus provide the first examples of lowcomplexity secret-key capacity-achieving schemes that are able to handle vector quantization for model (ii), or multiterminal communication for models (iii) and (iv).
@article{Chou2013b, author = {Chou, R\'emi A. and Bloch, Matthieu R and Abbe, Emmanuel}, journal = ieee_j_it, title = {Polar Coding for Secret-Key Generation}, year = {2015}, issn = {0018-9448}, month = nov, number = {11}, pages = {6213-6237}, volume = {61}, creationdate = {2013-10-09T00:00:00}, doi = {10.1109/TIT.2015.2471179}, eprint = {1305.4746}, file = {:2015-Chou-IEEETransIT-Polar Coding for Secret-Key Generation.pdf:PDF}, groups = {Secret key agreement, Polar codes}, keywords = {Biological system modeling;Decoding;Encoding;Markov processes;Privacy;Protocols;Reliability}, owner = {mattbloch} }
For a discrete or a continuous source model, we study the problem of secret-key generation with one round of rate-limited public communication between two legitimate users. Although we do not provide new bounds on the wiretap secret-key (WSK) capacity for the discrete source model, we use an alternative achievability scheme that may be useful for practical applications. As a side result, we conveniently extend known bounds to the case of a continuous source model. Specifically, we consider a sequential key-generation strategy, that implements a rate-limited reconciliation step to handle reliability, followed by a privacy amplification step performed with extractors to handle secrecy. We prove that such a sequential strategy achieves the best known bounds for the rate-limited WSK capacity (under the assumption of degraded sources in the case of two-way communication). However, we show that, unlike the case of rate-unlimited public communication, achieving the reconciliation capacity in a sequential strategy does not necessarily lead to achieving the best known bounds for the WSK capacity. Consequently, reliability and secrecy can be treated successively but not independently, thereby exhibiting a limitation of sequential strategies for rate-limited public communication. Nevertheless, we provide scenarios for which reliability and secrecy can be treated successively and independently, such as the two-way rate-limited SK capacity, the one-way rate-limited WSK capacity for degraded binary symmetric sources, and the one-way rate-limited WSK capacity for Gaussian degraded sources.
@article{Chou2012a, author = {Chou, R\'emi A. and Bloch, Matthieu R}, journal = ieee_j_it, title = {Separation of Reliability and Secrecy in Rate-Limited Secret Key-Distillation}, year = {2014}, month = aug, number = {8}, pages = {4941--4957}, volume = {60}, citeseerurl = {1210.4482}, creationdate = {2012-09-24T00:00:00}, doi = {10.1109/TIT.2014.2323246}, eprint = {1210.4482}, groups = {Secret key agreement}, owner = {mattbloch} }
Consider a commitment protocol between two parties, Alice and Bob, in which Alice may (i) commit to a message using a non-redundant discrete memoryless channel whose outputs are observed by Bob; and (ii) later reveal her committed message to Bob who must decide whether Alice is revealing the message she actually committed to. A commitment protocol should meet three standard requirements: concealment, bindingness, and soundness, to ensure that no party may act dishonestly. Our objective is to study whether one can enforce a fourth requirement that would allow Alice to retract a commitment before the reveal phase starts without Bob detecting that she ever participated in the commit phase of the protocol. We positively answer this question and characterize the commitment capacity for such a setting by relying on tools developed for covert communication.
@inproceedings{Chou2023Retractable, author = {Chou, R\'emi A. and Bloch, Matthieu R.}, booktitle = ieee_itw, title = {Retractable Commitment}, year = {2023}, address = {Saint-Malo, France}, month = apr, pages = {260--265}, doi = {10.1109/ITW55543.2023.10161683}, file = {:2023-Chou-ITW-Retractable Commitment over Noisy Channels.pdf:PDF}, groups = {NSF1955401}, howpublished = {accepted to \emph{IEEE Information Theory Workshop}} }
The problem of multi-user commitment is one in which multiple users first commit to individual messages with a bookmaker and later reveal their messages. The objective of the bookmaker is then to decide whether the revealed messages correspond to the committed messages. We study a specific multi-user commitment model in which the users and the bookmaker have access to a noiseless channel, as well as a noisy multiple-access channel whose inputs are controlled by the users and whose output is observed by the bookmaker. When the users are non-colluding and the channel is non-redundant, we fully characterize the commitment capacity region. When the users are colluding, we derive an achievable region and a tight converse for the sum-rate. In both cases our proposed achievable commitment schemes are constructive.
@inproceedings{Chou2022Commitment, author = {Chou, R\'emi and Bloch, Matthieu R.}, booktitle = {Proc. of 58th Annual Allerton Conference on Communication, Control, and Computing}, title = {Commitment over Multiple-Access Channels}, year = {2022}, address = {Monticello, IL}, month = sep, doi = {10.1109/Allerton49937.2022.9929405}, file = {:2022-Chou-Allerton-Commitment over Multiple-Access Channels.pdf:PDF}, howpublished = {accepted to \emph{Allerton conference}} }
Consider a sequence S of length n emitted by a Discrete Memoryless Source (DMS) with unknown distribution p. We wish to construct a lossless source code that maps S to a sequence S’ of minimal length m such that S’ approximates in terms of Kullback-Leibler divergence a sequence emitted by another DMS with known distribution q. Our main result is the existence of a coding scheme that performs such a task with an asymptotically optimal compression rate, i.e., such that the limit of m/n is H(p)/H(q) as n goes to infinity. Our coding scheme overcomes the challenges created by the lack of knowledge about p by relying on a sufficiently fine estimation of H(p), followed by an appropriately designed type-based compression that jointly performs source resolvability and universal lossless source coding. Our result recovers several previous results that either assume p uniform, or q uniform, or p known. The price paid for these generalizations is the use of common randomness with vanishing rate. We further determine that the length of the latter roughly scales as the square root of n, by an analysis of second order asymptotics and error exponents.
@inproceedings{Chou2016, author = {Chou, R\'emi A. and Bloch, Matthieu R. and Yener, Aylin}, booktitle = {54th Annual Allerton Conference on Communication, Control, and Computing (Allerton)}, title = {Universal covertness for Discrete Memoryless Sources}, year = {2016}, address = {Monticello, IL}, month = aug, pages = {516-523}, creationdate = {2016-01-26T00:00:00}, doi = {10.1109/ALLERTON.2016.7852275}, groups = {Steganography and covert communications}, keywords = {source coding;DMS;discrete memoryless source;error exponent analysis;second order asymptotic analysis;source resolvability;universal covertness;universal lossless source coding;Decoding;Entropy;Estimation;Random variables;Reliability;Source coding}, owner = {mattbloch} }
We show how to replace some of the randomized decisions in the encoding and decoding of polar codes by deterministic decisions. Specifically, we prove that random decisions on low-entropy bits may be replaced by an argmax decision without any loss of performance. We illustrate the usefulness of this result in the case of polar coding for the Wyner-Ziv problem and for channel coding.
@inproceedings{Chou2015a, author = {Chou, R\'emi A. and Bloch, M. R.}, booktitle = {Proc. of 53rd Annual Allerton Conference on Communication, Control, and Computing}, title = {Using deterministic decisions for low-entropy bits in the encoding and decoding of polar codes}, year = {2015}, address = {Monticello, IL}, month = sep, pages = {1380-1385}, creationdate = {2015-07-07T00:00:00}, doi = {10.1109/ALLERTON.2015.7447169}, file = {:2015-Chou-Allerton-Using_deterministic_decisions_for_low-entropy_bits_in_the_encoding_and_decoding_of_polar_codes.pdf:PDF}, groups = {Polar codes}, keywords = {channel coding;Wyner-Ziv problem;argmax decision;channel coding;deterministic decisions;low-entropy bits;polar codes;Channel coding;Computers;Couplings;Decoding;Distortion;Source coding}, owner = {mattbloch} }
It is known that a sub-linear rate of source-independent random seed (common randomness) can enable the construction of lossless compression codes whose output is nearly uniform under the variational distance (Chou-Bloch-ISIT’13). This work uses finite-blocklength techniques to present an alternate proof that for near-uniform lossless compression, the seed length has to grow strictly larger than n, where n represents the blocklength of the lossless compression code. In the lossy setting, we show the surprising result that a seed is not required to make the encoder output nearly uniform.
@inproceedings{Vellambi2015, author = {Vellambi, Badri N. and Bloch, Matthieu R. and Chou, R\'emi A. and Kliewer, Joerg}, booktitle = ieee_isit, title = {Lossless and Lossy Source Compression with Near-Uniform Outputs: Is Common Randomness Always Required?}, year = {2015}, address = {Hong Kong}, month = jun, pages = {2171--2175}, creationdate = {2015-01-27T00:00:00}, doi = {10.1109/ISIT.2015.7282840}, groups = {Randomness processing}, howpublished = {accepted to \emph{IEEE International Symposium on Information Theory}}, keywords = {Decoding;Distortion;Encoding;Manganese;Random variables;Tin;Finite-blocklength techniques;Lossless coding;Rate-distortion;Source coding}, owner = {mattbloch} }
We design low-complexity polar codes for empirical and strong coordination in two-node network. Our constructions hinge on the observation that polar codes may be used to approximate distribution; which we leverage to prove that nested polar codes achieve the capacity region of empirical coordination and strong coordination.
@inproceedings{Chou2015, author = {Chou, R\'emi A. and Bloch, Matthieu R and Kliewer, Joerg}, booktitle = ieee_isit, title = {Polar Coding for Empirical and Strong Coordination via Distribution Approximation}, year = {2015}, address = {Hong Kong}, month = jun, pages = {1512--1516}, creationdate = {2015-01-27T00:00:00}, doi = {10.1109/ISIT.2015.7282708}, groups = {Polar codes, Coordination of networks}, howpublished = {accepted to \emph{IEEE International Symposium on Information Theory}}, keywords = {Approximation methods;Convergence;Decoding;Encoding;Joints;Probability distribution;Random variables}, owner = {mattbloch} }
We develop a low-complexity and secrecy capacity achieving polar coding scheme for the discrete memoryless wiretap channel. Our scheme extends previous work by using a nearly optimal amount of uniform randomness in the stochastic encoder, and avoiding assumptions regarding the symmetry or degraded nature of the channels. The price paid for these extensions is that the encoder and decoder are required to share a secret seed of negligible size. We also highlight a close conceptual connection between the proposed polar coding scheme and a random binning proof of the secrecy capacity.
@inproceedings{Chou2014e, author = {Chou, R\'emi A. and Bloch, Matthieu R}, booktitle = ieee_itw, title = {Polar Coding for the Broadcast Channel with Confidential Messages}, year = {2015}, address = {Jerusalem, Israel}, month = apr, pages = {1-5}, creationdate = {2014-11-13T00:00:00}, doi = {10.1109/ITW.2015.7133142}, groups = {Wiretap codes, Polar codes}, howpublished = {accepted to \emph{IEEE Information Theory Workshop}}, keywords = {broadcast channels;channel capacity;channel coding;decoding;broadcast channel;channel symmetry;confidential messages;decoder;discrete memoryless wiretap channel;polar coding scheme;secrecy capacity;stochastic encoder;Channel coding;Decoding;Entropy;Joints;Parity check codes;Stochastic processes}, owner = {mattbloch} }
@inproceedings{Chou2014, author = {Chou, R\'emi A. and Bloch, Matthieu R and Kliewer, J\"org}, booktitle = ieee_itw, title = {Low-Complexity Channel Resolvability Codes for the Symmetric Multiple-Access Channel}, year = {2014}, address = {Hobart, Tasmania}, month = nov, pages = {466--470}, creationdate = {2014-01-24T00:00:00}, doi = {10.1109/ITW.2014.6970875}, file = {:2014-Chou-ITW.pdf:PDF}, groups = {Randomness processing}, howpublished = {accepted to \emph{IEEE Information Theory Workhop}}, owner = {mattbloch} }
@inproceedings{Chou2014c, author = {Chou, R\'emi A. and Bloch, Matthieu R}, booktitle = {Proc. of IEEE Conference on Communications and Network Security}, title = {Uniform Distributed Source Coding for the Multiple Access Wiretap Channel}, year = {2014}, address = {San Francisco, CA}, month = oct, pages = {127--132}, creationdate = {2014-07-07T00:00:00}, doi = {10.1109/CNS.2014.6997477}, groups = {Wiretap channels}, howpublished = {accepted at \emph{IEEE Conference on Communications and Network Security: Wokshop on Physical-layer Methods for Wireless Security} (invited)}, owner = {mattbloch} }
@inproceedings{Chou2013c, author = {Chou, R\'emi A. and Bloch, Matthieu R}, booktitle = {Proc. of Global Conference on Signal and Information Processing}, title = {Secret-Key Generation with Arbitrarily Varying Eavesdropper's Channel}, year = {2013}, address = {Austin, TX}, month = sep, pages = {277--280}, creationdate = {2013-10-21T00:00:00}, doi = {10.1109/GlobalSIP.2013.6736869}, groups = {Secret key agreement}, owner = {mattbloch} }
For any lossless fixed-length compression scheme operating at the optimal coding rate, it is known that the encoder output is not uniform in variational distance, which yet might be desirable in some security schemes. In the case of independent and identically distributed (i.i.d.) sources, uniformity in divergence might be achieved if a uniformly distributed sequence, called seed, of length dn negligible compared to the message length n, is shared between the encoder and the decoder. We show that the optimal scaling of dn that jointly ensures an optimal coding rate and a uniform encoder output in divergence, is roughly on the order of sqrt(n). We also develop a near optimal achievability scheme using invertible extractors.
@inproceedings{Chou2013, author = {Chou, R\'emi A. and Bloch, Matthieu R.}, booktitle = ieee_isit, title = {Data compression with nearly uniform ouput}, year = {2013}, address = {Istanbul, Turkey}, month = jul, pages = {1979-1983}, doi = {10.1109/ISIT.2013.6620572}, file = {:Users/mattbloch/Documents/Publications/2013-Chou-ISIT.pdf:PDF}, groups = {Randomness processing}, issn = {2157-8095} }
Practical implementations of secret-key generation are often based on sequential strategies, which handle reliability and secrecy in two successive steps, called reconciliation and privacy amplification. In this paper, we propose an alternative scheme based on polar coding that jointly deals with reliability and secrecy. We study a binary degraded symmetric discrete memoryless source model with uniform marginals, and assume one-way rate-limited public communication between two legitimate users. Specifically, we propose secret-key capacity-achieving polar coding schemes, in which users rely on pre-shared secret seed of negligible rate. For the model studied, we thus provide the first example of low-complexity secret-key capacity-achieving scheme that handles vector quantization, for rate-limited public communication. Furthermore, we provide examples for which no seed is required.
@inproceedings{Chou2013a, author = {Chou, R\'emi A. and Bloch, Matthieu R. and Abbe, Emmanuel}, booktitle = ieee_itw, title = {Polar Coding for Secret-Key Generation}, year = {2013}, address = {Sevilla, Spain}, month = apr, pages = {1-5}, creationdate = {2013-03-07T00:00:00}, doi = {10.1109/ITW.2013.6691225}, eprint = {1305.4746}, groups = {Secret key agreement, Polar codes}, howpublished = {accepted to \emph{IEEE Information Theory Workshop}}, owner = {mattbloch} }
This paper proposes a proof-of-principle design of a secret key generation system along with the desirable secrecy analysis to guarantee information-theoretic security. We conduct physical experiments on programmable radios in an indoor environment to analyze the statistical characteristics of the induced source that we employ to generate secret keys. We also provide a generic security analysis of the system, and we give an estimate of the achievable secret key rates for a target information leakage in the finite block-length regime.
@inproceedings{Pierrot2013a, author = {Pierrot, Alexandre J. and Chou, R\'emi A. and Bloch, Matthieu R.}, booktitle = {Proc. of Signal IEEE 4th Workshop on Signal Processing Advances in Wireless Communications}, title = {Experimental Aspects of Secret-Key Generation in Indoor Wireless Environments}, year = {2013}, month = apr, creationdate = {2013-02-13T00:00:00}, doi = {10.1109/SPAWC.2013.6612134}, file = {:../Publications/2013-Pierrot-SPAWC.pdf:PDF}, groups = {Experimental systems}, howpublished = {accepted to \emph{IEEE Workshop on Signal Processing Advances in Wireless Communications}}, owner = {mattbloch} }
We study the problem of key-distillation for a source model, with a one-way and rate-limited public communication between two legitimate users. Although, the secret-key capacity is already known, we provide an alternative achievability scheme, that directly translates into practical designs. We consider a sequential key-distillation strategy, which consists of a reconciliation phase followed by a privacy amplification phase performed with extractors. We determine the reconciliation capacity and show that, for a degraded source, such a sequential strategy leads to an optimal key-distillation strategy that achieves the secret-key capacity. We illustrate our results in the case of a binary source model.
@inproceedings{Chou2012, author = {Chou, R\'emi A. and Bloch, Matthieu R.}, booktitle = ieee_isit, title = {One-way rate-limited sequential key-distillation}, year = {2012}, address = {Cambridge, MA}, month = jul, pages = {1777--1781}, creationdate = {2012-08-30T00:00:00}, doi = {10.1109/ISIT.2012.6283584}, file = {:2012-Chou-ISIT.pdf:PDF}, groups = {Secret key agreement}, owner = {mattbloch} }