cryptography teams

Abstract: We prove quantum soundness of the total-degree diagonal line-vs-point test using the individual-degree soundness theorem of Ji, Natarajan, Vidick, Wright, and Yuen. A random change of coordinates yields projective polynomial decoders of total degree at most $md$. The uniform-line slice of the test bounds the weight of outcomes of degree greater than $d$, which are removed by a common relabeling. This reduction does not yield a dimension-independent soundness bound: the $\operatorname{poly}(m)$ dependence of the individual-degree theorem persists, as discussed in Section 1.2 of arXiv:2009.12982.

Abstract: Let $\mathcal C=(f)$ be a $λ$-constacyclic code over $\mathbb F_q$, where $f(X)$ is a monic factor of $X^N-λ$ with nonzero constant term. We introduce the support period $\operatorname{sp}(f)$ of $f(X)$, and define its support-primitive core $f_{\mathrm{sp}}(X)$ as the unique support-primitive polynomial satisfying $f(X)=f_{\mathrm{sp}}(X^s)$, where $s=\operatorname{sp}(f)$. We show that this polynomial relation induces a Hamming-weight-preserving linear isomorphism $\mathcal C\cong\mathcal C_{\mathrm{sp}}^{\, s}$, where $\mathcal C_{\mathrm{sp}}$ is the support-primitive core of $\mathcal C$, and prove that this decomposition is intrinsic to the code. We give two equivalent descriptions of the support period: a coefficient-based one and a roots-based one. In the repeated-root case, the latter is determined by the $p$-adic structure and the stabilizer of the defining function, while in the simple-root case it is determined by the coarsest multiple equal-difference representation of the defining set. We then derive coding-theoretic consequences for the Hamming distance, weight enumerator, covering radius, and Euclidean duality. In particular, the arithmetic Singleton bound of a simple-root constacyclic code is identified with the classical Singleton bound of its support-primitive core. Finally, we apply the decomposition to cyclic codes with reducible generator polynomials and obtain bounds for their arithmetic Singleton values.

Abstract: Delsarte (1973) conjectured that there are no nontrivial perfect codes in the Johnson scheme. In this paper, we prove that there are no nontrivial $e$-perfect codes in the Johnson scheme for $e\in\{1,2,4,9,10,12,16\}$. This paper complements "Perfect Codes in the Johnson Scheme Hardly Exist", thus proving Delsarte's conjecture completely.