BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Raymond W. Yeung

Raymond W. Yeung appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Information Theorymath.ITCryptography and SecurityDiscrete Mathematicsmath.CO

Catalog footprint

What is connected

12works
5topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

12 published item(s)

preprint2022arXiv

Proving Information Inequalities and Identities with Symbolic Computation

Proving linear inequalities and identities of Shannon's information measures, possibly with linear constraints on the information measures, is an important problem in information theory. For this purpose, ITIP and other variant algorithms have been developed and implemented, which are all based on solving a linear program (LP). In particular, an identity $f = 0$ is verified by solving two LPs, one for $f \ge 0$ and one for $f \le 0$. In this paper, we develop a set of algorithms that can be implemented by symbolic computation. Based on these algorithms, procedures for verifying linear information inequalities and identities are devised. Compared with LP-based algorithms, our procedures can produce analytical proofs that are both human-verifiable and free of numerical errors. Our procedures are also more efficient computationally. For constrained inequalities, by taking advantage of the algebraic structure of the problem, the size of the LP that needs to be solved can be significantly reduced. For identities, instead of solving two LPs, the identity can be verified directly with very little computation.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Secure Network Function Computation for Linear Functions -- Part I: Source Security

In this paper, we put forward secure network function computation over a directed acyclic network. In such a network, a sink node is required to compute with zero error a target function of which the inputs are generated as source messages at multiple source nodes, while a wiretapper, who can access any one but not more than one wiretap set in a given collection of wiretap sets, is not allowed to obtain any information about a security function of the source messages. The secure computing capacity for the above model is defined as the maximum average number of times that the target function can be securely computed with zero error at the sink node with the given collection of wiretap sets and security function for one use of the network. The characterization of this capacity is in general overwhelmingly difficult. In the current paper, we consider securely computing linear functions with a wiretapper who can eavesdrop any subset of edges up to a certain size r, referred to as the security level, with the security function being the identity function. We first prove an upper bound on the secure computing capacity, which is applicable to arbitrary network topologies and arbitrary security levels. When the security level r is equal to 0, our upper bound reduces to the computing capacity without security consideration. We discover the surprising fact that for some models, there is no penalty on the secure computing capacity compared with the computing capacity without security consideration. We further obtain an equivalent expression of the upper bound by using a graph-theoretic approach, and accordingly we develop an efficient approach for computing this bound. Furthermore, we present a construction of linear function-computing secure network codes and obtain a lower bound on the secure computing capacity.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Weakly Secure Symmetric Multilevel Diversity Coding

Multilevel diversity coding is a classical coding model where multiple mutually independent information messages are encoded, such that different reliability requirements can be afforded to different messages. It is well known that {\em superposition coding}, namely separately encoding the independent messages, is optimal for symmetric multilevel diversity coding (SMDC) (Yeung-Zhang 1999). In the current paper, we consider weakly secure SMDC where security constraints are injected on each individual message, and provide a complete characterization of the conditions under which superposition coding is sum-rate optimal. Two joint coding strategies, which lead to rate savings compared to superposition coding, are proposed, where some coding components for one message can be used as the encryption key for another. By applying different variants of Han's inequality, we show that the lack of opportunity to apply these two coding strategies directly implies the optimality of superposition coding. It is further shown that under a set of particular security constraints, one of the proposed joint coding strategies can be used to construct a code that achieves the optimal rate region.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Alphabet Size Reduction for Secure Network Coding: A Graph Theoretic Approach

We consider a communication network where there exist wiretappers who can access a subset of channels, called a wiretap set, which is chosen from a given collection of wiretap sets. The collection of wiretap sets can be arbitrary. Secure network coding is applied to prevent the source information from being leaked to the wiretappers. In secure network coding, the required alphabet size is an open problem not only of theoretical interest but also of practical importance, because it is closely related to the implementation of such coding schemes in terms of computational complexity and storage requirement. In this paper, we develop a systematic graph-theoretic approach for improving Cai and Yeung's lower bound on the required alphabet size for the existence of secure network codes. The new lower bound thus obtained, which depends only on the network topology and the collection of wiretap sets, can be significantly smaller than Cai and Yeung's lower bound. A polynomial-time algorithm is devised for efficient computation of the new lower bound.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Finite-Length Analysis of BATS Codes

BATS codes were proposed for communication through networks with packet loss. A BATS code consists of an outer code and an inner code. The outer code is a matrix generation of a fountain code, which works with the inner code that comprises random linear coding at the intermediate network nodes. In this paper, the performance of finite-length BATS codes is analyzed with respect to both belief propagation (BP) decoding and inactivation decoding. Our results enable us to evaluate efficiently the finite-length performance in terms of the number of batches used for decoding ranging from 1 to a given maximum number, and provide new insights on the decoding performance. Specifically, for a fixed number of input symbols and a range of the number of batches used for decoding, we obtain recursive formulae to calculate respectively the stopping time distribution of BP decoding and the inactivation probability in inactivation decoding. We also find that both the failure probability of BP decoding and the expected number of inactivations in inactivation decoding can be expressed in a power-sum form where the number of batches appears only as the exponent. This power-sum expression reveals clearly how the decoding failure probability and the expected number of inactivation decrease with the number of batches. When the number of batches used for decoding follows a Poisson distribution, we further derive recursive formulae with potentially lower computational complexity for both decoding algorithms. For the BP decoder that consumes batches one by one, three formulae are provided to characterize the expected number of consumed batches until all the input symbols are decoded.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Partition-Symmetrical Entropy Functions

Let $\cal{N}=\{1,\cdots,n\}$. The entropy function $\bf h$ of a set of $n$ discrete random variables $\{X_i:i\in\cal N\}$ is a $2^n$-dimensional vector whose entries are ${\bf{h}}({\cal{A}})\triangleq H(X_{\cal{A}}),\cal{A}\subset{\cal N} $, the (joint) entropies of the subsets of the set of $n$ random variables with $H(X_\emptyset)=0$ by convention. The set of all entropy functions for $n$ discrete random variables, denoted by $Γ^*_n$, is called the entropy function region for $n$. Characterization of $Γ^*_n$ and its closure $\overline{Γ^*_n}$ are well-known open problems in information theory. They are important not only because they play key roles in information theory problems but also they are related to other subjects in mathematics and physics. In this paper, we consider \emph{partition-symmetrical entropy functions}. Let $p=\{\cal{N}_1,\cdots, \cal{N}_t\}$ be a $t$-partition of $\cal N$. An entropy function $\bf h$ is called $p$-symmetrical if for all ${\cal A},{\cal B} \subset {\cal N}$, $\bf{h}({\cal A}) = \bf{h}({\cal B})$ whenever $|{\cal A} \cap {\cal N}_i| = |{\cal B} \cap {\cal N}_i|$, $i = 1, \cdots,t$. The set of all the $p$-symmetrical entropy functions, denoted by $Ψ^*_p$, is called $p$-symmetrical entropy function region. We prove that $\overline{Ψ^*_p}$, the closure of $Ψ^*_p$, is completely characterized by Shannon-type information inequalities if and only if $p$ is the $1$-partition or a $2$-partition with one of its blocks being a singleton. The characterization of the partition-symmetrical entropy functions can be useful for solving some information theory and related problems where symmetry exists in the structure of the problems. Keywords: entropy, entropy function, information inequality, polymatroid.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Cut-Set Bounds for Networks with Zero-Delay Nodes

In a network, a node is said to incur a delay if its encoding of each transmitted symbol involves only its received symbols obtained before the time slot in which the transmitted symbol is sent (hence the transmitted symbol sent in a time slot cannot depend on the received symbol obtained in the same time slot). A node is said to incur no delay if its received symbol obtained in a time slot is available for encoding its transmitted symbol sent in the same time slot. Under the classical model, every node in a discrete memoryless network (DMN) incurs a unit delay, and the capacity region of the DMN satisfies the well-known cut-set outer bound. In this paper, we propose a generalized model for the DMN where some nodes may incur no delay. Under our generalized model, we obtain a new cut-set outer bound, which is proved to be tight for some two-node DMN and is shown to subsume an existing cut-set bound for the causal relay network. In addition, we establish under the generalized model another cut-set outer bound on the positive-delay region -- the set of achievable rate tuples under the constraint that every node incurs a delay. We use the cut-set bound on the positive-delay region to show that for some two-node DMN under the generalized model, the positive-delay region is strictly smaller than the capacity region.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Batched Sparse Codes

Network coding can significantly improve the transmission rate of communication networks with packet loss compared with routing. However, using network coding usually incurs high computational and storage costs in the network devices and terminals. For example, some network coding schemes require the computational and/or storage capacities of an intermediate network node to increase linearly with the number of packets for transmission, making such schemes difficult to be implemented in a router-like device that has only constant computational and storage capacities. In this paper, we introduce BATched Sparse code (BATS code), which enables a digital fountain approach to resolve the above issue. BATS code is a coding scheme that consists of an outer code and an inner code. The outer code is a matrix generation of a fountain code. It works with the inner code that comprises random linear coding at the intermediate network nodes. BATS codes preserve such desirable properties of fountain codes as ratelessness and low encoding/decoding complexity. The computational and storage capacities of the intermediate network nodes required for applying BATS codes are independent of the number of packets for transmission. Almost capacity-achieving BATS code schemes are devised for unicast networks, two-way relay networks, tree networks, a class of three-layer networks, and the butterfly network. For general networks, under different optimization criteria, guaranteed decoding rates for the receiving nodes can be obtained.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Imperfect Secrecy in Wiretap Channel II

In a point-to-point communication system which consists of a sender, a receiver and a set of noiseless channels, the sender wishes to transmit a private message to the receiver through the channels which may be eavesdropped by a wiretapper. The set of wiretap sets is arbitrary. The wiretapper can access any one but not more than one wiretap set. From each wiretap set, the wiretapper can obtain some partial information about the private message which is measured by the equivocation of the message given the symbols obtained by the wiretapper. The security strategy is to encode the message with some random key at the sender. Only the message is required to be recovered at the receiver. Under this setting, we define an achievable rate tuple consisting of the size of the message, the size of the key, and the equivocation for each wiretap set. We first prove a tight rate region when both the message and the key are required to be recovered at the receiver. Then we extend the result to the general case when only the message is required to be recovered at the receiver. Moreover, we show that even if stochastic encoding is employed at the sender, the message rate cannot be increased.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Performance Bounds on a Wiretap Network with Arbitrary Wiretap Sets

Consider a communication network represented by a directed graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$, where $\mathcal{V}$ is the set of nodes and $\mathcal{E}$ is the set of point-to-point channels in the network. On the network a secure message $M$ is transmitted, and there may exist wiretappers who want to obtain information about the message. In secure network coding, we aim to find a network code which can protect the message against the wiretapper whose power is constrained. Cai and Yeung \cite{cai2002secure} studied the model in which the wiretapper can access any one but not more than one set of channels, called a wiretap set, out of a collection $\mathcal{A}$ of all possible wiretap sets. In order to protect the message, the message needs to be mixed with a random key $K$. They proved tight fundamental performance bounds when $\mathcal{A}$ consists of all subsets of $\mathcal{E}$ of a fixed size $r$. However, beyond this special case, obtaining such bounds is much more difficult. In this paper, we investigate the problem when $\mathcal{A}$ consists of arbitrary subsets of $\mathcal{E}$ and obtain the following results: 1) an upper bound on $H(M)$; 2) a lower bound on $H(K)$ in terms of $H(M)$. The upper bound on $H(M)$ is explicit, while the lower bound on $H(K)$ can be computed in polynomial time when $|\mathcal{A}|$ is fixed. The tightness of the lower bound for the point-to-point communication system is also proved.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

On Linear Operator Channels over Finite Fields

Motivated by linear network coding, communication channels perform linear operation over finite fields, namely linear operator channels (LOCs), are studied in this paper. For such a channel, its output vector is a linear transform of its input vector, and the transformation matrix is randomly and independently generated. The transformation matrix is assumed to remain constant for every T input vectors and to be unknown to both the transmitter and the receiver. There are NO constraints on the distribution of the transformation matrix and the field size. Specifically, the optimality of subspace coding over LOCs is investigated. A lower bound on the maximum achievable rate of subspace coding is obtained and it is shown to be tight for some cases. The maximum achievable rate of constant-dimensional subspace coding is characterized and the loss of rate incurred by using constant-dimensional subspace coding is insignificant. The maximum achievable rate of channel training is close to the lower bound on the maximum achievable rate of subspace coding. Two coding approaches based on channel training are proposed and their performances are evaluated. Our first approach makes use of rank-metric codes and its optimality depends on the existence of maximum rank distance codes. Our second approach applies linear coding and it can achieve the maximum achievable rate of channel training. Our code designs require only the knowledge of the expectation of the rank of the transformation matrix. The second scheme can also be realized ratelessly without a priori knowledge of the channel statistics.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Refined Coding Bounds and Code Constructions for Coherent Network Error Correction

Coherent network error correction is the error-control problem in network coding with the knowledge of the network codes at the source and sink nodes. With respect to a given set of local encoding kernels defining a linear network code, we obtain refined versions of the Hamming bound, the Singleton bound and the Gilbert-Varshamov bound for coherent network error correction. Similar to its classical counterpart, this refined Singleton bound is tight for linear network codes. The tightness of this refined bound is shown by two construction algorithms of linear network codes achieving this bound. These two algorithms illustrate different design methods: one makes use of existing network coding algorithms for error-free transmission and the other makes use of classical error-correcting codes. The implication of the tightness of the refined Singleton bound is that the sink nodes with higher maximum flow values can have higher error correction capabilities.

0 citations0 reviewsNo code linkedOpen access