Search

We survey the known group structures arising from elliptic curves defined by Weierstrass models over commutative rings with unity and satisfying a technical condition. For every considered base ring, the groups that may arise depending on the curve coefficients are recalled. When a complete classification is still out of reach, partial results about the group structure and relevant subgroups are provided. Several examples of elliptic curves over the inspected rings are presented, and open questions regarding the structure of their points are highlighted. [ABSTRACT FROM AUTHOR]

Given a local ring (R , m) and an elliptic curve E (R / m) , we define its elliptic loop as the points of P 2 (R) projecting to E under the canonical modulo- m reduction, endowed with an operation that extends the curve's addition. While its subset of points satisfying the curve's Weierstrass equation is a group, this larger object is proved to be a power-associative abelian algebraic loop, which is seldom completely associative. When an elliptic loop has no points of order 3, its affine part is obtained as a stratification of a one-parameter family of elliptic curves defined over R , which we call layers. Stronger associativity properties are established when m e vanishes for small values of e ∈ Z. When the underlying ring is R = Z / p e Z , the infinity part of an elliptic loop is generated by two elements, the group structure of layers may be established and the points with the same projection and same order possess a geometric description. [ABSTRACT FROM AUTHOR]

The notion of public-key encryption with keyword search (PEKS) was introduced to search over encrypted data without performing any decryption. In this article, we propose a PEKS scheme in which both the encrypted keyword and the trapdoor are randomized so that the cloud server is not able to recognize identical queries a priori. Our scheme is Ciphertext-Indistinguishabiltity secure in the single-user setting and Trapdoor-Indistinguishability secure in the multi-user setting with a stronger security, i.e., with multi-trapdoor. [ABSTRACT FROM AUTHOR]

The weight, balancedness and nonlinearity are important properties of Boolean functions, but they can be difficult to determine in general. In this paper, we study how to compute them for two classes of functions where these problems are more tractable. In particular, we study functions of degree three and the so-called “splitting” functions. The latter are functions that can be written as the sum of two functions defined over disjoint sets of variables. We show how, for splitting functions, studying these properties reduces to the study of simpler functions. We provide then a procedure to compute the weight of a cubic Boolean function. We show computationally that, for a cubic Boolean function with limited number of terms, this procedure is on average significantly more efficient than some other methods. [ABSTRACT FROM AUTHOR]

We review and compare three algebraic methods to compute the nonlinearity of Boolean functions. Two of them are based on Gröbner basis techniques: the first one is defined over the binary field, while the second one over the rationals. The third method improves the second one by avoiding the Gröbner basis computation. We also estimate the complexity of the algorithms, and, in particular, we show that the third method reaches an asymptotic worst-case complexity of O (n 2 n) operations over the integers, that is, sums and doublings. This way, with a different approach, the same asymptotic complexity of established algorithms, such as those based on the fast Walsh transform, is reached. [ABSTRACT FROM AUTHOR]

Propaganda played a very important role during Fascism; the kind of propaganda used by Mussolini to build a totalitarian state was to a very large extent based on his own personality cult, on the myth of the leader. Despite the disastrous outcome of the Mussolini regime, the propaganda has outlived Mussolini himself. Cultivating the image therefore becomes an essential part of the mechanism of generating consensus, anticipating by more than half a century the politics of spectacle used today throughout the world. [ABSTRACT FROM AUTHOR]

Abstract: Recently some methods have been proposed to find the distance and weight distribution of cyclic codes using Gröbner bases. We identify a class of codes for which these methods can be generalized. We show that this class contains all interesting linear codes and we provide variants and improvements. This approach sometimes reveals an unexpected algebraic structure in the code. We also investigate the decoding for a subclass, proving the existence of general error locator polynomials. [Copyright &y& Elsevier]

Using Gröbner techniques, we can exhibit a method to get the distance and weight distribution of cyclic codes and shortened cyclic codes, improving earlier similar results for the distance of cyclic codes. [ABSTRACT FROM AUTHOR]

In this paper, we show that a recently proposed algorithm for decoding cyclic codes may be applied efficiently to all binary cyclic codes with t ⩽ 2 and n < 63. This is accomplished by providing structure theorems for the codes in this range and classifying the relevant cases. [ABSTRACT FROM AUTHOR]

A new lower bound for the distance of cyclic codes is proposed. This bound depends on the defining set of the code, like several other bounds. The proposed bound improves upon the Bose-Chaudhuri-Hocquehghen (BCH) bound and, for some codes, improves upon the Hartmann-Tzeng bound and the Roos bound as well. [ABSTRACT FROM AUTHOR]

Abstract: We propose a new syndrome variety, which can be used to decode cyclic codes. We present also a generalization to erasure and error decoding. We can exhibit a polynomial whose roots give the error locations, once it has been specialized to a given syndrome. This polynomial has degree in the variable corresponding to the error locations and its coefficients are polynomials in the syndromes. [Copyright &y& Elsevier]

The Gro¨bner bases of the ideal generated by the symmetric functions are presented. Moreover we show how they can be fruitfully applied to a problem arising from coding theory. [Copyright &y& Elsevier]

In this paper we analyze the intersection between the norm-trace curve over F q 3 and the curves of the form y = a x 3 + b x 2 + c x + d , giving a complete characterization of the intersection between the curve and the parabolas (a=0), as well as sharp bounds for the other cases. This information is used for the determination of the weight distribution of some one-point AG codes arising from the curve. [ABSTRACT FROM AUTHOR]

We show how a small subgroup confinement-like attack may be mounted on the Bitcoin addresses generation protocol, by inspecting a special subgroup of the group associated to point multiplication. This approach does not undermine the system security but highlights the importance of using fair random sources during the private key selection. [ABSTRACT FROM AUTHOR]

Blockchain technology has attracted a lot of research interest in the last few years. Originally, their consensus algorithm was Hashcash, which is an instance of the so-called Proof-of-Work. Nowadays, there are several competing consensus algorithms, not necessarily PoW. In this paper, we propose an alternative proof of work algorithm which is based on the solution of consecutive discrete logarithm problems over the point group of elliptic curves. At the same time, we sketch a blockchain scheme, whose consensus is reached via our algorithm. In the considered architecture, the curves are pseudorandomly determined by block creators, chosen to be cryptographically secure and changed every epoch. Given the current state of the chain and a prescribed set of transactions, the curve selection is fully rigid, therefore trust is needed neither in miners nor in the scheme proposers. [ABSTRACT FROM AUTHOR]

We are interested in calculating the weight distribution of Hermitian codes over the finite field with q 2 elements. In this work we show that, if we can compute the partial weight distribution for about q 2 weights, then we will easily compute the whole weight distribution (which has about q 3 values). To achieve this, we actually show that the computation of a given element of the weight distribution is equivalent to a less laborious task, which is the classification of some submatrices of the parity-check matrix according to their rank. [ABSTRACT FROM AUTHOR]

Presents information on a study which proposed a linear programming approaches to estimate the weight distribution of a binary linear code. Methodology of the study; Results and discussion on the study.

The affine general linear group acting on a vector space over a prime field is a well-understood mathematical object. Its elementary abelian regular subgroups have recently drawn attention in applied mathematics thanks to their use in cryptography as a way to hide or detect weaknesses inside block ciphers. This paper is focused on building a convenient representation of their elements which suits better the purposes of the cryptanalyst. Several combinatorial counting formulas and a classification of their conjugacy classes are given as well. [ABSTRACT FROM AUTHOR]

In 1990 Cooper suggested to use Groebner bases' computations to decode cyclic codes and his idea gave rise to many research papers. In particular, as proved by Sala-Orsini, once defined the polynomial ring whose variables are the syndromes, the locations and the error values and considered the syndrome ideal, only one polynomial of a lexicographical Groebner basis for such ideal is necessary to decode (the general error locator polynomial, a.k.a. GELP). The decoding procedure only consists in evaluating this polynomial in the syndromes and computing its roots: the roots are indeed the error locations. A possible bottleneck in this procedure may be the evaluation part, since a priori the GELP may be dense. In this paper, focusing on binary cyclic codes with length n = 2 m - 1 , correcting up to two errors, we give a Groebner-free, sparse analog of the GELP, the half error locator polynomial (HELP). In particular, we show that it is not necessary to compute the whole Groebner basis for getting such kind of locator polynomial and we construct the HELP, studying the quotient algebra of the polynomial ring modulo the syndrome ideal by a combinatorial point of view. The HELP turns out to be computable with quadratic complexity and it has linear growth in the length n of the code: O n + 1 2 . [ABSTRACT FROM AUTHOR]

Abstract Sometimes it is possible to embed an algebraic trapdoor into a block cipher. Building on previous research, in this paper we investigate an especially dangerous algebraic structure, which is called a hidden sum and which is related to some regular subgroups of the affine group. Mixing group theory arguments and cryptographic tools, we pass from characterizing our hidden sums to designing an efficient algorithm to perform the necessary preprocessing for the exploitation of the trapdoor. [ABSTRACT FROM AUTHOR]

In recent years several papers have appeared that investigate the classical discrete logarithm problem for elliptic curves by means of the multivariate polynomial approach based on the celebrated summation polynomials, introduced by Semaev in 2004. With a notable exception by Petit et al. in 2016, all numerous papers on the subject have investigated only the composite-field case, leaving apart the laborious prime-field case. In this paper we propose a variation of Semaev's original approach that reduces to only one the relations to be found among points of the factor base, thus decreasing drastically the necessary Groebner basis computations. Our proposal holds for any finite field but it is particularly suitable for the prime-field case, where it outperforms both the original Semaev's method and the specialised algorithm by Petit et al.. [ABSTRACT FROM AUTHOR]

A block cipher can be easily broken if its encryption functions can be seen as linear maps on a small vector space. Even more so, if its round functions can be seen as linear maps on a small vector space. We show that this cannot happen for the AES. More precisely, we prove that if the AES round transformations can be embedded into a linear cipher acting on a vector space, then this space is huge-dimensional and so this embedding is infeasible in practice. We present two elementary proofs. [ABSTRACT FROM AUTHOR]

In this paper we propose a tokenization algorithm of Reversible Hybrid type, as defined in PCI DSS guidelines for designing a tokenization solution, based on a block cipher with a secret key and (possibly public) additional input. We provide some formal proofs of security for it, which imply our algorithm satisfies the most significant security requirements described in PCI DSS tokenization guidelines. Finally, we give an instantiation with concrete cryptographic primitives and fixed length of the PAN, and we analyze its efficiency and security. [ABSTRACT FROM AUTHOR]

General error locator polynomials were introduced in 2005 as an alternative decoding for cyclic codes. We now present a conjecture on their sparsity, which would imply polynomial-time decoding for all cyclic codes. A general result on the explicit form of the general error locator polynomial for all cyclic codes is given, along with several results for specific code families, providing evidence to our conjecture. From these, a theoretical justification of the sparsity of general error locator polynomials is obtained for all binary cyclic codes with $t\leq 2$ and $n<105$ , as well as for $t=3$ and $n<63$ , except for some cases where the conjectured sparsity is proved by a computer check. Moreover, we summarize all related results, previously published, and we show how they provide further evidence to our conjecture. Finally, we discuss the link between our conjecture and the complexity of bounded-distance decoding of the cyclic codes. [ABSTRACT FROM AUTHOR]

Most bounds on the size of codes hold for any code, whether linear or not. Notably, the Griesmer bound holds only in the linear case and so optimal linear codes are not necessarily optimal codes. In this paper, we identify code parameters $(q,d,k)$ , namely, field size, minimum distance, and combinatorial dimension, for which the Griesmer bound also holds in the (systematic) nonlinear case. Moreover, we show that the Griesmer bound does not necessarily hold for a systematic code by explicit construction of a family of optimal systematic binary codes. On the other hand, we are able to provide some versions of the Griesmer bound holding for all the systematic codes. [ABSTRACT FROM AUTHOR]

For any affine-variety code we show how to construct an ideal whose solutions correspond to codewords with any assigned weight. We are able to obtain geometric characterizations for small-weight codewords for some families of Hermitian codes over any F q 2 . From these geometric characterizations, we obtain explicit formulas. In particular, we determine the number of minimum-weight codewords for all Hermitian codes with d ≤ q and all second-weight codewords for distance- 3 , 4 codes. [ABSTRACT FROM AUTHOR]

Abstract: We classify completely the intersections of the Hermitian curve with parabolas in the affine plane. To obtain our results we employ well-known algebraic methods for finite fields and geometric properties of the curve automorphisms. In particular, we provide explicit counting formulas that have also applications to some Hermitian codes. [Copyright &y& Elsevier]

We present some upper bounds on the size of nonlinear codes and their restriction to systematic codes and linear codes. These bounds are independent of other known theoretical bounds, e.g., the Griesmer bound, the Johnson bound, the Plotkin bound, and of linear programming bounds. One of the new bound is actually an improvement of a bound by Zinoviev, Litsyn, and Laihonen. Our experiments show that in the linear case our bounds provide the best value in a wide range, compared with all other closed-formula upper bounds. In the nonlinear case, we also compare our bound with the linear programming bound and with some improvements on it, show that there are cases where we beat these bounds. In particular, we obtain a new bound in Brouwer's table for A3(16,3). [ABSTRACT FROM AUTHOR]

The determination of the weight distribution of linear codes has been a fascinating problem since the very beginning of coding theory. There has been a lot of research on weight enumerators of special cases, such as self-dual codes and codes with small Singleton's defect. We propose a new set of linear relations that must be satisfied by the coefficients of the weight distribution. From these relations we are able to derive known identities (in an easier way) for interesting cases, such as extremal codes, Hermitian codes, MDS and NMDS codes. Moreover, we are able to present for the first time the weight distribution of AMDS codes. We also discuss the link between our results and the Pless equations. [ABSTRACT FROM AUTHOR]

Abstract: General error locator polynomials are polynomials able to decode any correctable syndrome for a given linear code. Such polynomials are known to exist for all cyclic codes and for a large class of linear codes. We provide some decoding techniques for affine-variety codes using some multidimensional extensions of general error locator polynomials. We prove the existence of such polynomials for any correctable affine-variety code and hence for any linear code. We propose two main different approaches, that depend on the underlying geometry. We compute some interesting cases, including Hermitian codes. To prove our coding theory results, we develop a theory for special classes of zero-dimensional ideals, that can be considered generalizations of stratified ideals. Our improvement with respect to stratified ideals is twofold: we generalize from one variable to many variables and we introduce points with multiplicities. [Copyright &y& Elsevier]

The most important families of nonlinear codes are systematic. A brute-force check is the only known method to compute their weight distribution and distance distribution. On the other hand, it outputs also all closest word pairs in the code. In the black-box complexity model, the check is optimal among closest-pair algorithms. In this paper, we provide a Gröbner basis technique to compute the weight/distance distribution of any systematic nonlinear code. Also our technique outputs all closest pairs. Unlike the check, our method can be extended to work on code families. [ABSTRACT FROM AUTHOR]

A quantum random number generator (QRNG) based on a silicon nanocrystals (Si-NCs) light emitting device (LED) coupled with a silicon single photon avalanche photodiode (Si-SPAD) is presented. A simple setup is used for the generation of random bits. The modeled approach assures a negligible bias on datasets of [ABSTRACT FROM AUTHOR]

We study the relation among some security parameters for vectorial Boolean functions which prevent attacks on the related block cipher. We focus our study on a recently-introduced security criterion, called weak differential uniformity, which prevents the existence of an undetectable trapdoor based on imprimitive group action. We present some properties of functions with low weak differential uniformity, especially for the case of power functions and 4-bit S-Boxes. [ABSTRACT FROM AUTHOR]

The correctness in decrypting a ciphertext after some operations in the DGVH scheme depends heavily on the dimension of the secret key. In this paper we compute two bounds on the size of the secret key for the DGHV scheme to decrypt correctly a ciphertext after a fixed number of additions and a fixed number of multiplication. Moreover we improve the original bound on the dimension of the secret key for a general circuit. [ABSTRACT FROM AUTHOR]

Abstract: S-Boxes are important security components of block ciphers. We provide theoretical results on necessary or sufficient criteria for an (invertible) 4-bit S-Box to be weakly APN. Thanks to a classification of 4-bit invertible S-Boxes achieved independently by De Cannière and Leander–Poschmann, we can strengthen our results with a computer-aided proof. We also propose a class of 4-bit S-Boxes which are very strong from a security point of view. [Copyright &y& Elsevier]

BEAR, LION and LIONESS are block ciphers presented by Biham and Anderson (), inspired by the famous Luby-Rackoff constructions of block ciphers from other cryptographic primitives (). The ciphers proposed by Biham and Anderson are based on one stream cipher and one hash function. Good properties of the primitives may ensure good properties of the block cipher. In particular, Biham and Anderson are able to prove that their ciphers are immune to any efficient known-plaintext key-recovery attack that can use as input only one plaintext-ciphertext pair. Our contribution is showing that these ciphers are actually immune to any efficient known-plaintext key-recovery attack that can use as input any number of plaintext-ciphertext pairs. We are able to get this improvement by using slightly different hypotheses on the primitives. We also discuss the attack by Morin (). [ABSTRACT FROM AUTHOR]

Abstract: Irradiation of N-triphenylmethyloxy- or N-diphenylmethyloxy phthalimide is reported to result in the formation of phthalimide N-oxyl radical (PINO), which is able to initiate and propagate oxidative radical chain reactions of hydrocarbons. [Copyright &y& Elsevier]