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

Fang-Wei Fu

Fang-Wei Fu 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 Securitymath.RAmath.COmath.NT

Catalog footprint

What is connected

43works
6topics
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

43 published item(s)

preprint2023arXiv

Bent Partitions, Vectorial Dual-Bent Functions and Partial Difference Sets

It is known that partial spreads is a class of bent partitions. In \cite{AM2022Be,MP2021Be}, two classes of bent partitions whose forms are similar to partial spreads were presented. In \cite{AKM2022Ge}, more bent partitions $Γ_{1}, Γ_{2}, Γ_{1}^{\bullet}, Γ_{2}^{\bullet}, Θ_{1}, Θ_{2}$ were presented from (pre)semifields, including the bent partitions given in \cite{AM2022Be,MP2021Be}. In this paper, we investigate the relations between bent partitions and vectorial dual-bent functions. For any prime $p$, we show that one can generate certain bent partitions (called bent partitions satisfying Condition $\mathcal{C}$) from certain vectorial dual-bent functions (called vectorial dual-bent functions satisfying Condition A). In particular, when $p$ is an odd prime, we show that bent partitions satisfying Condition $\mathcal{C}$ one-to-one correspond to vectorial dual-bent functions satisfying Condition A. We give an alternative proof that $Γ_{1}, Γ_{2}, Γ_{1}^{\bullet}, Γ_{2}^{\bullet}, Θ_{1}, Θ_{2}$ are bent partitions. We present a secondary construction of vectorial dual-bent functions, which can be used to generate more bent partitions. We show that any ternary weakly regular bent function $f: V_{n}^{(3)}\rightarrow \mathbb{F}_{3}$ ($n$ even) of $2$-form can generate a bent partition. When such $f$ is weakly regular but not regular, the generated bent partition by $f$ is not coming from a normal bent partition, which answers an open problem proposed in \cite{AM2022Be}. We give a sufficient condition on constructing partial difference sets from bent partitions, and when $p$ is an odd prime, we provide a characterization of bent partitions satisfying Condition $\mathcal{C}$ in terms of partial difference sets.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Bounds and Constructions of Singleton-Optimal Locally Repairable Codes with Small Localities

Constructions of optimal locally repairable codes (LRCs) achieving Singleton-type bound have been exhaustively investigated in recent years. In this paper, we consider new bounds and constructions of Singleton-optimal LRCs with minmum distance $d=6$, locality $r=3$ and minimum distance $d=7$ and locality $r=2$, respectively. Firstly, we establish equivalent connections between the existence of these two families of LRCs and the existence of some subsets of lines in the projective space with certain properties. Then, we employ the line-point incidence matrix and Johnson bounds for constant weight codes to derive new improved bounds on the code length, which are tighter than known results. Finally, by using some techniques of finite field and finite geometry, we give some new constructions of Singleton-optimal LRCs, which have larger length than previous ones.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

New results on vectorial dual-bent functions and partial difference sets

Bent functions $f: V_{n}\rightarrow \mathbb{F}_{p}$ with certain additional properties play an important role in constructing partial difference sets, where $V_{n}$ denotes an $n$-dimensional vector space over $\mathbb{F}_{p}$, $p$ is an odd prime. In \cite{Cesmelioglu1,Cesmelioglu2}, the so-called vectorial dual-bent functions are considered to construct partial difference sets. In \cite{Cesmelioglu1}, Çeşmelioǧlu \emph{et al.} showed that for vectorial dual-bent functions $F: V_{n}\rightarrow V_{s}$ with certain additional properties, the preimage set of $0$ for $F$ forms a partial difference set. In \cite{Cesmelioglu2}, Çeşmelioǧlu \emph{et al.} showed that for a class of Maiorana-McFarland vectorial dual-bent functions $F: V_{n}\rightarrow \mathbb{F}_{p^s}$, the preimage set of the squares (non-squares) in $\mathbb{F}_{p^s}^{*}$ for $F$ forms a partial difference set. In this paper, we further study vectorial dual-bent functions and partial difference sets. We prove that for vectorial dual-bent functions $F: V_{n}\rightarrow \mathbb{F}_{p^s}$ with certain additional properties, the preimage set of the squares (non-squares) in $\mathbb{F}_{p^s}^{*}$ for $F$ and the preimage set of any coset of some subgroup of $\mathbb{F}_{p^s}^{*}$ for $F$ form partial difference sets. Furthermore, explicit constructions of partial difference sets are yielded from some (non)-quadratic vectorial dual-bent functions. In this paper, we illustrate that almost all the results of using weakly regular $p$-ary bent functions to construct partial difference sets are special cases of our results.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Polynomial-Time Key Recovery Attack on the Lau-Tan Cryptosystem Based on Gabidulin Codes

This paper presents a key recovery attack on the cryptosystem proposed by Lau and Tan in a talk at ACISP 2018. The Lau-Tan cryptosystem uses Gabidulin codes as the underlying decodable code. To hide the algebraic structure of Gabidulin codes, the authors chose a matrix of column rank $n$ to mix with a generator matrix of the secret Gabidulin code. The other part of the public key, however, reveals crucial information about the private key. Our analysis shows that the problem of recovering the private key can be reduced to solving a multivariate linear system over the base field, rather than solving a multivariate quadratic system as claimed by the authors. Solving the linear system for any nonzero solution permits us to recover the private key. Apparently, this attack costs polynomial time, and therefore completely breaks the cryptosystem.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Post-quantum Multi-stage Secret Sharing Schemes using Inhomogeneous Linear Recursion and Ajtai's Function

Secret sharing was firstly proposed in 1979 by Shamir and Blakley respectively. To avoid deficiencies of original schemes, researchers presented improvement schemes, among which the multi-secret sharing scheme (MSS) is significant. There are three categories of MSSs, however, we focus on multi-stage secret sharing scheme (MSSS) recovering secrets with any order in this work. By observing inhomogeneous linear recursions (ILRs) in the literature, we conclude a general formula and divide ILRs into two types according to different variables in them. Utilizing these two kinds of ILRs, we propose four verifiable MSSSs with Ajtai's function, which is a lattice-based function. Our schemes have the following advantages. Firstly, our schemes can detect cheat of the dealer and participants, and are multi-use. Secondly, we have several ways to restore secrets. Thirdly, we can turn our schemes into other types of MSSs due to the universality of our method. Fourthly, since we utilize a lattice-based function to mask shares, our schemes can resist the attack from the quantum computer with computational security. Finally, although our schemes need more memory consumption than some known schemes, we need much less time consumption, which makes our schemes more suitable facing limited computing power.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Semilinear Transformations in Coding Theory: A New Technique in Code-Based Cryptography

This paper presents a new technique for disturbing the algebraic structure of linear codes in code-based cryptography. This is a new attempt to exploit Gabidulin codes in the McEliece setting and almost all the previous cryptosystems of this type have been completely or partially broken. To be specific, we introduce the so-called semilinear transformation in coding theory, which is defined through an $\mathbb{F}_q$-linear automorphism of $\mathbb{F}_{q^m}$, then apply them to construct a public key encryption scheme. Our analysis shows that this scheme can resist all the existing distinguisher attacks, such as Overbeck's attack and Coggia-Couvreur attack. Meanwhile, we endow the underlying Gabidulin code with the so-called partial cyclic structure to reduce the public key size. Compared with some other code-based cryptosystems, our proposal has a much more compact representation of public keys. For instance, 2592 bytes are enough for our proposal to achieve the security of 256 bits, almost 403 times smaller than that of Classic McEliece entering the third round of the NIST PQC project.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Some New Constructions of Generalized Plateaued Functions

Plateaued functions as an extension of bent functions play a significant role in cryptography, coding theory, sequences and combinatorics. In \cite{Mesnager9}, Mesnager \emph{et al.} introduced generalized plateaued functions in order to study plateaued functions in the general context of generalized $p$-ary functions. In this paper, we focus on the constructions of generalized $p$-ary $s$-plateaued functions from $V_{n}$ to $\mathbb{Z}_{p^k}$, where $V_{n}$ is an $n$-dimensional vector space over $\mathbb{F}_{p}$, $p$ is a prime, $k\geq 1$ and $n+s$ is even when $p=2$. In particular, when $k=1$, the constructions in this paper are applicable for plateaued functions. Firstly, inspired by the work of Hodžić \emph{et al}. \cite{Hodzic3} for Boolean plateaued functions, we characterize generalized plateaued functions with affine Walsh supports and provide constructions of generalized plateaued functions with (non)-affine Walsh supports by spectral method. When $p=2, k=1$, our constructions of Boolean plateaued functions with (non)-affine Walsh supports provide an answer to the Open Problem 2 proposed in \cite{Hodzic3}. Secondly, based on what we called generalized indirect sum, we give constructions of generalized plateaued functions, which are also applicable for (non)-weakly regular generalized bent functions. In the end, we discuss the constructions of pairwise disjoint spectra generalized plateaued functions with (non)-affine Walsh supports and we present a construction of generalized bent functions by using pairwise disjoint spectra generalized plateaued functions as building blocks.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Some Results on the Improved Bound and Construction of Optimal $(r,δ)$ LRCs

Locally repairable codes (LRCs) with $(r,δ)$ locality were introduced by Prakash \emph{et al.} into distributed storage systems (DSSs) due to their benefit of locally repairing at least $δ-1$ erasures via other $r$ survival nodes among the same local group. An LRC achieving the $(r,δ)$ Singleton-type bound is called an optimal $(r,δ)$ LRC. Constructions of optimal $(r,δ)$ LRCs with longer code length and determining the maximal code length have been an important research direction in coding theory in recent years. In this paper, we conduct further research on the improvement of maximum code length of optimal $(r,δ)$ LRCs. For $2δ+1\leq d\leq 2δ+2$, our upper bounds largely improve the ones by Cai \emph{et al.}, which are tight in some special cases. Moreover, we generalize the results of Chen \emph{et al.} and obtain a complete characterization of optimal $(r=2, δ)$-LRCs in the sense of geometrical existence in the finite projective plane $PG(2,q)$. Within this geometrical characterization, we construct a class of optimal $(r,δ)$ LRCs based on the sunflower structure. Both the construction and upper bounds are better than previous ones.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Two Public-Key Cryptosystems Based on Expanded Gabidulin Codes

This paper presents two public key cryptosystems based on the so-called expanded Gabidulin codes, which are constructed by expanding Gabidulin codes over the base field. Exploiting the fast decoder of Gabidulin codes, we propose an efficient algorithm to decode these new codes when the noise vector satisfies a certain condition. Additionally, these new codes have an excellent error-correcting capability because of the optimality of their parent Gabidulin codes. With different masking techniques, we give two encryption schemes by using expanded Gabidulin codes in the McEliece setting. Being constructed over the base field, these two proposals can prevent the existing structural attacks using the Frobenius map. Based on the distinguisher for Gabidulin codes, we propose a distinguisher for expanded Gabidulin codes by introducing the concept of the so-called twisted Frobenius power. It turns out that the public code in our proposals seems indistinguishable from random codes under this distinguisher. Furthermore, our proposals have an obvious advantage in public key representation without using the cyclic or quasi-cyclic structure compared to some other code-based cryptosystems. To achieve the security of 256 bits, for instance, a public key size of 37583 bytes is enough for our first proposal, while around 1044992 bytes are needed for Classic McEliece selected as a candidate of the third round of the NIST PQC project.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A Note on Self-Dual Generalized Reed-Solomon Codes

A linear code is called an MDS self-dual code if it is both an MDS code and a self-dual code with respect to the Euclidean inner product. The parameters of such codes are completely determined by the code length. In this paper, we consider new constructions of MDS self-dual codes via generalized Reed-Solomon (GRS) codes and their extended codes. The critical idea of our constructions is to choose suitable evaluation points such that the corresponding (extended) GRS codes are self-dual. The evaluation set of our constructions is consists of a subgroup of finite fields and its cosets in a bigger subgroup. Four new families of MDS self-dual codes are obtained and they have better parameters than previous results in certain region. Moreover, by the Mobius action over finite fields, we give a systematic way to construct self-dual GRS codes with different evaluation points provided any known self-dual GRS codes. Specially, we prove that all the self-dual extended GRS codes over $\mathbb{F}_{q}$ with length $n< q+1$ can be constructed from GRS codes with the same parameters.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Construction of MDS Euclidean Self-Dual Codes via Two Subsets

The parameters of a $q$-ary MDS Euclidean self-dual codes are completely determined by its length and the construction of MDS Euclidean self-dual codes with new length has been widely investigated in recent years. In this paper, we give a further study on the construction of MDS Euclidean self-dual codes via generalized Reed-Solomon (GRS) codes and their extended codes. The main idea of our construction is to choose suitable evaluation points such that the corresponding (extended) GRS codes are Euclidean self-dual. Firstly, we consider the evaluation set consists of two disjoint subsets, one of which is based on the trace function, the other one is a union of a subspace and its cosets. Then four new families of MDS Euclidean self-dual codes are constructed. Secondly, we give a simple but useful lemma to ensure that the symmetric difference of two intersecting subsets of finite fields can be taken as the desired evaluation set. Based on this lemma, we generalize our first construction and provide two new families of MDS Euclidean self-dual codes. Finally, by using two multiplicative subgroups and their cosets which have nonempty intersection, we present three generic constructions of MDS Euclidean self-dual codes with flexible parameters. Several new families of MDS Euclidean self-dual codes are explicitly constructed.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

New Constructions of Optimal Cyclic (r,δ) Locally Repairable Codes from Their Zeros

An $(r, δ)$-locally repairable code ($(r, δ)$-LRC for short) was introduced by Prakash et al. \cite{Prakash2012} for tolerating multiple failed nodes in distributed storage systems, which was a generalization of the concept of $r$-LRCs produced by Gopalan et al. \cite{Gopalan2012}. An $(r, δ)$-LRC is said to be optimal if it achieves the Singleton-like bound. Recently, Chen et al. \cite{Chen2018} generalized the construction of cyclic $r$-LRCs proposed by Tamo et al. \cite{Tamo2015,Tamo2016} and constructed several classes of optimal $(r, δ)$-LRCs of length $n$ for $n\, |\, (q-1)$ or $n\,|\, (q+1)$, respectively in terms of a union of the set of zeros controlling the minimum distance and the set of zeros ensuring the locality. Following the work of \cite{Chen2018,Chen2019}, this paper first characterizes $(r, δ)$-locality of a cyclic code via its zeros. Then we construct several classes of optimal cyclic $(r, δ)$-LRCs of length $n$ for $n\, |\, (q-1)$ or $n\,|\, (q+1)$, respectively from the product of two sets of zeros. Our constructions include all optimal cyclic $(r,δ)$-LRCs proposed in \cite{Chen2018,Chen2019}, and our method seems more convenient to obtain optimal cyclic $(r, δ)$-LRCs with flexible parameters. Moreover, many optimal cyclic $(r,δ)$-LRCs of length $n$ for $n\, |\, (q-1)$ or $n\,|\, (q+1)$, respectively such that $(r+δ-1)\nmid n$ can be obtained from our method.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A new trace bilinear form on cyclic $\mathbb{F}_q$-linear $\mathbb{F}_{q^t}$-codes

Let $\mathbb{F}_q$ be a finite field of cardinality $q$, where $q$ is a power of a prime number $p$, $t\geq 2$ an even number satisfying $t \not\equiv 1 \;(\bmod \;p)$ and $\mathbb{F}_{q^t}$ an extension field of $\mathbb{F}_q$ with degree $t$. First, a new trace bilinear form on $\mathbb{F}_{q^t}^n$ which is called $Δ$-bilinear form is given, where $n$ is a positive integer coprime to $q$. Then according to this new trace bilinear form, bases and enumeration of cyclic $Δ$-self-orthogonal and cyclic $Δ$-self-dual $\mathbb{F}_q$-linear $\mathbb{F}_{q^t}$-codes are investigated when $t=2$. Furthermore, some good $\mathbb{F}_q$-linear $\mathbb{F}_{q^2}$-codes are obtained.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Constructions of Optimal Cyclic $(r,δ)$ Locally Repairable Codes

A code is said to be a $r$-local locally repairable code (LRC) if each of its coordinates can be repaired by accessing at most $r$ other coordinates. When some of the $r$ coordinates are also erased, the $r$-local LRC can not accomplish the local repair, which leads to the concept of $(r,δ)$-locality. A $q$-ary $[n, k]$ linear code $\cC$ is said to have $(r, δ)$-locality ($δ\ge 2$) if for each coordinate $i$, there exists a punctured subcode of $\cC$ with support containing $i$, whose length is at most $r + δ- 1$, and whose minimum distance is at least $δ$. The $(r, δ)$-LRC can tolerate $δ-1$ erasures in total, which degenerates to a $r$-local LRC when $δ=2$. A $q$-ary $(r,δ)$ LRC is called optimal if it meets the Singleton-like bound for $(r,δ)$-LRCs. A class of optimal $q$-ary cyclic $r$-local LRCs with lengths $n\mid q-1$ were constructed by Tamo, Barg, Goparaju and Calderbank based on the $q$-ary Reed-Solomon codes. In this paper, we construct a class of optimal $q$-ary cyclic $(r,δ)$-LRCs ($δ\ge 2$) with length $n\mid q-1$, which generalizes the results of Tamo \emph{et al.} Moreover, we construct a new class of optimal $q$-ary cyclic $r$-local LRCs with lengths $n\mid q+1$ and a new class of optimal $q$-ary cyclic $(r,δ)$-LRCs ($δ\ge 2$) with lengths $n\mid q+1$. The constructed optimal LRCs with length $n=q+1$ have the best-known length $q+1$ for the given finite field with size $q$ when the minimum distance is larger than $4$.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Constructions of Snake-in-the-Box Codes under $\ell_{\infty}$-metric for Rank Modulation

In the rank modulation scheme, Gray codes are very useful in the realization of flash memories. For a Gray code in this scheme, two adjacent codewords are obtained by using one "push-to-the-top" operation. Moreover, snake-in-the-box codes under the $\ell_{\infty}$-metric are Gray codes, which can be capable of detecting one $\ell_{\infty}$-error. In this paper, we give two constructions of $\ell_{\infty}$-snakes. On the one hand, inspired by Yehezkeally and Schwartz's construction, we present a new construction of the $\ell_{\infty}$-snake. The length of this $\ell_{\infty}$-snake is longer than the length of the $\ell_{\infty}$-snake constructed by Yehezkeally and Schwartz. On the other hand, we also give another construction of $\ell_{\infty}$-snakes by using $\mathcal{K}$-snakes and obtain the longer $\ell_{\infty}$-snakes than the previously known ones.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Left dihedral codes over Galois rings ${\rm GR}(p^2,m)$

Let $D_{2n}=\langle x,y\mid x^n=1, y^2=1, yxy=x^{-1}\rangle$ be a dihedral group, and $R={\rm GR}(p^2,m)$ be a Galois ring of characteristic $p^2$ and cardinality $p^{2m}$ where $p$ is a prime. Left ideals of the group ring $R[D_{2n}]$ are called left dihedral codes over $R$ of length $2n$, and abbreviated as left $D_{2n}$-codes over $R$. Let ${\rm gcd}(n,p)=1$ in this paper. Then any left $D_{2n}$-code over $R$ is uniquely decomposed into a direct sum of concatenated codes with inner codes ${\cal A}_i$ and outer codes $C_i$, where ${\cal A}_i$ is a cyclic code over $R$ of length $n$ and $C_i$ is a skew cyclic code of length $2$ over an extension Galois ring or principal ideal ring of $R$, and a generator matrix and basic parameters for each outer code $C_i$ is given. Moreover, a formula to count the number of these codes is obtained, the dual code for each left $D_{2n}$-code is determined and all self-dual left $D_{2n}$-codes and self-orthogonal left $D_{2n}$-codes over $R$ are presented, respectively.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Cyclic codes over $\mathbb{F}_{2^m}[u]/\langle u^k\rangle$ of oddly even length

Let $\mathbb{F}_{2^m}$ be a finite field of characteristic $2$ and $R=\mathbb{F}_{2^m}[u]/\langle u^k\rangle=\mathbb{F}_{2^m} +u\mathbb{F}_{2^m}+\ldots+u^{k-1}\mathbb{F}_{2^m}$ ($u^k=0$) where $k\in \mathbb{Z}^{+}$ satisfies $k\geq 2$. For any odd positive integer $n$, it is known that cyclic codes over $R$ of length $2n$ are identified with ideals of the ring $R[x]/\langle x^{2n}-1\rangle$. In this paper, an explicit representation for each cyclic code over $R$ of length $2n$ is provided and a formula to count the number of codewords in each code is given. Then a formula to calculate the number of cyclic codes over $R$ of length $2n$ is obtained. Moreover, the dual code of each cyclic code and self-dual cyclic codes over $R$ of length $2n$ are investigated. (AAECC-1522)

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On double cyclic codes over Z_4

Let $R=\mathbb{Z}_4$ be the integer ring mod $4$. A double cyclic code of length $(r,s)$ over $R$ is a set that can be partitioned into two parts that any cyclic shift of the coordinates of both parts leaves invariant the code. These codes can be viewed as $R[x]$-submodules of $R[x]/(x^r-1)\times R[x]/(x^s-1)$. In this paper, we determine the generator polynomials of this family of codes as $R[x]$-submodules of $R[x]/(x^r-1)\times R[x]/(x^s-1)$. Further, we also give the minimal generating sets of this family of codes as $R$-submodules of $R[x]/(x^r-1)\times R[x]/(x^s-1)$. Some optimal or suboptimal nonlinear binary codes are obtained from this family of codes. Finally, we determine the relationship of generators between the double cyclic code and its dual.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On the Optimality of Secure Network Coding

In network communications, information transmission often encounters wiretapping attacks. Secure network coding is introduced to prevent information from being leaked to adversaries. The investigation of performance bounds on the numbers of source symbols and random symbols are two fundamental research problems. For an important case that each wiretap-set with cardinality not larger than $r$, Cai and Yeung proposed a coding scheme, which is optimal in the senses of maximizing the number of source symbols and at the same time minimizing the number of random symbols. In this letter, we further study achievable lower bound on the number of random key and show that it just depends on the security constraint, and particularly, is independent to the information amount for transmission. This implies that when the number of transmitted source message changes, we can't reduce the number of random key to keep the same security level. We further give an intuitive interpretation on our result. In addition, a similar construction of secure linear network codes is proposed, which achieves this lower bound on the number of random key no matter how much information is transmitted. At last, we also extend our result to imperfect security case.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Repairable Threshold Secret Sharing Schemes

In this paper, we propose a class of threshold secret sharing schemes with repairing function between shares without the help of the dealer, that we called repairable threshold secret sharing schemes. Specifically, if a share fails, such as broken or lost, it will be repaired just by some other shares. A construction of such repairable threshold secret sharing schemes is designed by applying linearized polynomials and regenerating codes in distributed storage systems. In addition, a new repairing rate is introduced to characterize the performance and efficiency of the repairing function. Then an achievable upper bound on the repairing rate is derived, which implies the optimality of the repair and describes the security between different shares. Under this optimality of the repair, we further discuss traditional information rate and also indicate its optimality, that can describe the efficiency of secret sharing schemes in the aspect of storage. Finally, by applying the minimum bandwidth regenerating (MBR) codes, our construction designs repairable threshold secret sharing schemes achieving both optimal repairing and information rates simultaneously.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Distributed Storage over Unidirectional Ring Networks

In this paper, we study distributed storage problems over unidirectional ring networks, whose storage nodes form a directed ring and data is transmitted along the same direction. The original data is distributed to store on these nodes. Each user can connect one and only one storage node to download the total data. A lower bound on the reconstructing bandwidth to recover the original data for each user is proposed, and it is achievable for arbitrary parameters. If a distributed storage scheme can achieve this lower bound with equality for every user, we say it an optimal reconstructing distributed storage scheme (ORDSS). Furthermore, the repair problem for a failed storage node in ORDSSes is under consideration and a tight lower bound on the repair bandwidth is obtained. In particular, we indicate the fact that for any ORDSS, every storage node can be repaired with repair bandwidth achieving the lower bound with equality. In addition, we present two constructions for ORDSSes of arbitrary parameters, called MDS construction and ED construction, respectively. Particularly, ED construction, by using the concept of Euclidean division, is more efficient by our analysis in detail.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Distributed Storage Schemes over Unidirectional Ring Networks

In this paper, we study distributed storage problems over unidirectional ring networks. A lower bound on the reconstructing bandwidth to recover total original data for each user is proposed, and it is achievable for arbitrary parameters. If a distributed storage scheme can achieve this lower bound with equality for each user, we say it an optimal reconstructing distributed storage scheme (ORDSS). Furthermore, the repair problem for a failed storage node in ORDSSes is under consideration and a tight lower bound on the repair bandwidth for each storage node is obtained. Particularly, we indicate the fact that for any ORDSS, every storage node can be repaired with repair bandwidth achieving the lower bound with equality. In addition, we present an efficient approach to construct ORDSSes for arbitrary parameters by using the concept of Euclidean division. Finally, we take an example to characterize the above approach.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

On Linear Codes over $\mathbb{Z}_4+v\mathbb{Z}_4$

Linear codes are considered over the ring $\mathbb{Z}_4+v\mathbb{Z}_4$, where $v^2=v$. Gray weight, Gray maps for linear codes are defined and MacWilliams identity for the Gray weight enumerator is given. Self-dual codes, construction of Euclidean isodual codes, unimodular complex lattices, MDS codes and MGDS codes over $\mathbb{Z}_4+v\mathbb{Z}_4$ are studied. Cyclic codes and quadratic residue codes are also considered. Finally, some examples for illustrating the main work are given.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Self-dual codes and quadratic residue codes over the ring $\mathbb{Z}_9+u\mathbb{Z}_9$

In this paper, we introduce a new definitions of the Gray weight and the Gray map for linear codes over $\mathbb{Z}_9+u\mathbb{Z}_9$ with $u^2=u$. Some results on self-dual codes over this ring are investigated. Further, the structural properties of quadratic residue codes are also considered. Two self-dual codes with parameters $[22,11,5]$ and $[24,12,9]$ over $\mathbb{Z}_9$ are obtained.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Small Field Size for Secure Network Coding

In network coding, information transmission often encounters wiretapping attacks. Secure network coding is introduced to prevent information from being leaked to adversaries. For secure linear network codes (SLNCs), the required field size is a very important index, because it largely determines the computational and space complexities of a SLNC, and it is also very important for the process of secure network coding from theoretical research to practical application. In this letter, we further discuss the required field size of SLNCs, and obtain a new lower bound. This bound shows that the field size of SLNCs can be reduced further, and much smaller than the known results for almost all cases.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Variable-Rate Linear Network Error Correction MDS Codes

In network communication, the source often transmits messages at several different information rates within a session. How to deal with information transmission and network error correction simultaneously under different rates is introduced in this paper as a variable-rate network error correction problem. Apparently, linear network error correction MDS codes are expected to be used for these different rates. For this purpose, designing a linear network error correction MDS code based on the existing results for each information rate is an efficient solution. In order to solve the problem more efficiently, we present the concept of variable-rate linear network error correction MDS codes, that is, these linear network error correction MDS codes of different rates have the same local encoding kernel at each internal node. Further, we propose an approach to construct such a family of variable-rate network MDS codes and give an algorithm for efficient implementation. This approach saves the storage space for each internal node, and resources and time for the transmission on networks. Moreover, the performance of our proposed algorithm is analyzed, including the field size, the time complexity, the encoding complexity at the source node, and the decoding methods. Finally, a random method is introduced for constructing variable-rate network MDS codes and we obtain a lower bound on the success probability of this random method, which shows that this probability will approach to one as the base field size goes to infinity.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

An Authentication Scheme for Subspace Codes over Network Based on Linear Codes

Network coding provides the advantage of maximizing the usage of network resources, and has great application prospects in future network communications. However, the properties of network coding also make the pollution attack more serious. In this paper, we give an unconditional secure authentication scheme for network coding based on a linear code $C$. Safavi-Naini and Wang gave an authentication code for multi-receivers and multiple messages. We notice that the scheme of Safavi-Naini and Wang is essentially constructed with Reed-Solomon codes. And we modify their construction slightly to make it serve for authenticating subspace codes over linear network. Also, we generalize the construction with linear codes. The generalization to linear codes has the similar advantages as generalizing Shamir's secret sharing scheme to linear secret sharing sceme based on linear codes. One advantage of this generalization is that for a fixed message space, our scheme allows arbitrarily many receivers to check the integrity of their own messages, while the scheme with Reed-Solomon codes has a constraint on the number of verifying receivers. Another advantage is that we introduce access structure in the generalized scheme. Massey characterized the access structure of linear secret sharing scheme by minimal codewords in the dual code whose first component is 1. We slightly modify the definition of minimal codewords. Let $C$ be a $[V,k]$ linear code. For any coordinate $i\in \{1,2,\cdots,V\}$, a codeword $\vec{c}$ in $C$ is called minimal respect to $i$ if the codeword $\vec{c}$ has component 1 at the $i$-th coordinate and there is no other codeword whose $i$-th component is 1 with support strictly contained in that of $\vec{c}$. Then the security of receiver $R_i$ in our authentication scheme is characterized by the minimal codewords respect to $i$ in the dual code $C^\bot$.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Generalized Quasi-Cyclic Codes Over $\mathbb{F}_q+u\mathbb{F}_q$

Generalized quasi-cyclic (GQC) codes with arbitrary lengths over the ring $\mathbb{F}_{q}+u\mathbb{F}_{q}$, where $u^2=0$, $q=p^n$, $n$ a positive integer and $p$ a prime number, are investigated. By the Chinese Remainder Theorem, structural properties and the decomposition of GQC codes are given. For 1-generator GQC codes, minimal generating sets and lower bounds on the minimum distance are given. As a special class of GQC codes, quasi-cyclic (QC) codes over $\mathbb{F}_q+u\mathbb{F}_q$ are also discussed briefly in this paper.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Linear Network Error Correction Multicast/Broadcast/Dispersion Codes

In this paper, for the purposes of information transmission and network error correction simultaneously, three classes of important linear network codes in network coding, linear multicast/broadcast/dispersion codes are generalized to linear network error correction coding, i.e., linear network error correction multicast/broadcast/dispersion codes. We further propose the (weakly, strongly) extended Singleton bounds for these new classes of codes, and define the optimal codes satisfying the corresponding Singleton bounds with equality, which are called multicast/broadcast/dispersion MDS codes respectively. The existence of such codes are proved by an algebraic method and one kind of constructive algorithm is also proposed.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Linear Network Error Correction Multicast/Broadcast/Dispersion/Generic Codes

In the practical network communications, many internal nodes in the network are required to not only transmit messages but decode source messages. For different applications, four important classes of linear network codes in network coding theory, i.e., linear multicast, linear broadcast, linear dispersion, and generic network codes, have been studied extensively. More generally, when channels of communication networks are noisy, information transmission and error correction have to be under consideration simultaneously, and thus these four classes of linear network codes are generalized to linear network error correction (LNEC) coding, and we say them LNEC multicast, broadcast, dispersion, and generic codes, respectively. Furthermore, in order to characterize their efficiency of information transmission and error correction, we propose the (weakly, strongly) extended Singleton bounds for them, and define the corresponding optimal codes, i.e., LNEC multicast/broadcast/dispersion/generic MDS codes, which satisfy the corresponding Singleton bounds with equality. The existences of such MDS codes are discussed in detail by algebraic methods and the constructive algorithms are also proposed.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Multi-receiver Authentication Scheme for Multiple Messages Based on Linear Codes

In this paper, we construct an authentication scheme for multi-receivers and multiple messages based on a linear code $C$. This construction can be regarded as a generalization of the authentication scheme given by Safavi-Naini and Wang. Actually, we notice that the scheme of Safavi-Naini and Wang is constructed with Reed-Solomon codes. The generalization to linear codes has the similar advantages as generalizing Shamir's secret sharing scheme to linear secret sharing sceme based on linear codes. For a fixed message base field $\f$, our scheme allows arbitrarily many receivers to check the integrity of their own messages, while the scheme of Safavi-Naini and Wang has a constraint on the number of verifying receivers $V\leqslant q$. And we introduce access structure in our scheme. Massey characterized the access structure of linear secret sharing scheme by minimal codewords in the dual code whose first component is 1. We slightly modify the definition of minimal codewords in \cite{Massey93}. Let $C$ be a $[V,k]$ linear code. For any coordinate $i\in \{1,2,\cdots,V\}$, a codeword $\vec{c}$ in $C$ is called minimal respect to $i$ if the codeword $\vec{c}$ has component 1 at the $i$-th coordinate and there is no other codeword whose $i$-th component is 1 with support strictly contained in that of $\vec{c}$. Then the security of receiver $R_i$ in our authentication scheme is characterized by the minimal codewords respect to $i$ in the dual code $C^\bot$.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Quasi-Cyclic Codes Over Finite Chain Rings

In this paper, we mainly consider quasi-cyclic (QC) codes over finite chain rings. We study module structures and trace representations of QC codes, which lead to some lower bounds on the minimum Hamming distance of QC codes. Moreover, we investigate the structural properties of 1-generator QC codes. Under some conditions, we discuss the enumeration of 1-generator QC codes and describe how to obtain the one and only one generator for each 1-generator QC code.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Security Analysis on "An Authentication Code Against Pollution Attacks in Network Coding"

We analyze the security of the authentication code against pollution attacks in network coding given by Oggier and Fathi and show one way to remove one very strong condition they required. Actually, we find a way to attack their authentication scheme. In their scheme, they considered that if some malicious nodes in the network collude to make pollution in the network flow or make substitution attacks to other nodes, they thought these malicious nodes must solve a system of linear equations to recover the secret parameters. Then they concluded that their scheme is an unconditional secure scheme. Actually, note that the authentication tag in the scheme of Oggier and Fathi is nearly linear on the messages, so it is very easy for any malicious node to make pollution attack in the network flow, replacing the vector of any incoming edge by linear combination of his incoming vectors whose coefficients have sum 1. And if the coalition of malicious nodes can carry out decoding of the network coding, they can easily make substitution attack to any other node even if they do not know any information of the private key of the node. Moreover, even if their scheme can work fruitfully, the condition in their scheme $H\leqslant M$ in a network can be removed, where $H$ is the sum of numbers of the incoming edges at adversaries. Under the condition $H\leqslant M$, $H$ may be large, so we need large parameter $M$ which increases the cost of computation a lot. On the other hand, the parameter $M$ can not be very large as it can not exceed the length of original messages.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Skew Generalized Quasi-Cyclic Codes over Finite Fields

In this work, we study a class of generalized quasi-cyclic (GQC) codes called skew GQC codes. By the factorization theory of ideals, we give the Chinese Remainder Theorem over the skew polynomial ring, which leads to a canonical decomposition of skew GQC codes. We also focus on some characteristics of skew GQC codes in details. For a 1-generator skew GQC code, we define the parity-check polynomial, determine the dimension and give a lower bound on the minimum Hamming distance. The skew quasi-cyclic (QC) codes are also discussed briefly.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Stopping Sets of Algebraic Geometry Codes

Stopping sets and stopping set distribution of a linear code play an important role in the performance analysis of iterative decoding for this linear code. Let $C$ be an $[n,k]$ linear code over $\f$ with parity-check matrix $H$, where the rows of $H$ may be dependent. Let $[n]=\{1,2,...,n\}$ denote the set of column indices of $H$. A \emph{stopping set} $S$ of $C$ with parity-check matrix $H$ is a subset of $[n]$ such that the restriction of $H$ to $S$ does not contain a row of weight 1. The \emph{stopping set distribution} $\{T_{i}(H)\}_{i=0}^{n}$ enumerates the number of stopping sets with size $i$ of $C$ with parity-check matrix $H$. Denote $H^{*}$ the parity-check matrix consisting of all the non-zero codewords in the dual code $C^{\bot}$. In this paper, we study stopping sets and stopping set distributions of some residue algebraic geometry (AG) codes with parity-check matrix $H^*$. First, we give two descriptions of stopping sets of residue AG codes. For the simplest AG codes, i.e., the generalized Reed-Solomon codes, it is easy to determine all the stopping sets. Then we consider AG codes from elliptic curves. We use the group structure of rational points of elliptic curves to present a complete characterization of stopping sets. Then the stopping sets, the stopping set distribution and the stopping distance of the AG code from an elliptic curve are reduced to the search, counting and decision versions of the subset sum problem in the group of rational points of the elliptic curve, respectively. Finally, for some special cases, we determine the stopping set distributions of AG codes from elliptic curves.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

The Failure Probability of Random Linear Network Coding for Networks

In practice, since many communication networks are huge in scale, or complicated in structure, or even dynamic, the predesigned linear network codes based on the network topology is impossible even if the topological structure is known. Therefore, random linear network coding has been proposed as an acceptable coding technique for the case that the network topology cannot be utilized completely. Motivated by the fact that different network topological information can be obtained for different practical applications, we study the performance analysis of random linear network coding by analyzing some failure probabilities depending on these different topological information of networks. We obtain some tight or asymptotically tight upper bounds on these failure probabilities and indicate the worst cases for these bounds, i.e., the networks meeting the upper bounds with equality. In addition, if the more topological information of the network is utilized, the better upper bounds are obtained. On the other hand, we also discuss the lower bounds on the failure probabilities.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

New Deep Holes of Generalized Reed-Solomon Codes

Deep holes play an important role in the decoding of generalized Reed-Solomon codes. Recently, Wu and Hong \cite{WH} found a new class of deep holes for standard Reed-Solomon codes. In the present paper, we give a concise method to obtain a new class of deep holes for generalized Reed-Solomon codes. In particular, for standard Reed-Solomon codes, we get the new class of deep holes given in \cite{WH}. Li and Wan \cite{L.W1} studied deep holes of generalized Reed-Solomon codes $GRS_{k}(\f,D)$ and characterized deep holes defined by polynomials of degree $k+1$. They showed that this problem is reduced to be a subset sum problem in finite fields. Using the method of Li and Wan, we obtain some new deep holes for special Reed-Solomon codes over finite fields with even characteristic. Furthermore, we study deep holes of the extended Reed-Solomon code, i.e., $D=\f$ and show polynomials of degree $k+2$ can not define deep holes.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Construction of Network Error Correction Codes in Packet Networks

Recently, network error correction coding (NEC) has been studied extensively. Several bounds in classical coding theory have been extended to network error correction coding, especially the Singleton bound. In this paper, following the research line using the extended global encoding kernels proposed in \cite{zhang-correction}, the refined Singleton bound of NEC can be proved more explicitly. Moreover, we give a constructive proof of the attainability of this bound and indicate that the required field size for the existence of network maximum distance separable (MDS) codes can become smaller further. By this proof, an algorithm is proposed to construct general linear network error correction codes including the linear network error correction MDS codes. Finally, we study the error correction capability of random linear network error correction coding. Motivated partly by the performance analysis of random linear network coding \cite{Ho-etc-random}, we evaluate the different failure probabilities defined in this paper in order to analyze the performance of random linear network error correction coding. Several upper bounds on these probabilities are obtained and they show that these probabilities will approach to zero as the size of the base field goes to infinity. Using these upper bounds, we slightly improve on the probability mass function of the minimum distance of random linear network error correction codes in \cite{zhang-random}, as well as the upper bound on the field size required for the existence of linear network error correction codes with degradation at most $d$.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

New Results on Two Hypercube Coloring Problems

In this paper, we study the following two hypercube coloring problems: Given $n$ and $d$, find the minimum number of colors, denoted as $χ'_{d}(n)$ (resp. $χ_{d}(n)$), needed to color the vertices of the $n$-cube such that any two vertices with Hamming distance at most $d$ (resp. exactly $d$) have different colors. These problems originally arose in the study of the scalability of optical networks. Using methods in coding theory, we show that $χ'_{4}(2^{r+1}-1)=2^{2r+1}$, $χ'_{5}(2^{r+1})=4^{r+1}$ for any odd number $r\geq3$, and give two upper bounds on $χ_{d}(n)$. The first upper bound improves on that of Kim, Du and Pardalos. The second upper bound improves on the first one for small $n$. Furthermore, we derive an inequality on $χ_{d}(n)$ and $χ'_{d}(n)$.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

On Random Linear Network Coding for Butterfly Network

Random linear network coding is a feasible encoding tool for network coding, specially for the non-coherent network, and its performance is important in theory and application. In this letter, we study the performance of random linear network coding for the well-known butterfly network by analyzing the failure probabilities. We determine the failure probabilities of random linear network coding for the well-known butterfly network and the butterfly network with channel failure probability p.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Stopping Set Distributions of Some Linear Codes

Stopping sets and stopping set distribution of an low-density parity-check code are used to determine the performance of this code under iterative decoding over a binary erasure channel (BEC). Let $C$ be a binary $[n,k]$ linear code with parity-check matrix $H$, where the rows of $H$ may be dependent. A stopping set $S$ of $C$ with parity-check matrix $H$ is a subset of column indices of $H$ such that the restriction of $H$ to $S$ does not contain a row of weight one. The stopping set distribution $\{T_i(H)\}_{i=0}^n$ enumerates the number of stopping sets with size $i$ of $C$ with parity-check matrix $H$. Note that stopping sets and stopping set distribution are related to the parity-check matrix $H$ of $C$. Let $H^{*}$ be the parity-check matrix of $C$ which is formed by all the non-zero codewords of its dual code $C^{\perp}$. A parity-check matrix $H$ is called BEC-optimal if $T_i(H)=T_i(H^*), i=0,1,..., n$ and $H$ has the smallest number of rows. On the BEC, iterative decoder of $C$ with BEC-optimal parity-check matrix is an optimal decoder with much lower decoding complexity than the exhaustive decoder. In this paper, we study stopping sets, stopping set distributions and BEC-optimal parity-check matrices of binary linear codes. Using finite geometry in combinatorics, we obtain BEC-optimal parity-check matrices and then determine the stopping set distributions for the Simplex codes, the Hamming codes, the first order Reed-Muller codes and the extended Hamming codes.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

The Failure Probability at Sink Node of Random Linear Network Coding

In practice, since many communication networks are huge in scale or complicated in structure even dynamic, the predesigned network codes based on the network topology is impossible even if the topological structure is known. Therefore, random linear network coding was proposed as an acceptable coding technique. In this paper, we further study the performance of random linear network coding by analyzing the failure probabilities at sink node for different knowledge of network topology and get some tight and asymptotically tight upper bounds of the failure probabilities. In particular, the worst cases are indicated for these bounds. Furthermore, if the more information about the network topology is utilized, the better upper bounds are obtained. These bounds improve on the known ones. Finally, we also discuss the lower bound of this failure probability and show that it is also asymptotically tight.

0 citations0 reviewsNo code linkedOpen access