Visible to the public Coding Theory and Security, 2014, Part 3

SoS Newsletter- Advanced Book Block


SoS Logo

Coding Theory and Security, 2014

Part 3

Coding theory is one of the essential pieces of information theory. More important, coding theory is a core element in cryptography. The research work cited here looks at signal processing, crowdsourcing, matroid theory, WOM codes, and the N-P hard problem. These works were presented or published in 2014. 

Xuan Guang; Jiyong Lu; Fang-Wei Fu, "Locality-Preserving Secure Network Coding," Information Theory Workshop (ITW), 2014 IEEE, vol. no., pp. 396, 400, 2-5 Nov. 2014. doi:10.1109/ITW.2014.6970861
Abstract: In the paradigm of network coding, when wiretapping attacks occur, secure network coding is introduced to prevent information leaking adversaries. In practical network communications, the source often multicasts messages at several different rates within a session. How to deal with information transmission and information security simultaneously under variable rates and fixed security-level is introduced in this paper as a variable-rate and fixed-security-level secure network coding problem. In order to solve this problem effectively, we propose the concept of locality-preserving secure linear network codes of different rates and fixed security-level, which have the same local encoding kernel at each internal node. We further present an approach to construct such a family of secure linear network codes and give an algorithm for efficient implementation. This approach saves the storage space for both source node and internal nodes, and resources and time on networks. Finally, the performance of the proposed algorithm is analyzed, including the field size, computational and storage complexities.
Keywords: linear codes; network coding; telecommunication security; variable rate codes; fixed-security-level secure network coding problem; information security; information transmission; internal nodes; local encoding kernel; locality-preserving secure linear network codes; source node; variable-rate secure network coding problem; wiretapping attacks; Complexity theory; Decoding; Encoding; Information rates; Kernel; Network coding; Vectors (ID#: 15-4884)


Watanabe, S.; Oohama, Y., "Cognitive Interference Channels with Confidential Messages Under Randomness Constraint," Information Theory, IEEE Transactions on, vol. 60, no. 12, pp. 7698, 7707, Dec. 2014. doi:10.1109/TIT.2014.2360683
Abstract: The cognitive interference channel with confidential messages (CICC) proposed by Liang et al. is investigated. When the security is considered in coding systems, it is well-known that the sender needs to use a stochastic encoding to avoid the information about the transmitted confidential message to be leaked to an eavesdropper. For the CICC, the tradeoff between the rate of the random number to realize the stochastic encoding and the communication rates is investigated, and the optimal tradeoff is completely characterized.
Keywords: Decoding; Encoding; Interference channels; Random variables; Receivers; Security; Tin; Cognitive Interference Channel; Cognitive interference channel; Confidential Messages; Randomness Constraint; Stochastic Encoder; Superposition Coding; confidential messages; randomness constraint; stochastic encoder; superposition coding (ID#: 15-4885)


Muramatsu, J., "General Formula for Secrecy Capacity of Wiretap Channel with Noncausal State," Information Theory (ISIT), 2014 IEEE International Symposium on, vol., no., pp. 21, 25, June 29 2014 – July 4 2014. doi:10.1109/ISIT.2014.6874787
Abstract: The coding problem for a wiretap channel with a noncausal state is investigated, where the problem includes the coding problem for a channel with a noncausal state, which is known as the Gel'fand-Pinsker problem, and the coding problem for a wiretap channel introduced by Wyner. The secrecy capacity for this channel is derived, where an optimal code is constructed based on the hash property and a constrained-random-number generator. Since an ensemble of sparse matrices has a hash property, the rate of the proposed code using a sparse matrix can achieve the secrecy capacity.
Keywords: encoding; random number generation; security of data; Gel'fand-Pinsker problem; coding problem; constrained random number generator; hash property; noncausal state; optimal code; secrecy capacity; wiretap channel; Decoding; Encoding; Manganese; Random variables; Tin; Zinc (ID#: 15-4886)


Yardi, A.D.; Kumar, A.; Vijayakumaran, S., "Channel-Code Detection by a Third-Party Receiver via the Likelihood Ratio Test," Information Theory (ISIT), 2014 IEEE International Symposium on, vol., no., pp. 1051, 1055, June 29 2014 – July 4 2014. doi:10.1109/ISIT.2014.6874993
Abstract: Channel codebook detection is of interest in cognitive paradigm or security applications. A binary hypothesis testing problem is considered, where a receiver has to detect the channel-code from two possible choices upon observing noise-affected codewords through a communication channel. For analytical tractability, it is assumed that the two channel-codes are linear block codes with identical block-length. In a first, this work studies the likelihood ratio test for minimizing the error probability in this detection problem. In an asymptotic setting, where a large number of noise-affected codewords are available for detection, the Chernoff information characterizes the error probability. A lower bound on the Chernoff information, based on the parameters of the two hypothesis, is established. Further, it is shown that if likelihood based efficient (generalized distributive law or BCJR) bit-decoding algorithms are available for the two codes, then the likelihood ratio test for the code-detection problem can be performed in a computationally feasible manner.
Keywords: block codes; channel coding; cognitive radio; error statistics; linear codes; statistical analysis; telecommunication security; BCJR; Chernoff information; analytical tractability; binary hypothesis testing problem; bit-decoding algorithms; channel codebook detection; cognitive paradigm; communication channel; error probability minimization; generalized distributive law; identical block-length; likelihood ratio test; linear block codes; noise-affected codewords; security application; third-party receiver; Block codes; Error probability; Noise; Receivers; Testing; Vectors (ID#: 15-4887)


Villard, J.; Piantanida, P.; Shamai, S., "Secure Transmission of Sources over Noisy Channels with Side Information at the Receivers," Information Theory, IEEE Transactions on, vol. 60, no. 1, pp. 713, 739, Jan. 2014. doi:10.1109/TIT.2013.2288256
Abstract: This paper investigates the problem of source-channel coding for secure transmission with arbitrarily correlated side informations at both receivers. This scenario consists of an encoder (referred to as Alice) that wishes to compress a source and send it through a noisy channel to a legitimate receiver (referred to as Bob). In this context, Alice must simultaneously satisfy the desired requirements on the distortion level at Bob and the equivocation rate at the eavesdropper (referred to as Eve). This setting can be seen as a generalization of the problems of secure source coding with (uncoded) side information at the decoders and the wiretap channel. A general outer bound on the rate-distortion-equivocation region, as well as an inner bound based on a pure digital scheme, is derived for arbitrary channels and side informations. In some special cases of interest, it is proved that this digital scheme is optimal and that separation holds. However, it is also shown through a simple counterexample with a binary source that a pure analog scheme can outperform the digital one while being optimal. According to these observations and assuming matched bandwidth, a novel hybrid digital/analog scheme that aims to gather the advantages of both digital and analog ones is then presented. In the quadratic Gaussian setup when side information is only present at the eavesdropper, this strategy is proved to be optimal. Furthermore, it outperforms both digital and analog schemes and cannot be achieved via time-sharing. Through an appropriate coding, the presence of any statistical difference among the side informations, the channel noises, and the distortion at Bob can be fully exploited in terms of secrecy.
Keywords: Gaussian channels; combined source-channel coding; receivers; telecommunication security; binary source; channel noise; eavesdropper; encoder; hybrid digital-analog scheme; quadratic Gaussian setup; rate-distortion-equivocation region; receiver; source coding security; source-channel coding; statistical difference; time-sharing; transmission security; wiretap channel; Channel coding; Decoding; Noise measurement; Radio frequency; Random variables; Source coding; Combined source-channel coding; Gaussian channels; information security; rate-distortion; side information (ID#: 15-4888)


Muxi Yan; Sprintson, A.; Zelenko, I., "Weakly Secure Data Exchange with Generalized Reed Solomon Codes," Information Theory (ISIT), 2014 IEEE International Symposium on, vol., no., pp. 1366, 1370, June 29 2014 – July 4 2014. doi:10.1109/ISIT.2014.6875056
Abstract: We focus on secure data exchange among a group of wireless clients. The clients exchange data by broadcasting linear combinations of packets over a lossless channel. The data exchange is performed in the presence of an eavesdropper who has access to the channel and can obtain all transmitted data. Our goal is to develop a weakly secure coding scheme that prevents the eavesdropper from being able to decode any of the original packets held by the clients. We present a randomized algorithm based on Generalized Reed-Solomon (GRS) codes. The algorithm has two key advantages over the previous solutions: it operates over a small (polynomial-size) finite field and provides a way to verify that constructed code is feasible. In contrast, the previous approaches require exponential field size and do not provide an efficient (polynomial-time) algorithm to verify the secrecy properties of the constructed code. We formulate an algebraic-geometric conjecture that implies the correctness of our algorithm and prove its validity for special cases. Our simulation results indicate that the algorithm is efficient in practical settings.
Keywords: Reed-Solomon codes; algebra; broadcast channels; electronic data interchange; geometry; security of data; telecommunication security; wireless channels; GRS codes; algebraic-geometric conjecture; eavesdropper prevention; exponential field size; finite field; generalized Reed Solomon codes; lossless broadcast channel; weakly secure coding scheme; weakly secure data exchange problem; wireless clients; Encoding; Network coding; Polynomials; Reed-Solomon codes; Silicon; Vectors (ID#: 15-4889)


Geil, O.; Martin, S.; Matsumoto, R.; Ruano, D.; Yuan Luo, "Relative Generalized Hamming Weights of One-Point Algebraic Geometric Codes," Information Theory, IEEE Transactions on, vol. 60, no. 10, pp. 5938, 5949, Oct. 2014. doi:10.1109/TIT.2014.2345375
Abstract: Security of linear ramp secret sharing schemes can be characterized by the relative generalized Hamming weights of the involved codes. In this paper, we elaborate on the implication of these parameters and devise a method to estimate their value for general one-point algebraic geometric codes. As it is demonstrated, for Hermitian codes, our bound is often tight. Furthermore, for these codes, the relative generalized Hamming weights are often much larger than the corresponding generalized Hamming weights.
Keywords: Hamming codes; algebraic geometric codes; cryptography; Hermitian codes; cryptographic method; general one-point algebraic geometric codes; linear ramp secret sharing schemes; relative generalized Hamming weights; Cryptography; Electronic mail; Hamming weight; Linear codes; Materials; Random variables; Vectors; Feng-Rao bound; Hermitian code; Linear code; one-point algebraic geometric code; relative dimension/length profile; relative generalized Hamming weight; secret sharing; wiretap channel of type II (ID#: 15-4890)


Tyagi, H.; Vardy, A., "Explicit Capacity-Achieving Coding Scheme for the Gaussian Wiretap Channel," Information Theory (ISIT), 2014 IEEE International Symposium on, vol. no., pp. 956, 960, June 29 2014 – July 4 2014. doi:10.1109/ISIT.2014.6874974
Abstract: We extend the Bellare-Tessaro coding scheme for a discrete, degraded, symmetric wiretap channel to a Gaussian wiretap channel. Denoting by SNR the signal-to-noise ratio of the eavesdropper's channel, the proposed scheme converts a transmission code of rate R for the channel of the legitimate receiver into a code of rate R-0.5 log(1+SNR) for the Gaussian wiretap channel. The conversion has a polynomial complexity in the codeword length and the proposed scheme achieves strong security. In particular, when the underlying transmission code is capacity achieving, this scheme achieves the secrecy capacity of the Gaussian wiretap channel.
Keywords: Gaussian channels; channel capacity; channel coding; telecommunication security; Bellare-Tessaro coding; Gaussian wiretap channel; degraded wiretap channel; discrete wiretap channel; explicit capacity-achieving coding; secrecy capacity; symmetric wiretap channel; transmission code; Cryptography; Encoding; Receivers; Reliability; Zinc (ID#: 15-4891)


Matsumoto, R., "New Asymptotic Metrics for Relative Generalized Hamming Weight," Information Theory (ISIT), 2014 IEEE International Symposium on, vol., no., pp. 3142, 3144, June 29 2014 – July 4 2014. doi:10.1109/ISIT.2014.6875413
Abstract: It was recently shown that RGHW (relative generalized Hamming weight) exactly expresses the security of linear ramp secret sharing scheme. In this paper we determine the true value of the asymptotic metric for RGHW previously proposed by Zhuang et al. in 2013. Then we propose new asymptotic metrics useful for investigating the optimal performance of linear ramp secret sharing scheme constructed from a pair of linear codes. We also determine the true values of the proposed metrics in many cases.
Keywords: Hamming codes; cryptography; linear codes; RGHW; asymptotic metrics; linear codes; linear ramp secret sharing scheme; relative generalized Hamming weight; Cryptography; Equations; Hamming weight; Information rates; Linear codes; Measurement (ID#: 15-4892)


Khisti, A.; Tie Liu, "Private Broadcasting over Independent Parallel Channels," Information Theory, IEEE Transactions on, vol. 60, no. 9, pp. 5173, 5187, Sept. 2014. doi:10.1109/TIT.2014.2332336
Abstract: We study broadcasting of two confidential messages to two groups of receivers over independent parallel subchannels. One group consists of an arbitrary number of receivers, interested in a common message, whereas the other group has only one receiver. Each message must be confidential from the receiver(s) in the other group. Each of the subchannels is assumed to be degraded in a certain fashion. While corner points of the capacity region of this setup were characterized in earlier works, we establish the complete capacity region, and show the optimality of a superposition coding technique. For Gaussian channels, we establish the optimality of a Gaussian input distribution by applying an extremal information inequality. By extending our coding scheme to block-fading channels, we demonstrate significant performance gains over a baseline time-sharing scheme.
Keywords: Gaussian channels; block codes; data privacy; fading channels; radio receivers; telecommunication security; wireless channels; Gaussian channels; Gaussian input distribution; baseline time sharing scheme; block fading channels; coding scheme; extremal information inequality; independent parallel channels; independent parallel subchannels; private broadcasting; receivers; superposition coding technique; Broadcasting; Channel models; Coherence; Encoding; Fading; Indexes; Receivers; Wiretap channel; parallel channels; private broadcasting; secrecy capacity; superposition coding (ID#: 15-4893)


Mirzaee, M.; Akhlaghi, S., "Maximizing the Minimum Achievable Secrecy Rate in a Two-User Gaussian Interference Channel," Communication and Information Theory (IWCIT), 2014 Iran Workshop on, pp. 1, 5, 7 – 8 May 2014. doi:10.1109/IWCIT.2014.6842501
Abstract: This paper studies a two-user Gaussian interference channel in which two single-antenna sources aim at sending their confidential messages to the legitimate destinations such that each message should be kept confidential from non-intended receiver. Also, it is assumed that the direct channel gains are stronger than the interference channel gains and the noise variances at two destinations are equal. In this regard, under Gaussian code book assumption, the problem of secrecy rate balancing which aims at exploring the optimal power allocation policy at the sources in an attempt to maximize the minimum achievable secrecy rate is investigated, assuming each source is subject to a transmit power constraint. To this end, it is shown that at the optimal point, two secrecy rates are equal, hence, the problem is abstracted to maximizing the secrecy rate associated with one of destinations while the other destination is restricted to have the same secrecy rate. Accordingly, the optimum secrecy rate associated with the investigated max-min problem is analytically derived leading to the solution of secrecy rate balancing problem.
Keywords: Gaussian channels; antennas; interference (signal); telecommunication security; Gaussian code book assumption; achievable secrecy rate; direct channel gains; interference channel gains; max-min problem; noise variances; nonintended receiver; optimal power allocation policy; secrecy rate balancing; single-antenna sources; transmit power constraint; two-user Gaussian interference channel; Array signal processing; Gain; Interference channels; Linear programming; Noise; Optimization; Transmitters; Achievable secrecy rate; Gaussian interference channel; Max-Min problem (ID#: 15-4894)


Pengwei Wang; Safavi-Naini, R., "An Efficient Code for Adversarial Wiretap Channel," Information Theory Workshop (ITW), 2014 IEEE, vol., no., pp. 40, 44, 2-5 Nov. 2014. doi:10.1109/ITW.2014.6970788
Abstract: In the (ρr, ρw)-adversarial wiretap (AWTP) channel model of [13], a codeword sent over the communication channel is corrupted by an adversary who observes a fraction ρr of the codeword, and adds noise to a fraction ρw of the codeword. The adversary is adaptive and chooses the subsets of observed and corrupted components, arbitrarily. In this paper we give the first efficient construction of a code family that provides perfect secrecy in this model, and achieves the secrecy capacity.
Keywords: channel coding; telecommunication security; wireless channels; AWTP channel model; adversarial wiretap channel model; code family; codeword; communication channel; secrecy capacity; Computational modeling; Decoding; Encoding; Reed-Solomon codes; Reliability; Security; Vectors (ID#: 15-4895)


Son Hoang Dau; Wentu Song; Chau Yuen, "On Block Security of Regenerating Codes at the MBR Point for Distributed Storage Systems," Information Theory (ISIT), 2014 IEEE International Symposium on, vol., no., pp. 1967, 1971, June 29 2014 – July 4 2014. doi:10.1109/ISIT.2014.6875177
Abstract: A passive adversary can eavesdrop stored content or downloaded content of some storage nodes, in order to learn illegally about the file stored across a distributed storage system (DSS). Previous work in the literature focuses on code constructions that trade storage capacity for perfect security. In other words, by decreasing the amount of original data that it can store, the system can guarantee that the adversary, which eavesdrops up to a certain number of storage nodes, obtains no information (in Shannon's sense) about the original data. In this work we introduce the concept of block security for DSS and investigate minimum bandwidth regenerating (MBR) codes that are block secure against adversaries of varied eavesdropping strengths. Such MBR codes guarantee that no information about any group of original data units up to a certain size is revealed, without sacrificing the storage capacity of the system. The size of such secure groups varies according to the number of nodes that the adversary can eavesdrop. We show that code constructions based on Cauchy matrices provide block security. The opposite conclusion is drawn for codes based on Vandermonde matrices.
Keywords: codes; distributed processing; matrix algebra; security of data; storage management; Cauchy matrices; DSS; MBR codes; MBR point; Vandermonde matrices; block security; code constructions; distributed storage systems; minimum bandwidth regenerating codes; passive adversary; storage capacity; Decision support systems; Degradation; Encoding; Maintenance engineering; Network coding; Security (ID#: 15-4896)


Jinlong Lu; Harshan, J.; Oggier, F., "A USRP Implementation of Wiretap Lattice Codes," Information Theory Workshop (ITW), 2014 IEEE, vol., no., pp. 316, 320, 2-5 Nov. 2014. doi:10.1109/ITW.2014.6970845
Abstract: A wiretap channel models a communication channel between a legitimate sender Alice and a legitimate receiver Bob in the presence of an eavesdropper Eve. Confidentiality between Alice and Bob is obtained using wiretap codes, which exploit the difference between the channels to Bob and to Eve. This paper discusses a first implementation of wiretap lattice codes using USRP (Universal Software Radio Peripheral), which focuses on the channel between Alice and Eve. Benefits of coset encoding for Eve's confusion are observed, using different lattice codes in small dimensions, and varying the position of the eavesdropper.
Keywords: channel coding; software radio; telecommunication security; USRP implementation; communication channel; coset encoding; eavesdropper; universal software radio peripheral; wiretap channel models; wiretap lattice codes; Baseband; Decoding; Encoding; Lattices; Receivers; Security; Signal to noise ratio (ID#: 15-4897)


Jinjing Jiang; Marukala, N.; Tie Liu, "Symmetrical Multilevel Diversity Coding and Subset Entropy Inequalities," Information Theory, IEEE Transactions on, vol. 60, no. 1, pp. 84,103, Jan. 2014. doi:10.1109/TIT.2013.2288263
Abstract: Symmetrical multilevel diversity coding (SMDC) is a classical model for coding over distributed storage. In this setting, a simple separate encoding strategy known as superposition coding was shown to be optimal in terms of achieving the minimum sum rate and the entire admissible rate region of the problem. The proofs utilized carefully constructed induction arguments, for which the classical subset entropy inequality played a key role. This paper consists of two parts. In the first part, the existing optimality proofs for classical SMDC are revisited, with a focus on their connections to subset entropy inequalities. Initially, a new sliding-window subset entropy inequality is introduced and then used to establish the optimality of superposition coding for achieving the minimum sum rate under a weaker source-reconstruction requirement. Finally, a subset entropy inequality recently proved by Madiman and Tetali is used to develop a new structural understanding of the work of Yeung and Zhang on the optimality of superposition coding for achieving the entire admissible rate region. Building on the connections between classical SMDC and the subset entropy inequalities developed in the first part, in the second part the optimality of superposition coding is extended to the cases where there is either an additional all-access encoder or an additional secrecy constraint.
Keywords: codecs; encoding; entropy codes; SMDC; admissible rate region; all-access encoder; distributed storage; encoding strategy; secrecy constraint; sliding-window subset entropy inequality; source-reconstruction requirement; subset entropy inequalities sum rate; superposition coding; symmetrical multilevel diversity coding; Clocks; Decoding; Electronic mail; Encoding; Entropy; Indexes; Tin; Distributed storage; information-theoretic security; multilevel diversity coding; subset entropy inequality (ID#: 15-4898)


Chen, Yanling; Koyluoglu, O.Ozan; Sezgin, Aydin, "On the Achievable Individual-Secrecy Rate Region for Broadcast Channels with Receiver Side Information," Information Theory (ISIT), 2014 IEEE International Symposium on, vol., no., pp. 26, 30, June 29 2014 – July 4 2014. doi:10.1109/ISIT.2014.6874788
Abstract: In this paper, we study the problem of secure communication over the broadcast channel with receiver side information, under the lens of individual secrecy constraints (i.e., information leakage from each message to an eavesdropper is made vanishing). Several coding schemes are proposed by extending known results in broadcast channels to this secrecy setting. In particular, individual secrecy provided via one-time pad signal is utilized in the coding schemes. As a result, we obtain an achievable rate region together with a characterization of the capacity region for special cases of either a weak or strong eavesdropper (compared to both legitimate receivers). Interestingly, the capacity region for the former corresponds to a line and the latter corresponds to a square with missing corners; a phenomenon occurring due to the coupling between user's rates. At the expense of having a weaker notion of security, positive secure transmission rates are always guaranteed, unlike the case of the joint secrecy constraint.
Keywords:  (not provided) (ID#: 15-4899)


Tao Ye; Veitch, D.; Johnson, S., "RA-Inspired Codes for Efficient Information Theoretic Multi-Path Network Security," Information Theory and its Applications (ISITA), 2014 International Symposium on, vol., no., pp.408, 412, 26-29 Oct. 2014. doi: (not provided)
Abstract: Mobile devices have multiple network interfaces, some of which have security weaknesses, yet are used for sensitive data despite the risk of eavesdropping. We describe a data-splitting approach which, by design, maps exactly to a wiretap channel, thereby offering information theoretic security. Being based on the deletion channel, it perfectly hides block boundaries from the eavesdropper, which enhances security further. We provide an efficient Repeat Accumulate inspired code design, which satisfies the security criterion, and explore its security rate as a function block size and other parameters.
Keywords: codes; information theory; security of data; telecommunication security; RA-inspired codes; data-splitting approach; deletion channel; eavesdropper; eavesdropping; function block size; information theoretic multipath network security; mobile devices; multiple network interfaces; repeat accumulate inspired code design; security criterion; security rate; security weaknesses; sensitive data; wiretap channel; Australia; Decoding; Encoding; Generators; Parity check codes; Security; Vectors (ID#: 15-4900)


Li-Chia Choo; Cong Ling, "Superposition Lattice Coding for Gaussian Broadcast Channel with Confidential Message," Information Theory Workshop (ITW), 2014 IEEE, vol., no., pp. 311, 315, 2-5 Nov. 2014. doi:10.1109/ITW.2014.6970844
Abstract: In this paper, we propose superposition coding based on the lattice Gaussian distribution to achieve strong secrecy over the Gaussian broadcast channel with one confidential message, with a constant gap to the secrecy capacity (only for the confidential message). The proposed superposition lattice code consists of a lattice Gaussian code for the Gaussian noise and a wiretap lattice code with strong secrecy. The flatness factor is used to analyze the error probability, information leakage and achievable rates. By removing the secrecy coding, we can modify our scheme to achieve the capacity of the Gaussian broadcast channel with one common and one private message without the secrecy constraint.
Keywords: Gaussian channels; broadcast channels; channel coding; error statistics; lattice theory; telecommunication security; Gaussian broadcast channel; Gaussian noise; achievable rates; confidential message; constant gap; error probability analysis; flatness factor; information leakage; lattice Gaussian code; lattice Gaussian distribution; secrecy capacity; superposition lattice coding; wiretap lattice code; Decoding; Encoding; Error probability; Gaussian distribution; Lattices; Noise; Vectors (ID#: 15-4901)


Fan Cheng, "Optimality of Routing on the Wiretap Network with Simple Network Topology," Information Theory (ISIT), 2014 IEEE International Symposium on, vol., no., pp. 786, 790, June 29 2014 – July 4 2014. doi:10.1109/ISIT.2014.6874940
Abstract: In this paper, we study the performance of routing in the Level-I/II (n1, n2) wiretap networks, consisting of a source node, a destination node, and an intermediate node. The intermediate node connects the source and the destination nodes via a set of noiseless parallel channels, with sizes n1 and n2, respectively. The information in the network may be eavesdropped by a wiretapper, who can access at most one set of channels, called a wiretap set. All the possible wiretap sets which may be accessed by the wiretapper form a wiretap pattern. A random key K is used to protect the message M. We define two decoding levels: in Level-I, only M is decoded and in Level-II, both M and K are decoded. The objective is to minimize H(K)/H(M) under perfect secrecy constraint. Our concern is whether routing is optimal in this simple network. By harnessing the power of Shannon-type inequalities, we enumerate all the wiretap patterns in the Level-I/II (3, 3) networks, and find out that gaps exist between the bounds by routing and the bounds by Shannon-type inequalities for a small fraction of all the wiretap patterns. Furthermore, we show that for some wiretap patterns, the Shannon bounds can be achieved by a linear code; i.e, routing is not optimal even in the (3, 3) case. Some subtle issues on the network models are discussed and interesting open problems are introduced.
Keywords: linear codes; network coding; telecommunication network routing; telecommunication network topology; telecommunication security; Shannon-type inequalities; destination node; eavesdropped; intermediate node; linear code; network topology; noiseless parallel channels; source node; wiretap network; wiretap pattern; wiretap set; wiretapper; Channel coding; Decoding; Network coding; Random variables; Routing (ID#: 15-4902)


Carlet, C.; Freibert, F.; Guilley, S.; Kiermaier, M.; Jon-Lark Kim; Solé, P., "Higher-Order CIS Codes," Information Theory, IEEE Transactions on, vol. 60, no. 9, pp. 5283, 5295, Sept. 2014. doi:10.1109/TIT.2014.2332468
Abstract: We introduce complementary information set codes of higher order. A binary linear code of length tk and dimension k is called a complementary information set code of order t (t-CIS code for short) if it has t pairwise disjoint information sets. The duals of such codes permit to reduce the cost of masking cryptographic algorithms against side-channel attacks. As in the case of codes for error correction, given the length and the dimension of a t-CIS code, we look for the highest possible minimum distance. In this paper, this new class of codes is investigated. The existence of good long CIS codes of order 3 is derived by a counting argument. General constructions based on cyclic and quasi-cyclic codes and on the building up construction are given. A formula similar to a mass formula is given. A classification of 3-CIS codes of length ≤ 12 is given. Nonlinear codes better than linear codes are derived by taking binary images of Z4-codes. A general algorithm based on Edmonds' basis packing algorithm from matroid theory is developed with the following property: given a binary linear code of rate 1/t, it either provides t disjoint information sets or proves that the code is not t-CIS. Using this algorithm, all optimal or best known [tk, k] codes, where t = 3, 4, . . . , 256 and 1≤ k ≤⌊256/t⌋ are shown to be t-CIS for all such k and t, except for t = 3 with k = 44 and t = 4 with k = 37.
Keywords: binary codes; cryptography; cyclic codes; error correction codes; higher order statistics; linear codes; matrix algebra; set theory; 3-CIS code classification; Edmonds basis packing algorithm; Z4-linear code; binary linear code; complementary information set; cost reduction; cryptographic algorithm; error correction codes; higher order CIS codes; masking scheme; matroid theory; pairwise disjoint information sets; quasi-cyclic codes; side channel attacks; Boolean functions; Educational institutions; Linear codes; Partitioning algorithms; Registers; Security; Silicon;( {mathbb Z}_{4}) -linear codes; Boolean functions; Dual distance; quasi-cyclic codes (ID#: 15-4903)


Articles listed on these pages have been found on publicly available internet pages and are cited with links to those pages. Some of the information included herein has been reprinted with permission from the authors or data repositories. Direct any requests via Email to for removal of the links or modifications to specific citations. Please include the ID# of the specific citation in your correspondence.