Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Cyclic codes are an important subclass of linear codes. In this paper, we investigate the construction of quinary cyclic codes with parameters \([5^{m}-1, 5^{m}-2m-2, 4]\) and eight new classes optimal quinary cyclic codes of form \({\mathcal {C}}_{(1,e,s)}\) are presented by discussing the solutions of certain equations over \({\mathbb {F}}_{5^{m}}\) . PubDate: 2025-03-01 DOI: 10.1007/s00200-023-00604-8
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract A linear code C of length \(n = ru + sv\) is a two-dimensional \({\mathbb {F}}\) -double cyclic code if the set of coordinates can be partitioned into two arrays, such that any cyclic row-shifts and column-shifts of both arrays of a codeword is also a codeword. In this paper, we examine the algebraic structure of these codes and their dual codes in general. Moreover, we are interested in finding out a generating set for these codes (and their dual codes) in case when \(u=2\) , \(v=4\) and char \((F) \ne 2\) . PubDate: 2025-03-01 DOI: 10.1007/s00200-023-00595-6
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Algebraic Cryptanalysis is a widely used technique that tackles the problem of breaking ciphers mainly relying on the ability to express a cryptosystem as a solvable polynomial system. Each output bit/word can be expressed as a polynomial equation in the cipher’s inputs—namely the key and the plaintext or the initialisation vector bits/words. A part of research in this area consists in finding suitable algebraic structures where polynomial systems can be effectively solved, e.g., by computing Gröbner bases. In 2009, Dinur and Shamir proposed the cube attack, a chosen plaintext algebraic cryptanalysis technique for the offline acquisition of an equivalent system by means of monomial reduction; interpolation on cubes in the space of variables enables retrieving a linear polynomial system, hence making it exploitable in the online phase to recover the secret key. Since its introduction, this attack has received both many criticisms and endorsements from the crypto community; this work aims at providing, under a unified notation, a complete state-of-the-art review of recent developments by categorising contributions in five classes. We conclude the work with an in-depth description of the kite attack framework, a cipher-independent tool that implements cube attacks on GPUs. Mickey2.0 is adopted as a showcase. PubDate: 2025-03-01 DOI: 10.1007/s00200-023-00602-w
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Let \(p\equiv 1\pmod 4\) be a prime. In this paper, we support a new method, i.e., a product of 2-adic values for four binary sequences, to determine the maximum evaluations of the 2-adic complexity in all almost balanced cyclotomic binary sequences of order four with period \(N=p\) , which are viewed as generalizing the results in Hu (IEEE Trans. Inf. Theory 60:5803–5804, 2014) and Xiong et al. (IEEE Trans. Inf. Theory 60:2399–2406, 2014) without the autocorrelation values of cyclotomic binary sequences of order four with period p. By number theory we obtain two necessary and sufficient conditions about the 2-adic complexity of all balanced cyclotomic binary sequences of order four with period \(N=2p\) and show the 2-adic complexity of several non-balanced cyclotomic binary sequences of order four with period 2p, which are viewed as generalizing the results in Zhang et al. (IEEE Trans. Inf. Theory 66:4613–4620, 2020). PubDate: 2025-03-01 DOI: 10.1007/s00200-023-00598-3
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract The task of recognizing an algebraic surface from a single apparent contour can be reduced to the recovering of a homogeneous equation in four variables from its discriminant. In this paper, we use the fact that Darboux cyclides have a singularity along the absolute conic in order to recognize them up to Euclidean similarity transformations. PubDate: 2025-03-01 DOI: 10.1007/s00200-023-00600-y
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract The choice of the elliptic curve for a given pairing based protocol is primordial. For many cryptosystems based on pairings such as group signatures and their variants (EPID, anonymous attestation, etc) or accumulators, operations in the first pairing group \(\mathbb {G}\) of points of the elliptic curve is more predominant. At 128-bit security level two curves BW13-P310 and BW19-P286 with odd embedding degrees 13 and 19 suitable for super optimal pairing have been recommended for such pairing based protocols. But a prime embedding degree ( \(k=13;19\) ) eliminates some important optimisation for the pairing computation. However The Miller loop length of the superoptimal pairing is the half of that of the optimal ate pairing but involve more exponentiations that affect its efficiency. In this work, we successfully develop methods and construct algorithms to efficiently evaluate and avoid heavy exponentiations that affect the efficiency of the superoptimal pairing. This leads to the definition of new bilinear and non degenerate pairing on BW13-P310 and BW19-P286 called x-superoptimal pairing where its Miller loop is about \(15.3 \%\) and \(39.8 \%\) faster than the one of the optimal ate pairing previously computed on BW13-P310 and BW19-P286 respectively. PubDate: 2025-03-01 DOI: 10.1007/s00200-023-00596-5
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract A combinatorial problem concerning the maximum size of the (Hamming) weight set of an \([n,k]_q\) linear code was recently introduced. Codes attaining the established upper bound are the Maximum Weight Spectrum (MWS) codes. Those \([n,k]_q\) codes with the same weight set as \(\mathbb {F}_q^n\) are called Full Weight Spectrum (FWS) codes. FWS codes are necessarily “short”, whereas MWS codes are necessarily “long”. For fixed k, q the values of n for which an \([n,k]_q\) -FWS code exists are completely determined, but the determination of the minimum length M(H, k, q) of an \([n,k]_q\) -MWS code remains an open problem. The current work broadens discussion first to general coordinate-wise weight functions, and then specifically to the Lee weight and a Manhattan like weight. In the general case we provide bounds on n for which an FWS code exists, and bounds on n for which an MWS code exists. When specializing to the Lee or to the Manhattan setting we are able to completely determine the parameters of FWS codes. As with the Hamming case, we are able to provide an upper bound on \(M({\mathscr {L}},k,q)\) (the minimum length of Lee MWS codes), and pose the determination of \(M({\mathscr {L}},k,q)\) as an open problem. On the other hand, with respect to the Manhattan weight we completely determine the parameters of MWS codes. PubDate: 2025-03-01 DOI: 10.1007/s00200-023-00608-4
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Sequences of consecutive Legendre and Jacobi symbols as pseudorandom bit generators were proposed for cryptographic use in 1988. Major interest has been shown towards pseudorandom functions (PRF) recently, based on the Legendre and power residue symbols, due to their efficiency in the multi-party setting. The security of these PRFs is not known to be reducible to standard cryptographic assumptions. In this work, we show that key-recovery attacks against the Legendre PRF are equivalent to solving a specific family of multivariate quadratic (MQ) equation system over a finite prime field. This new perspective sheds some light on the complexity of key-recovery attacks against the Legendre PRF. We conduct algebraic cryptanalysis on the resulting MQ instance. We show that the currently known techniques and attacks fall short in solving these sparse quadratic equation systems. Furthermore, we build novel cryptographic applications of the Legendre PRF, e.g., verifiable random function and (verifiable) oblivious (programmable) PRFs. PubDate: 2025-03-01 DOI: 10.1007/s00200-023-00599-2
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract The strongly annihilating-ideal graph \(\textrm{SAG}(R)\) of a commutative unital ring R is a simple graph whose vertices are non-zero ideals of R with non-zero annihilator and there exists an edge between two distinct vertices if and only if each of them has a non-zero intersection with annihilator of the other one. In this paper, we compute twin-free clique number of \(\textrm{SAG}(R)\) and as an application strong metric dimension of \(\textrm{SAG}(R)\) is given. Moreover, we investigate the structures of strong resolving sets in \(\textrm{SAG}(R)\) to find forcing strong metric dimension in \(\textrm{SAG}(R)\) . PubDate: 2025-03-01 DOI: 10.1007/s00200-023-00601-x
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Illustrated by a problem on paint pots that is easy to understand but hard to solve, we investigate whether particular monoids have the property of common right multiples. As one result we characterize generalized braid monoids represented by undirected graphs, being a subclass of Artin–Tits monoids. Stated in other words, we investigate to which graphs the old Garside result stating that braid monoids have the property of common right multiples, generalizes. This characterization also follows from old results on Coxeter groups and the connection between finiteness of Coxeter groups and common right multiples in Artin–Tits monoids. However, our independent presentation is self-contained up to some basic knowledge of rewriting, and also applies to monoids beyond the Artin–Tits format. The main new contribution is a technique to prove that the property of common right multiples does not hold, by finding a particular model, in our examples all being finite. PubDate: 2025-03-01 DOI: 10.1007/s00200-023-00606-6
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract In this paper, we compute sequence covering arrays (SCAs), which are arrays, consisting of sequences, such that all subsequences with pairwise different entries of some length are covered, via a novel approach based on commutative algebra and symbolic computation. Hereby, we provide various algebraic models being capable to characterize possibly small sets of permutations collectively containing particular shorter subsequences. These models take the form of multivariate polynomial systems of equations and are then processed via supercomputing by a Gröbner Basis solver in order to compute solutions from them. If the variety is not empty, i.e. the Gröbner basis is non-trivial, then each point in the computed variety can be transformed to a SCA. In our experiments, we observed varying computational performance depending on the chosen model, while all of them exhibited scalability issues. Additionally and for comparison, we give new SAT descriptions modelling SCAs. By employing a SAT solver on our provided SAT models, we are able to provide upper bounds, one of which is best among literature results. Lastly, we adapt our SAT approach to answer a question posed by Yuster (Des Codes Cryptogr 88(3):585–593, 2020). As a result, we find a characterization of the dimensions of all perfect SCAs with coverage multiplicity two of strength three. PubDate: 2025-03-01 DOI: 10.1007/s00200-023-00597-4
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract There are four commutative unital rings of order four. Among them, we consider the ring \(R=\mathbb {F}_{2}+u\mathbb {F}_{2}= \left\{ 0,1,u,\bar{u}=u+1\right\} \) where \(u^2=0\) , which is a commutative ring with characteristic 2. In this paper, we study linear complementary dual (LCD) codes over the ring R. We first define \({\text{ LCD }}[n,k]_{R}\) , which denotes the maximum of possible values of d among free [n, k, d] LCD codes over R, and obtain a Griesmer type bound for linear codes over R. We get an upper bound for \({\text{ LCD }}[n,2]_{R}\) , and further show that \({\text{ LCD }}[n,2]_{R}\) with the exception of \(n\equiv 0, -1 \; (\textrm{mod} \; \) 6) meets the upper bound exactly. For \(k=3\) , we also get an upper bound for \({\text{ LCD }}[n,3]_{R}\) . Then we show that \({\text{ LCD }}[n,3]_{R}\) meets the upper bound exactly for \(n\equiv 3, 5\) (mod 7). We also derive bounds of \({\text{ LCD }}[n,k]_{R}\) for \(k=4, 5\) from the binary cases. Furthermore, we obtain the exact value of \({\text{ LCD }}[n,n-i]_{R}\) for i greater than or equal to two using the sphere packing bound. PubDate: 2025-01-28 DOI: 10.1007/s00200-025-00677-7
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Given an algebraic germ of a plane curve at the origin, in terms of a bivariate polynomial, we analyze the complexity of computing an irreducible decomposition up to any given truncation order. With a suitable representation of the irreducible components, and whenever the characteristic of the ground field is zero or larger than the degree of the germ, we design a new algorithm that involves a nearly linear number of arithmetic operations in the ground field plus a small amount of irreducible univariate polynomial factorizations. PubDate: 2025-01-01 DOI: 10.1007/s00200-024-00669-z
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract The LG cryptosystem is a public-key encryption scheme in the rank metric using the recent family of \(\mathbf{\mathrm {\lambda }}-\) Gabidulin codes and introduced in 2019 by Lau and Tan. In this paper, we present a cryptanalysis showing that the security of several parameters of the scheme have been overestimated. We also show the existence of some weak keys allowing an attacker to find in polynomial time an alternative private key. PubDate: 2024-12-14 DOI: 10.1007/s00200-024-00671-5
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Type II \({\mathbb {Z}}_4\) -codes are a class of self-dual \({\mathbb {Z}}_4\) -codes with Euclidean weights divisible by eight. A Type II \({\mathbb {Z}}_4\) -code of length n is extremal if its minimum Euclidean weight is equal to \(8\left\lfloor \frac{n}{24}\right\rfloor +8.\) A small number of such codes is known for lengths greater than or equal to 48. Based on the doubling method, in this paper we develop a method to construct new extremal Type II \({\mathbb {Z}}_4\) -codes starting from a free extremal Type II \({\mathbb {Z}}_4\) -code of length 48, 56 or 64. Using this method, we construct extremal Type II \({\mathbb {Z}}_4\) -codes of length 64 and type \(4^{31}2^2\) . Extremal Type II \({\mathbb {Z}}_4\) -codes of length 64 of this type were not known before. Moreover, the residue codes of the constructed extremal \({\mathbb {Z}}_4\) -codes are best known [64, 31] binary codes and the supports of the minimum weight codewords of the residue code and the torsion code of one of these codes yields self-orthogonal 1-design. PubDate: 2024-12-11 DOI: 10.1007/s00200-024-00674-2
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract In this paper, two classes of permutation pentanomials over finite fields \(\mathbb {F}_{p^{2m}}\) are investigated by transforming the permutation property of polynomials to verifying that some low-degree equations has no solutions in the unit circle. Furthermore, based on the study of the algebraic curves for fractional polynomials, several classes of permutation pentanomials and hexanomials over \(\mathbb {F}_{5^{2m}}\) are discovered. Additionally, we obtain some new permutation pentanomials, quadrinomials and octonomials over \(\mathbb {F}_{5^{2m}}\) from known permutation polynomials in the unit circle. PubDate: 2024-11-25 DOI: 10.1007/s00200-024-00673-3
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract In this paper, we define the complex-type k-Padovan numbers and then give the relationships between the \(\left( 1,k-1\right)\) -bonacci numbers, the k -Padovan numbers and the complex-type k-Padovan numbers by matrix method. In addition, we study the complex-type k-Padovan sequence modulo m and then we show that for some m the periods of the complex type k-Padovan and k-Padovan sequences modulo m are related. Furthermore, we extend the complex-type k-Padovan sequences to groups. Finally, we obtain the periods of the complex-type 4, 5, 6-Padovan sequences in the semidihedral group \(SD_{2^{m}}\) , \(\left( m\ge 4\right)\) with respect to the generating pairs \(\left( x,y\right)\) and \(\left( y,x\right)\) . PubDate: 2024-11-05 DOI: 10.1007/s00200-024-00672-4