查看更多>>摘要：Let n be an odd positive integer, p be an odd prime with p ≡ 3 (mod 4), d_1 = p~n-1/2-1 and d_2 = p~n - 2. The function defined by f_u(x) = ux~(d_1) + x~(d_2) is called the generalized Ness-Helleseth function over F_(p~n), where u ∈ F_(p~n). It was initially studied by Ness and Helleseth in the ternary case. In this paper, for p~n ≡ 3 (mod 4) and p~n ≥ 7, we provide the necessary and sufficient condition for f_u(x) to be an APN function. In addition, for each u satisfying χ(u + 1) = χ(u - 1), the differential spectrum of f_u(x) is investigated, and it is expressed in terms of some quadratic character sums of cubic polynomials, where χ(·) denotes the quadratic character of F_(p~n).
查看更多>>摘要：A generator matrix of a linear code C over GF(q) is also a matrix of the same rank k over any extension field GF(q~ℓ) and generates a linear code of the same length, same dimension and same minimum distance over GF(q~ℓ), denoted by C(q|q~ℓ) and called a lifted code of C. Although C and their lifted codes C(q|q~ℓ) have the same parameters, they have different weight distributions and different applications. Few results about lifted linear codes are known in the literature. This paper proves some fundamental theory for lifted linear codes, and studies the 2-designs of the lifted projective Reed-Muller codes, lifted Hamming codes and lifted Simplex codes. In addition, this paper settles the weight distributions of the lifted Reed-Muller codes of certain orders, and investigates the 3-designs supported by these lifted codes. As a by-product, an infinite family of three-weight projective codes over GF(4) is obtained.
查看更多>>摘要：Let q be a prime power. This paper provides a new class of linear codes that arises from the action of the alternating group on F_q [x_1,…, x_m] combined with the ideas in Datta and Johnsen (Des Codes Cryptogr 91(3):747-761, 2023). Compared with Generalized Reed-Muller codes with analogous parameters, our codes have the same asymptotic relative distance but a better rate. Our results follow from combinations of Galois theoretical methods with Weil-type bounds for hypersurfaces.
查看更多>>摘要：Sieving using near-neighbor search techniques is a well-known method in lattice-based cryptanalysis, yielding the current best runtime for the shortest vector problem in both the classical and quantum setting. Recently, sieving has also become an important tool in code-based cryptanalysis. Specifically, a variant of the information-set decoding (ISD) framework, commonly used for attacking cryptographically relevant instances of the decoding problem, has been introduced that involves a sieving subroutine. The resulting sieving-based ISD framework yields complexities close to the best-performing classical algorithms for the decoding problem. It is therefore natural to ask how well quantum versions perform. In this work, we introduce the first quantum algorithms for code sieving by designing quantum variants of the aforementioned sieving subroutine. In particular, using quantum-walk techniques, we provide a speed-up over classical code sieving and over a variant using Grover's algorithm. Our quantum-walk algorithm exploits the structure of the underlying search problem by adding a layer of locality sensitive filtering, inspired by a quantum-walk algorithm for lattice sieving. We complement our asymptotic analysis of the quantum algorithms with numerical results, and observe that our quantum speed-ups for code sieving behave similarly as those observed in lattice sieving. In addition, we show that a natural quantum analog of the sieving-based ISD framework does not provide any speed-up over the first quantum ISD algorithm. Our analysis highlights that the framework should be adapted in order to outperform state-of-the-art quantum ISD algorithms.
Carlos Aguilar-MelchorVictor DyserynPhilippe Gaborit
1645-1669页
查看更多>>摘要：We present a secret-key encryption scheme based on random rank metric ideal linear codes with a simple decryption circuit. It supports unlimited homomorphic additions and plaintext multiplications (i.e. the homomorphic multiplication of a clear plaintext with a ciphertext) as well as a fixed arbitrary number of homomorphic multiplications. We study a candidate bootstrapping algorithm that requires no multiplication but additions and plaintext multiplications only. This latter operation is therefore very efficient in our scheme, whereas bootstrapping is usually the main reason which penalizes the performance of other fully homomorphic encryption schemes. However, the security reduction of our scheme restricts the number of independent ciphertexts that can be published. In particular, this prevents to securely evaluate the bootstrapping algorithm as the number of ciphertexts in the key switching material is too large. Our scheme is nonetheless the first somewhat homomorphic encryption scheme based on random ideal codes and a first step towards full homomorphism. Random ideal codes give stronger security guarantees as opposed to existing constructions based on highly structured codes. We give concrete parameters for our scheme that shows that it achieves competitive sizes and performance, with a key size of 3.7 kB and a ciphertext size of 0.9 kB when a single multiplication is allowed.
查看更多>>摘要：Ternary isodual codes and their duals are shown to support 3-designs under mild symmetry conditions. These designs are held invariant by a double cover of the permutation part of the automorphism group of the code. Examples of interest include extended quadratic residues (QR) codes of lengths 14 and 38 whose automorphism groups are PSL(2, 13) and PSL(2, 37), respectively. We also consider Generalized Quadratic Residue (GQR) codes in the sense of Lint and MacWiliams (IEEE Trans Inf Theory 24(6): 730-737,1978). These codes are the abelian generalizations of the Quadratic Residue (QR) codes which are cyclic. We construct them as row span of a Jacobsthal matrix. In lengths 50 and 26 we obtain 3-designs invariant under a double cover of PΣL(2,49), and PΣL(2, 25), respectively. In addition, from block orbits of these 3-designs we construct a number of other 3-designs and 2-designs. Finally, we apply the same construction to the binary extended GQR code of length 82.
查看更多>>摘要：We provide a new construction of quantum codes that enables integration of a broader class of classical codes into the mathematical framework of quantum stabilizer codes. Next, we present new connections between twisted codes and linear cyclic codes and provide novel bounds for the minimum distance of twisted codes. We show that classical tools such as the Hartmann-Tzeng minimum distance bound are applicable to twisted codes. This enabled us to discover five new infinite families and many other examples of record-breaking, and sometimes optimal, binary quantum codes. We also discuss the role of the y value on the parameters of twisted codes and present new results regarding the construction of twisted codes with different y values but identical parameters. Finally, we list many new record-breaking binary quantum codes that we obtained from additive twisted, linear cyclic, and constacyclic codes.
查看更多>>摘要：Permutation and multi-permutation codes have been widely studied due to their potential applications in communications and storage systems, especially in flash memory. In this paper, we consider balanced multi-permutation codes correcting a single burst of stable deletions of length t and length at most t, respectively. Based on the properties of burst stable deletions and stabilizer permutation subgroups, we propose two constructions of multi-permutation codes correcting a single burst of stable deletions of length up to some parameter. The multi-permutation codes can achieve larger rates than available codes while maintaining simple interleaving structures. Moreover, the decoding methods are given in proofs and verified by examples.
查看更多>>摘要：For a set L of lines of PG(n, q), a set X of points of PG(n, q) is called an L-blocking set if each line of L contains at least one point of X. Consider a possibly singular quadric Q of PG(n, q) and denote by S (respectively, T) the set of all lines of PG(n, q) meeting Q in 2 (respectively, 1 or q + 1) points. For L ∈ {S, T ∪ S}, we find the minimal cardinality of an L-blocking set of PG(n, q) and determine all L-blocking sets of that minimal cardinality.
查看更多>>摘要：Let n = 2~k - 1 and m = 2~(k-2) for a certain k ≥ 3. Consider the point-line geometry of 2m-element subsets of an n-element set. Maximal singular subspaces of this geometry correspond to binary simplex codes of dimension k. For k ≥ 4 the associated collinearity graph contains maximal cliques different from maximal singular subspaces. We investigate maximal cliques corresponding to symmetric (n, 2m, m)-designs. The main results concern the case k = 4 and give a geometric interpretation of the five well-known symmetric (15, 8,4)-designs.
NETL
NSTL