## 编码及相关数学理论系列报告九则

Since the mid 2000s, asymptotically-good strongly-multiplicative linear (ramp) secret sharing schemes over a fixed finite field have turned out as a central theoretical primitive in numerous constant-communication-rate results in multi-party cryptographic scenarios, and, surprisingly, in two-party cryptography as well.

Known constructions of this most powerful class of arithmetic secret sharing schemes all rely heavily on algebraic geometry (AG). It is a well-known open question since the first (explicit) constructions of such schemes appeared in CRYPTO 2006 whether the use of heavy machinery'' can be avoided here. i.e., the question is whether the mere existence of such schemes can also be proved by elementary'' techniques only (say, from classical algebraic coding theory), even disregarding effective construction. So far, there is no progress.

In this talk we show the theoretical result that, no matter whether this open question has an affirmative answer or not, these schemes can be constructed  explicitly by elementary algorithms defined in terms of basic algebraic coding theory. This pertains to all relevant operations associated to such schemes, including, notably, the generation of an instance for a given number of players n, as well as error correction in the presence of corrupt shares.

Arikan于2009年提出的极化码不仅可以达到信道容量，并且具有高效快速的编码和译码算法，是纠错编码理论领域近年来的一大突破，已广泛应用于5G通信、光纤通信、量子通信、深度学习以及信息安全等众多领域。本文主要研究作为二元输入离散无记忆信道（Binary-Input Discrete Memoryless Channel，BIDMC）W上的极化码的推广——混合多核极化码的极化性：占比接近W的对称容量I(W)的部分虚拟信道近似于无噪的可靠信道，同时占比接近1-I(W)的部分虚拟信道近似于纯噪声信道。js345金沙城娱乐场线路将极化码构造中通用的信道组合与分裂策略（Combining and Splitting Tactics，CAST）进行了推广，对混合多核极化码的编码矩阵与递归构造中使用的各CAST的核矩阵之间的关系给出了明确的表达，并利用随机切换信道和并行广播信道的概念，首次对混合多核极化码的极化性给出了严格证明。

：王丽萍 研究员

Information set decoding (ISD) is well known as the best attack against the syndrome decoding (SD) problem. Recently, Horlemann-Trautmann and Weger converted Stern’s ISD algorithm from Hamming metric over F2 to Lee metric over Z4. In this paper, we use the Wagner algorithm with two floors to solve the SD problem over Z4 under Lee metric. Compared with the above Stern’s algorithm in Lee metric, our algorithm has a significant improvement in time complexity.

We first propose the maximum arc problem, normal rational curve conjecture, and extensions of normal rational curves over finite local rings, analogously to the finite geometry over finite fields. We then study the deep hole problem of generalized Reed-Solomon (RS) codes over finite local rings. Several different classes of deep holes are constructed. The relationship between finite geometry and deep holes of RS codes over finite local rings are also studied.  This is a joint work with Zhang Jun.

In this talk, I will present some results on graphs without short cycles. As application, we give a new construction of Tanner graph. This work is joint with Ke Liu and Zequn Lv.

An $(r, \delta)$-locally repairable code ($(r, \delta)$-LRC for short) was introduced by Prakash et al. for tolerating multiple failed nodes in distributed storage systems, which was a generalization of the concept of $r$-LRCs produced by Gopalan et al.. An $(r, \delta)$-LRC is said to be optimal if it achieves the Singleton-like bound. Recently, Chen et al. generalized the construction of cyclic $r$-LRCs proposed by Tamo et al. and constructed several classes of optimal $(r, \delta)$-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 Chen et al., this paper first characterizes $(r, \delta)$-locality of a cyclic code via its zeros. Then we construct several classes of optimal cyclic $(r, \delta)$-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,\delta)$-LRCs proposed in Chen et al., and our method seems more convenient to obtain optimal cyclic $(r, \delta)$-LRCs with flexible parameters. Moreover, many optimal cyclic $(r,\delta)$-LRCs of length $n$ for $n | (q-1)$ or $n | (q+1)$, respectively with $(r+\delta-1)\nmid n$ can be obtained from our method.

Differential uniformity is a significant concept in cryptography as it quantifies the degree of security of S-boxes respect to differential attacks. Power functions of the form $F(x)=x^d$ with low differential uniformity have been extensively studied in the past decades due to their strong resistance to differential attacks and low implementation cost in hardware. In this talk, we give an affirmative answer to a recent conjecture proposed by Budaghyan, Calderini, Carlet, Davidova and Kaleyski about the differential uniformity of $F(x)=x^d$ over $\mathbb{F}_{2^{4n}}$, where $n$ is a positive integer and $d=2^{3n}+2^{2n}+2^{n}-1$, and we completely determine its differential spectrum.

In this talk, we will employ the defining sets of cyclic codes to present two general characterizations of the hulls that have dimension $k-1$ or $k^\perp-1$,where $k^\perp$ is the dimension of the dual code $\mathcal C^\perp$. Several sufficient and necessary conditions for primitive and projective BCH codes to have $(k-1)$-dimensional (or $(k^\perp-1)$-dimensional) hulls are also developed by presenting lower and upper bounds on their designed distances. Furthermore, several classes of self-orthogonal codes are proposed via the hulls of BCH codes and their parameters are also investigated.