Images are a common type of digital media in computer networks, appearing in web pages, instant messaging, cloud storage, etc. Minor distortion of an image is probably not detecTable, so it is possible to hide secret messages inside images sent through the network, thus becoming a potential vulnerability. In image steganography, most steganalysis tools focus on classifying whether each input image is a stego image or not. The algorithm for extracting/decoding secret messages is not used by these tools, although we can assume the knowledge of this information under Kerckhoffs's principle. To adhere to Kerckhoffs's principle, one-time stego-key can be used, but key exchange is challenging in scenarios that apply steganography. We consider steganography based on syndrome-trellis codes (STC) without stego-keys, where STC is a powerful embedding scheme that can minimize the embedding distortion and handle wet pixels without extra effort. As secret messages are usually considered as uniformly random strings, we investigate whether the decoded strings from normal images are also uniform, i.e., statistical detectability. By applying the NIST SP 800-22 Rev. 1a statistical test suite, we show that these decoded strings are instead highly non-uniform, unless the pixels are randomly shuffled. We also demonstrate that the non-uniformity may be applied for pooled steganalysis in theory, even when the extraction includes random shuffling. This suggests that minimizing distortion is not the only metric for measurlng securlty.

Natural steganography concerns embedding a secret message in a cover-source following some distribution S_1, such that after embedding the distribution of the stego-media mimics another cover-source with distribution S_2 (without embedding). Prior works have studied natural steganography over image files, where S_1 and S_2 correspond to the light intensity distribution of a photo taken respectively at some ISO_1 and ISO_2, and much effort has been dedicated to various embedding methods. On the other hand, while the nature of mimicking the distribution S_2 by embedding messages into S_1 sources means that accurate estimations of such distributions are crucial, relatively little attention has been given to this aspect. Furthermore, deploying these stegosystems in practice requires users to estimate the noise distributions of their cameras, which poses a challenging technological barrier for average users and limits the utility of the stegosystems. An objective of this work is to verify the existing claim that, for each fixed ISO value, the pixel values follow a family of Gaussian distributions where the variance is an affine function of the mean. Towards estimating and verifying the concerned distributions, we have created a comprehensive image dataset with the mainstream Sony A6400 camera in a professional photo-shooting environment. Analyses over our dataset reveal that parameters of the light intensity distributions appear to have more complicated behaviour than reported in prior works -- they seem to depend on the overall exposure level induced by the camera settings. For the ease of analysis, we have also developed a set of tools for automating the parameter estimation process. We believe that these tools will eventually improve the accessibility of natural steganography.

Batched sparse (BATS) code is a network coding solution for multi-hop wireless networks with packet loss. Achieving a close-to-optimal rate relies on an optimal degree distribution. Technical challenges arise from the sensitivity of this distribution to the often empirically obtained rank distribution at the destination node. Specifically, if the empirical distribution overestimates the channel, BATS codes experience a significant rate degradation, leading to unstable rates across different runs and hence unpredictable transmission costs. Confronting this unresolved obstacle, we introduce a formulation for distributionally robust optimization in degree optimization. Deploying the resulting degree distribution resolves the instability of empirical rank distributions, ensuring a close-to-optimal rate, and unleashing the potential of applying BATS codes in real-world scenarios.

Batched sparse (BATS) code is a class of batched network code that can achieve a close-to-optimal rate when an optimal degree distribution is provided. We observed that most probability masses in this optimal distribution are very small, i.e., the distribution “looks” sparse. In this paper, we investigate the sparsity optimization of degree distribution for BATS codes that produces sparse degree distributions. There are many advantages to use a sparse degree distribution, say, it is robust to precision errors when sampling the degree distribution during encoding and decoding in practice. We discuss a few heuristics and also a way to obtain an exact sparsity solution. These approaches give a trade-of T between computational time and achievable rate, thus give us the flexibility to adopt BATS codes in various scenarios, e.g., device with limited computational power, stable channel condition, etc.

Wireless relay network is a solution to extend the reach of a wireless connection by installing a relay node between the source node and the sink node. Due to the broadcast nature of wireless transmission, the sink node has a chance to receive part of the data sent by the source node. In this paper, we apply a network coding scheme called BATS codes on a wireless relay network where the relay node has a stable power supply, so that we can aim for the best decoding time instead of minimizing the number of transmissions for saving energy. We optimize the time efficiency that maximize the average decoding rate per unit time by some heuristics, and bring out a message that it is not optimal to set an average number of recoded packets per batch at the relay node equals the number of packets per batch sent by the source node.

Batched network coding (BNC) is a solution to multi-hop transmission on networks with packet loss. To be compatible with the existing infrastructure, BNC is usually implemented over UDP. A single error bit will probably result in discarding the packet. UDP-Lite is a variant of UDP that supports partial checksums. As long as the data covered by the checksum is correct, damaged payload will be delivered. With UDP-Lite, we can cope with other techniques such as payload aggregation of BNC packets to reduce the protocol overhead, and forward error correction to combat against bit errors. Unlike traditional transmissions, BNC has a loss resilience feature and there are dependencies between BNC packets. In this paper, we conduct a preliminary investigation on BNC over UDP-Lite. We show that aggregating as much as we can is not always the best strategy, and a hop-by-hop distributed efficiency optimization approach may lead to a worse throughput compared with the scheme without aggregation in a long network. These unnatural results caution that a casual integration of techniques with BNC can be harmful, and give us hints on future research directions.

When there are multiple channels between a pair of source and destination, the way to use the channels carries some extra information. In this paper, we study a coding scheme that encodes the message into the choices of channels. Unlike the traditional sense that the message bits are ordered in a temporal manner, the ordering information is lost after the transformation. To resolve this issue, the data to be sent via the channels is the ordering of the message blocks. We study the properties on the number of channel-uses and the limitation of the code. We also investigate the optimal message length that maximizes the efficiency of channel-uses.

Edwards-curve digital signature algorithm (EdDSA) is a highly efficient scheme with a short key size. It is derived from the threshold-friendly Schnorr signatures and is covered by the NIST standardization efforts of threshold cryptographic primitives. Nevertheless, extending its deterministic nonce generation to the threshold setting requires heavyweight cryptographic techniques, even when the hash function is replaced with one optimized for secure multi-party computation. Indeed, an efficient extension to the threshold setting is considered a major challenge by NIST and academia.

BATched Sparse codes (BATS codes) are a class of random linear network code designed for wireless multi-hop networks with packet loss. The encoder of a BATS code generates batches where each batch contains a number of coded packets. As the outer code is a matrix generalization of the fountain code, the ordinary batch construction scheme relies on a degree distribution with a random packet sampling scheme. In practical applications, we want a batch construction scheme which achieves a high decoding rate at the destination. A natural question to ask is: Is there any batch construction scheme which achieves a higher decoding rate than the ordinary one? We give an affirmative answer to this question by formulating the batch construction scheme as a multi-armed bandit problem and solving it with a deep reinforcement learning method with the degree distribution as a guiding prior. The BATS code generated by our proposed method achieves a higher decoding rate with improved efficiency compared with the ordinary batch construction scheme.

The theory of multichannel prefix codes aims to generalize the classical theory of prefix codes. Although single- two-channel prefix codes always have decoding trees, the same cannot be said when there are more than two channels. One question is of theoretical interest: Do there exist optimal codes that are not optimal prefix codes? Existing literature, focused on generalizing single-channel results, covered little about non-tree-decodable prefix codes since they have no single-channel counterparts. In this work, we study the fundamental reason behind the non-tree-decodability of prefix codes. By investigating the non-tree-decodable structure, we obtain a general sufficient condition on the channel alphabets for the existence of optimal tree-decodable codes that are not optimal prefix codes.

Batched network coding (BNC) is a low-complexity variant of random linear network coding (RLNC) that encodes the file to be sent into batches, each consisting of a few coded packets. Although many works are focusing on the overhead reduction of RLNC, the overhead reduction for BNC is rarely studied. Different types of overheads in BNC interact and can potentially increase the overall overhead significantly. In this paper, we formulate a minimization problem for BNC on the number of symbols we need to send at the source node by tuning the number of packets divided from the file, which has the same meaning as tuning the packet size. It is hard to optimize the discrete zigzag-like objective efficiently. However, in practical scenarios, the encoder has to optimize the problem in real-time for different file size and redundancy requirements. We propose an efficient heuristic for this purpose and show its accuracy by numerical evaluations.

Batched network coding is a practical realization of random linear network coding that resolves the issue of high computational and storage costs at the intermediate nodes by restricting recoding to the packets belonging to the same batch. Although there are various recoding approaches in the literature, they consider a one-shot approach which decides the number of recoded packets to be generated and transmits them without considering the reception status of these packets at the next node. In this paper, we divide the recoding process into multiple phases. In each phase, recoding depends on the amount of innovative information left at the current node after the transmission of the previous phases, where this knowledge can be obtained via feedback mechanism. This way, we can reduce the uncertainty during recoding and utilize the network more efficiently.We formulate the optimization problems for multi-phase adaptive recoding and show by simulation that two-phase recoding can already enhance the throughput significantly

In a ring-signature-based anonymous cryptocurrency, signers of a transaction are hidden among a set of potential signers, called a ring, whose size is much smaller than the number of all users. The ringmembership relations specified by the sets of transactions thus induce bipartite transaction graphs, whose distribution is in turn induced by the ring sampler underlying the cryptocurrency. Since efficient graph analysis could be performed on transaction graphs to potentially deanonymise signers, it is crucial to understand the resistance of (the transaction graphs induced by) a ring sampler against graph analysis. Of particular interest is the class of partitioning ring samplers. Although previous works showed that they provide almost optimal local anonymity, their resistance against global, e.g. graph-based, attacks were unclear. In this work, we analyse transaction graphs induced by partitioning ring samplers. Specifically, we show (partly analytically and partly empirically) that, somewhat surprisingly, by setting the ring size to be at least logarithmic in the number of users, a graph-analysing adversary is no better than the one that performs random guessing in deanonymisation up to constant factor of 2.

Batched network coding is a low-complexity network coding solution to feedbackless multi-hop wireless packet network transmission with packet loss. The data to be transmitted is encoded into batches where each of which consists of a few coded packets. Unlike the traditional forwarding strategy, the intermediate network nodes have to perform recoding, which generates recoded packets by network coding operations restricted within the same batch. Adaptive recoding is a technique to adapt the fluctuation of packet loss by optimizing the number of recoded packets per batch to enhance the throughput. The input rank distribution, which is a piece of information regarding the batches arriving at the node, is required to apply adaptive recoding. However, this distribution is not known in advance in practice as the incoming link's channel condition may change from time to time. On the other hand, to fully utilize the potential of adaptive recoding, we need to have a good estimation of this distribution. In other words, we need to guess this distribution from a few samples so that we can apply adaptive recoding as soon as possible. In this paper, we propose a distributionally robust optimization for adaptive recoding with a small-sample inferred prediction of the input rank distribution. We develop an algorithm to efficiently solve this optimization with the support of theoretical guarantees that our optimization's performance would constitute as a confidence lower bound of the optimal throughput with high probability.

Batched network coding is a solution to reliable communications in multi-hop networks with packet loss. Adaptive recoding is a technique to enhance the throughput of batched network coding. Two pieces of information is needed to apply adaptive recoding: the distribution of the information remained in the received batches and the channel condition of the outgoing link. A simple way to obtain the former information is to make a short observation by grouping a few batches into a block. This way to apply adaptive recoding is called blockwise adaptive recoding (BAR), which can achieve a nice throughput even when the block size is small. Previous literature assumes that the latter information is known in advance and would not be changed over time. However in practice, these assumptions do not hold in general. In this paper, we investigate the impact of inaccurate channel condition on BAR and show by numerical evaluations that the throughput is very close to the one with accurate channel condition. To adapt the varying channel condition, we also propose a feedback scheme for BAR and a method to reduce the computational time for BAR.

Batched network coding (BNC) is a low-complexity solution to network transmission in multi-hop packet networks with packet loss. BNC encodes the source data into batches of packets. As a network coding scheme, the intermediate nodes perform recoding on the received packets belonging to the same batch instead of just forwarding them. A recoding scheme that may generate more recoded packets for batches of a higher rank is also called adaptive recoding. Meanwhile, in order to combat burst packet loss, the transmission of a block of batches can be interleaved. Stream interleaving studied in literature achieves the maximum separation among any two consecutive packets of a batch, but permutes packets across blocks and hence cannot bound the buffer size and the latency. To resolve the issue of stream interleaver, we design an intrablock interleaver for adaptive recoding that can preserve the advantages of using a block interleaver when the number of recoded packets is the same for all batches. We use potential energy in classical mechanics to measure the performance of an interleaver, and propose an algorithm to optimize the interleaver with this performance measure. Our problem formulation and algorithm for intrablock interleaving are also of independent interest.

Zero-error single-channel source coding has been studied extensively over the past decades. Its natural multi-channel generalization is however seldom investigated. While the special case with multiple symmetric-alphabet channels was studied a decade ago, codes in such setting have no advantage over single-channel codes in data compression, making them worthless in most applications. With essentially no development since the last decade, in this paper, we break the stalemate by showing that it is possible to beat single-channel source codes in terms of compression assuming asymmetric-alphabet channels. We present the multi-channel analogs of several classical results in single-channel source coding, e.g., a multi-channel Huffman code is an optimal tree-decodable code. We also show evidences that finding an efficient construction of multi-channel Huffman codes may be hard. Nevertheless, we propose a construction whose redundancy is guaranteed to be no larger than that of an optimal single-channel source code.

Although n-channel prefix-free codes are natural extensions of their 1-channel counterpart, the extra dimensions greatly increase the complexity of the problem such that most classical results cannot be generalized directly. Recently, a greedy algorithm was developed for deciding if it is possible to construct a 2-channel prefix-free code from a given multiset of codeword lengths. By dropping the information about codeword assignments which are not necessary for the decision problem, the greedy algorithm runs in polynomial time. However, if we naively turn the decision algorithm into a search algorithm (for constructing a prefix-free code) by retaining the information about codeword assignments, the computational complexity becomes exponential. One puzzle left unsolved was that whether the search problem can also be solved in polynomial time. In this paper, we give an affirmative answer to this question by designing a tailor-made data structure and a new lazy evaluation technique.

Wireless relay network is a solution for transmitting information from a source node to a sink node far away by installing a relay in between. The broadcasting nature of wireless communication allows the sink node to receive part of the data sent by the source node. In this way, the relay does not need to receive the whole piece of data from the source node and it does not need to forward everything it received. In this paper, we consider the application of batched network coding, a practical form of random linear network coding, for a better utilization of such a network. The amount of innovative information at the relay which is not yet received by the sink node, called the innovative rank, plays a crucial role in various applications including the design of the transmission scheme and the analysis of the throughput. We present a visualization of the innovative rank which allows us to understand and derive formulae related to the innovative rank with ease.

A ring signature scheme allows the signer to sign on behalf of an ad hoc set of users, called a ring. The verifier can be convinced that a ring member signs, but cannot point to the exact signer. Ring signatures have become increasingly important today with their deployment in anonymous cryptocurrencies. Conventionally, it is implicitly assumed that all ring members are equally likely to be the signer. This assumption is generally false in reality, leading to various practical and devastating deanonymizing attacks in Monero, one of the largest anonymous cryptocurrencies. These attacks highlight the unsatisfactory situation that how a ring should be chosen is poorly understood.

Network utility maximization (NUM) is studied for multihop wireless networks employing an efficient random linear network coding scheme called BATS codes. Compared with the classical random linear network coding scheme, BATS codes have lower computational and storage costs at the intermediate network nodes, and can achieve close-to-optimal end-to-end throughput and latency for multihop networks with packet loss. We formulate a NUM problem that optimizes the total utility of multiple communication flows under certain link scheduling constraints. Our problem employs a practical throughput measure induced by BATS codes and hence can provide realistic guidelines about network protocol designs for multihop wireless networks. Our problem in general has a non-convex objective function with integer variables, so that the algorithms of solving existing network utility maximization problems cannot be directly applied to our problem. We discuss a modified dual-based algorithm for solving our problem and evaluate its performance numerically.

Batched network coding is a practical branch of random linear network coding which encodes the input file into small batches of coded packets. Although burst erasures within the batches can reduce the advantage of network coding, it can be alleviated by applying a block interleaver which spreads the burst across multiple batches. On the other hand, the intermediate network nodes are required to perform recoding on the batches unlike the traditional forwarding strategy. The recoding of a batch can be started once all the packets in that batch which are not dropped by the channel are received. This means that the intermediate network nodes have to deinterleave the batches for recoding and reinterleave the batches again for transmission, which gives us a choice to use different interleaver depths at different network nodes. In this paper, we study the memory requirements of the schemes for transmitting batches which apply different interleaver depths. We investigate the periodic structure of buffer sizes and the connection between buffer sizes and the total delay induced by the interleaver. More importantly, we show that there exists a scheme which can achieve the lowest memory requirement and minimum total delay simultaneously.

The Kraft inequality gives a necessary and sufficient condition for the existence of a single channel prefix-free code. However, the multichannel Kraft inequality does not imply the existence of a multichannel prefix-free code in general. It is natural to ask whatever there exists an efficient decision procedure for the existence of multichannel prefix-free codes. In this paper, we tackle the two-channel case of the above problem by relating it to a constrained rectangle packing problem. Although a general rectangle packing problem is NP-complete, the extra imposed constraints allow us to propose an algorithm which can solve the problem efficiently.

Batched network coding is a practical realization of random linear network coding, which encodes the packets for transmission into small batches of coded packets. The advantage of network coding can be reduced when a burst loss occurs. Block interleaver is one of the approach to spread the burst across multiple batches. However, an intermediate node has to receive all the packets in a batch which are not dropped by the channel before it can perform recoding on the batch, which means that the node has to deinterleave for recoding and reinterleave again for transmission. This gives us the freedom to select heterogeneous interleaver depth among the intermediate nodes. In general, the larger the interleaver depth, the better the spread of the bursts. On the other hand, we want the delay as short as possible to enable real-time applications. In this paper, we investigate the delay induced by applying a block interleaver on batched network codes. We also show that a homogeneous interleaver depth is the largest interleaver depth we can use to achieve a minimum delay.

Batched network coding is a variation of random linear network coding which has low computational and storage costs. In order to adapt random fluctuations in the number of erasures in individual batches, it is not optimal to recode and transmit the same number of packets for all batches. Different distributed optimization problems, which are called adaptive recoding, were formulated for this purpose. The key component of these optimization problems is the expected value of the rank distribution of a batch at the next network node, which also known as the expected rank. In this paper, we put forth a unified adaptive recoding framework. We show that the expected rank functions are concave when the packet loss pattern follows a stationary stochastic process regardless of the field size, which covers but not limited to independent packet loss and burst packet loss. Under this concavity property, we show that there always exists a preferred solution which not only can make the number of recoded packets almost deterministic but can also tolerate rank distribution errors due to inaccurate measurements or limited precision of the machine. To obtain such an optimal solution, we propose tuning schemes that can turn any feasible solution into one with the above desired properties.

BATS codes are a class of random linear network coding scheme which have close-to-optimal achievable rates, while adaptive recoding is a packet combining scheme which adds a boost to the throughput by adapting the packet combining at the relay to the random fluctuations in the number of erasures in individual batches. In this paper, we apply BATS code with adaptive recoding for the transmission on wireless relay network. In contrast to the existing adaptive recoding schemes, we propose a model which can make use of the broadcast nature of wireless communication to enhance the achievable rates via overhearing. We also optimize the packet efficiency, i.e., minimizing the average number of channel use for each input packet for a successful decoding.

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 generalization of fountain codes, which works with the inner code that comprises random linear network coding at the intermediate network nodes. In this paper, we propose a new inner code scheme for BATS codes, called adaptive recoding, which can be applied distributively at the intermediate network nodes, requiring only local knowledge of the received packets and the outgoing network link erasure probability. We show that adaptive recoding has significant throughput gain for relatively small batch sizes, compared with the baseline recoding scheme used in existing works.