Fang-Wei Fu

Jing Qiu, Weijun Fang, Shu-Tao Xia et al.

Maximum distance separable (MDS) codes are widely used in distributed storage, but naively repairing a single failure in an $(n,k)$ MDS code requires downloading the full contents of $k$ surviving nodes. Minimum storage regenerating (MSR) codes, introduced by Dimakis et al., minimize repair bandwidth while preserving the MDS property by contacting $d>k$ helper nodes and downloading only a fraction of each helper. For scalar MDS codes, Guruswami and Wootters established a linear repair framework, and Tamo, Ye, and Barg subsequently gave the first explicit Reed-Solomon (RS) codes achieving the MSR point. Their construction yields RS-MSR codes with subpacketization $\ell=s\prod_{i=1}^n p_i$, where $s=d+1-k$ and the distinct primes $p_i$ satisfy $p_i\equiv 1\pmod{s}$. In this paper, we show that this congruence condition is not intrinsic to the RS repair problem. We develop a basis-transformation approach to the construction of repair-enabling subspaces. The approach consists of three deterministic operations -- Euclidean Square Partition, Transposition, and Column Aggregation -- which construct the required repair-enabling subspaces directly from the standard monomial basis of the repair field. Consequently, we obtain RS-MSR codes with subpacketization $\ell=s\prod_{i=1}^n p_i$ for arbitrary distinct primes $p_i>s$. For fixed $s$, this improves the subpacketization of the Tamo--Ye--Barg construction by a factor asymptotic to $φ(s)^{n+\mathrm{o}(n)}$, where $φ(\cdot)$ denotes Euler's totient function.

Xiaofeng Liu, Jun Zhang, Fang-Wei Fu

Motivated by the studies of twisted generalized Reed-Solomon (TGRS) codes, we initiate the study of twisted elliptic curve codes (TECCs) in this paper. In particular, we study a class of TECCs with one twist. The parity-check matrices of the TECCs are explicitly given by computing the Weil differentials. Then the sufficient and necessary conditions of self-duality are presented. The minimum distances of the TECCs are also determined. Moreover, examples of MDS, AMDS, self-dual and MDS self-dual TECCs are given. Finally, we calculate the dimensions of the Schur squares of TECCs and show the non-equivalence between TECCs and ECCs/GRS codes.

Xiaofeng Liu, Jun Zhang, Fang-Wei Fu

Motivated by the constructions of binary sequences by utilizing the cyclic elliptic function fields over the finite field $\mathbb{F}_{2^{n}}$ by Jin \textit{et al.} in [IEEE Trans. Inf. Theory 71(8), 2025], we extend the construction to the cyclic elliptic function fields with odd characteristic by using the quadratic residue map $η$ instead of the trace map used therein. For any cyclic elliptic function field with $q+1+t$ rational points and any positive integer $d$ with $\gcd(d, q+1+t)=1$, we construct a new family of binary sequences of length $q+1+t$, size $q^{d-1}-1$, balance upper bounded by $(d+1)\cdot\lfloor2\sqrt{q}\rfloor+|t|+d,$ the correlation upper bounded by $(2d+1)\cdot\lfloor2\sqrt{q}\rfloor+|t|+2d$ and the linear complexity lower bounded by $\frac{q+1+2t-d-(d+1)\cdot\lfloor2\sqrt{q}\rfloor}{d+d\cdot\lfloor2\sqrt{q}\rfloor}$ where $\lfloor x\rfloor$ stands for the integer part of $x\in\mathbb{R}$.

Xiang Wang, Weijun Fang, Han Li et al.

Levenshtein first introduced the sequence reconstruction problem in $2001$. In the realm of combinatorics, the sequence reconstruction problem is equivalent to determining the value of $N(n,d,t)$, which represents the maximum size of the intersection of two metric balls of radius $t$, given that the distance between their centers is at least $d$ and the sequence length is $n$. In this paper, We present a lower bound on $N(n,3,t)$ for $n\geq \max\{13,t+8\}$ and $t \geq 4$. For $t=4$, we prove that this lower bound is tight. This settles an open question posed by Pham, Goyal, and Kiah, confirming that $N(n,3,4)=20n-166$ for all $n \geq 13$.

Jiaqi Liu, Yuanyi Zhang, Fang-Wei Fu

We construct a lattice-based ciphertext-policy attribute-based encryption (CP-ABE) scheme for $\mathsf{NC}^1$ access policies with constant-size ciphertexts. Let $λ$ be the security parameter. For an $\mathsf{NC}^1$ circuit of depth $d$ and size $s$ on $\ell$-bit inputs, our scheme has the public-key and ciphertext sizes $O(1)$ (independent of $d$), and secret-key size $O(\ell)$, where the $O(\cdot)$ hides $\operatorname{poly}(λ)$ factors. As an application, we obtain a broadcast encryption scheme for $N$ users with ciphertext size $\operatorname{poly}(λ)$ independent of $\log N$ and key sizes $\operatorname{poly}(λ,\log N)$. Our construction is selectively secure in the standard model under the $\operatorname{poly}(λ)$-succinct LWE assumption introduced by Wee (CRYPTO~2024).

Hengfeng Jin, Fang-Wei Fu

In recent years, locally repairable codes (LRCs) have attracted considerable attention owing to their pivotal role in distributed storage systems. Since binary linear locally repairable codes can significantly reduce the complexity of both encoding and decoding processes, the construction of binary LRCs has attracted extensive research interest. In this paper, we construct locally repairable codes via concatenated codes and present a systematic approach to select outer codes to obtain optimal binary LRCs, where the outer codes are linear codes over $\mathbb{F}_4$. The weight distributions of the resulting LRCs are determined by the weight distributions of the selected linear codes over $\mathbb{F}_4$. Furthermore, several classes of optimal binary locally repairable codes are constructed, including binary LRCs meeting the Griesmer-like bound, and binary perfect LRCs. Meanwhile, for the locality $r=2$, we improve the Johnson-like bound for binary LRCs with disjoint local repair groups established by Ma and Ge, and construct explicit LRCs that attain this new bound.

Han Li, Xiang Wang, Fang-Wei Fu

In the deletion channel, an important problem is to determine the number of subsequences derived from a string $U$ of length $n$ when subjected to $t$ deletions. It is well-known that the number of subsequences in the setting exhibits a strong dependence on the number of runs in the string $U$, where a run is defined as a maximal substring of identical characters. In this paper we study the number of subsequences of a non-binary string in this scenario, and propose some improved bounds on the number of subsequences of $r$-run non-binary strings. Specifically, we characterize a family of $r$-run non-binary strings with the maximum number of subsequences under any $t$ deletions, and show that this number can be computed in polynomial time.

Qin Zhou, Fang-Wei Fu

Secure network function computation is a critical research direction in network coding, which aims to ensure that the target function is correctly computed at the sink node while preventing the wiretapper from obtaining any information about the security function. In this paper, we focus on the general secure network function computation model, where the target function f and the security function ζ are arbitrary, and the wiretapper can eavesdrop on any subset of edges with size at most a given security level. Using information-theoretic techniques, we establish a nontrivial upper bound on the secure computing capacity, which is applicable to arbitrary networks, arbitrary target and security functions, and arbitrary security levels. This upper bound is shown to degenerate to the existing bounds in the literature when the target and security functions are specific forms. Furthermore, we consider two specific models: one where the target function is vector-linear and the security function is the identity function, and another where both functions are vector-linear. For the former, we derive a simplified form of the upper bound on the secure computing capacity via order-theoretic methods and propose an efficient algorithm to compute this bound with linear time complexity in the number of network edges. For the latter, we characterize the equivalent conditions for the computability and security of linear secure network codes, develop two constructive schemes for such codes, and derive an upper bound on the minimal finite field size required for the constructions, thereby obtaining a nontrivial lower bound on the secure computing capacity.

Wei Zhao, Fang-Wei Fu, Ximing Fu

For scalar maximum distance separable (MDS) codes, the conventional repair schemes that achieve the cut-set bound with equality for the single-node repair have been proven to require a super-exponential sub-packetization level.As is well known, such an extremely high level severely limits the practical deployment of MDS codes.To address this challenge, we introduce a partial-exclusion (PE) repair scheme for scalar linear codes.In the proposed PE repair framework, each node is associated with an exclusion set.The cardinality of the exclusion set is called the flexibility of the node.The maximum value of flexibility over all nodes defines the \textit{flexibility} of the PE repair scheme. Notably, the conventional repair scheme is the special case of PE repair scheme where the flexibility is 1. Under the PE repair framework, for any valid flexibility, we establish a lower bound on the sub-packetization level of MDS codes that meet the cut-set bound with equality for single-node repair. To realize MDS codes attaining the cut-set bound under the PE repair framework, we propose two generic constructions of Reed-Solomon (RS) codes. Moreover, we demonstrate that for a sufficiently large flexibility, the sub-packetization level of our constructions is strictly lower than the known lower bound established for the conventional repair schemes.This implies that, from the perspective of sub-packetization level, our constructions outperform all existing and potential constructions designed for conventional repair schemes. Finally, we implement the repair process for these codes as executable Magma programs, thereby exhibiting the practical efficiency of our constructions.

Jing Yang, Fang-Wei Fu

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.

Wenshuo Guo, Fang-Wei Fu

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.

Jing Yang, Fang-Wei Fu

Secret sharing was proposed primarily in 1979 to solve the problem of key distribution. In recent decades, researchers have proposed many improvement schemes. Among all these schemes, the verifiable multi-secret sharing (VMSS) schemes are studied sufficiently, which share multiple secrets simultaneously and perceive malicious dealer as well as participants. By pointing out that the schemes presented by Dehkordi and Mashhadi in 2008 cannot detect some vicious behaviors of the dealer, we propose two new VMSS schemes by adding validity check in the verification phase to overcome this drawback. Our new schemes are based on XTR public key system, and can realize $GF(p^{6})$ security by computations in $GF(p^{2})$ without explicit constructions of $GF(p^{6})$, where $p$ is a prime. Compared with the VMSS schemes using RSA and linear feedback shift register (LFSR) public key cryptosystems, our schemes can achieve the same security level with shorter parameters by using trace function. What's more, our schemes are much simpler to operate than those schemes based on Elliptic Curve Cryptography (ECC). In addition, our schemes are dynamic and threshold changeable, which means that it is efficient to implement our schemes according to the actual situation when participants, secrets or the threshold needs to be changed.

Jing Yang, Fang-Wei Fu

A verifiable multi-secret sharing (VMSS) scheme enables the dealer to share multiple secrets, and the deception of both participants and the dealer can be detected. After analyzing the security of VMSS schemes proposed by Mashhadi and Dehkordi in 2015, we illustrate that they cannot detect some deception of the dealer. By using nonhomogeneous linear recursion and LFSR public key cryptosystem, we introduce two new VMSS schemes. Our schemes can not only overcome the drawback mentioned above, but also have shorter private/public key length at the same safety level. Besides, our schemes have dynamism.

Xuan Guang, Jiyong Lu, Fang-Wei Fu

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.

Jun Zhang, Xinran Li, Fang-Wei Fu

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$.

Jun Zhang, Xinran Li, Fang-Wei Fu

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$.

Jun Zhang, Xinran Li, Fang-Wei Fu

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.