Designs, Codes and Cryptography

Correction to: Improved Singleton bound on frequency hopping sequences and optimal constructions The original version of this article unfortunately contained a mistake in an equation.

Polynomial time bounded distance decoding near Minkowski's bound in discrete logarithm lattices Abstract We propose a concrete family of dense lattices of arbitrary dimension n in which the lattice bounded distance decoding (BDD) problem can be solved in deterministic polynomial time. This construction is directly adapted from the Chor–Rivest cryptosystem (IEEE-TIT 1988). The lattice construction needs discrete logarithm computations that can be made in deterministic polynomial time for well-chosen parameters. Each lattice comes with a deterministic polynomial time decoding algorithm able to decode up to large radius. Namely, we reach decoding radius within \(O(\log n)\) Minkowski's bound, for both \(\ell _1\) and \(\ell _2\) norms.

Nearly optimal robust secret sharing Abstract We prove that a known general approach to improve Shamir's celebrated secret sharing scheme; i.e., adding an information-theoretic authentication tag to the secret, can make it robust for n parties against any collusion of size \(\delta n\) , for any constant \(\delta \in (0, 1/2)\) . Shamir's original scheme is robust for all \(\delta \in (0,1/3)\) . Beyond that, we employ the best known list decoding algorithms for Reed-Solomon codes and show that, with high probability, only the correct secret maintains the correct information-theoretic tag if an algebraic manipulation detection (AMD) code is used to tag secrets. This result holds in the so-called "non-rushing" model in which the n shares are submitted simultaneously for reconstruction. We thus obtain a fully explicit and robust secret sharing scheme in this model that is essentially optimal in all parameters including the share size which is \(k(1+o(1)) + O(\kappa )\) , where k is the secret length and \(\kappa \) is the security parameter. Like Shamir's scheme, in this modified scheme any set of more than \(\delta n\) honest parties can efficiently recover the secret. Using algebraic geometry codes instead of Reed-Solomon codes, the share length can be decreased to a constant (only depending on \(\delta \) ) while the number of shares n can grow independently. In this case, when n is large enough, the scheme satisfies the "threshold" requirement in an approximate sense; i.e., any set of \(\delta n(1+\rho )\) honest parties, for arbitrarily small \(\rho > 0\) , can efficiently reconstruct the secret. From a practical perspective, the main importance of our result is in showing that existing systems employing Shamir-type secret sharing schemes can be made much more robust than previously thought with minimal change, essentially only involving the addition of a short and simple checksum to the original data.

Codes with the rank metric and matroids Abstract We study the relationship between linear codes with the rank metric in the vector space of matrices with entries in a finite field and a q-analogue of matroids. We prove a Greene type identity for the rank generating function of these matroidal structures and the rank weight enumerator of these linear codes. As an application, we give a combinatorial proof of the MacWilliams type identity for Delsarte rank-metric codes.

Cameron–Liebler sets of k -spaces in $${{\mathrm{PG}}}(n,q)$$ PG ( n , q ) Abstract Cameron–Liebler sets of k-spaces were introduced recently in Filmus and Ihringer (J Combin Theory Ser A, 2019). We list several equivalent definitions for these Cameron–Liebler sets, by making a generalization of known results about Cameron–Liebler line sets in \({{\mathrm{PG}}}(n,q)\) and Cameron–Liebler sets of k-spaces in \({{\mathrm{PG}}}(2k+1,q)\) . We also present some classification results.

An algorithmic framework for the generalized birthday problem Abstract The generalized birthday problem (GBP) was introduced by Wagner in 2002 and has shown to have many applications in cryptanalysis. In its typical variant, we are given access to a function \(H:\{0,1\}^{\ell } \rightarrow \{0,1\}^n\) (whose specification depends on the underlying problem) and an integer \(K>0\) . The goal is to find K distinct inputs to H (denoted by \(\{x_i\}_{i=1}^{K}\) ) such that \(\sum _{i=1}^{K}H(x_i) = 0\) . Wagner's K-tree algorithm solves the problem in time and memory complexities of about \(N^{1/(\lfloor \log K \rfloor + 1)}\) (where \(N= 2^n\) ). In this paper, we improve the best known GBP time-memory tradeoff curve (published independently by Nikolić and Sasaki and also by Biryukov and Khovratovich) for all \(K \ge 8\) from \(T^2M^{\lfloor \log K \rfloor -1} = N\) to \(T^{\lceil (\log K)/2 \rceil + 1 }M^{\lfloor (\log K)/2 \rfloor } = N\) , applicable for a large range of parameters. We further consider values of K which are not powers of 2 and show that in many cases even more efficient time-memory tradeoff curves can be obtained. Finally, we optimize our techniques for several concrete GBP instances and show how to solve some of them with improved time and memory complexities compared to the state-of-the-art. Our results are obtained using a framework that combines several algorithmic techniques such as variants of the Schroeppel–Shamir algorithm for solving knapsack problems (devised in works by Howgrave-Graham and Joux and by Becker, Coron and Joux) and dissection algorithms (published by Dinur, Dunkelman, Keller and Shamir).

Uniqueness of codes using semidefinite programming Abstract For  \(n,d,w \in \mathbb {N}\) , let A(n, d, w) denote the maximum size of a binary code of word length n, minimum distance d and constant weight w. Schrijver recently showed using semidefinite programming that \(A(23,8,11)=1288\) , and the second author that  \(A(22,8,11)=672\) and  \(A(22,8,10)=616\) . Here we show uniqueness of the codes achieving these bounds. Let A(n, d) denote the maximum size of a binary code of word length n and minimum distance d. Gijswijt et al. showed that  \(A(20,8)=256\) . We show that there are several nonisomorphic codes achieving this bound, and classify all such codes with all distances divisible by 4.

A trigonometric sum sharp estimate and new bounds on the nonlinearity of some cryptographic Boolean functions Abstract In this paper, we give a sharp estimate of a trigonometric sum which has several applications in cryptography and sequence theory. Using this estimate, we deduce new lower bounds on the nonlinearity of Carlet–Feng function, which has very good cryptographic properties with its nonlinearity bound being improved in numerous papers, as well as the function proposed by Tang–Carlet–Tang.

Weightwise perfectly balanced functions with high weightwise nonlinearity profile Abstract Boolean functions satisfying good cryptographic criteria when restricted to the set of vectors with constant Hamming weight play an important role in the recent FLIP stream cipher (Méaux et al.: in Lecture Notes in Computer Science, vol. 9665, pp. 311–343, Springer, Berlin, 2016). In this paper, we propose a large class of weightwise perfectly balanced (WPB) functions, which is 2-rotation symmetric. This new class of WPB functions is not extended affinely equivalent to the known constructions. We also discuss the weightwise nonlinearity profile of these functions, and present general lower bounds on k-weightwise nonlinearity, where k is a power of 2. Moreover, we exhibit a subclass of the family. By a recursive lower bound, we show that these subclass of WPB functions have very high weightwise nonlinearity profile.

Optimal binary constant weight codes and affine linear groups over finite fields Abstract The affine linear group of degree one, \(\text {AGL}(1,\mathbb {F}_q)\) , over the finite field \(\mathbb {F}_q\) , acts sharply two-transitively on \(\mathbb {F}_q\) . Given \(S<\text {AGL}(1,\mathbb {F}_q)\) and an integer k, \(1\le k\le q\) , does there exist a k-element subset \(B\subset \mathbb {F}_q\) whose set-wise stabilizer is S? Our main result is the derivation of two formulas which provide an answer to this question. This result allows us to determine all possible parameters of binary constant weight codes that are constructed from the action of \(\text {AGL}(1,\mathbb {F}_q)\) on \(\mathbb {F}_q\) to meet the Johnson bound. Consequently, for many parameters, we are able to determine the values of the function \(A_2(n,d,w)\) , which is the maximum number of codewords in a binary constant weight code of length n, weight w and minimum distance \(\ge d\) .

Alexandros Sfakianakis
Anapafseos 5 . Agios Nikolaos
Crete.Greece.72100
2841026182

6948891480

alsfakia@gmail.com