Source author record

Roberto La Scala

Roberto La Scala appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

math.RA math.AC Cryptography and Security math.AP Symbolic Computation

Catalog footprint

What is connected

7works

5topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2022arXiv

An algebraic attack to the Bluetooth stream cipher E0

In this paper we study the security of the Bluetooth stream cipher E0 from the viewpoint it is a "difference stream cipher", that is, it is defined by a system of explicit difference equations over the finite field GF(2). This approach highlights some issues of the Bluetooth encryption such as the invertibility of its state transition map, a special set of 14 bits of its 132-bit state which when guessed implies linear equations among the other bits and finally a small number of spurious keys, with 83 guessed bits, which are compatible with a keystream of about 60 bits. Exploiting these issues, we implement an algebraic attack using Gröbner bases, SAT solvers and Binary Decision Diagrams. Testing activities suggest that the version based on Gröbner bases is the best one and it is able to attack E0 in about 2^79 seconds on an Intel i9 CPU. To the best of our knowledge, this work improves any previous attack based on a short keystream, hence fitting with Bluetooth specifications.

preprint2021arXiv

Stream/block ciphers, difference equations and algebraic attacks

In this paper we model a class of stream and block ciphers as systems of (ordinary) explicit difference equations over a finite field. We call this class "difference ciphers" and we show that ciphers of application interest, as for example systems of LFSRs with a combiner, Trivium and Keeloq, belong to the class. By using Difference Algebra, that is, the formal theory of difference equations, we can properly define and study important properties of these ciphers, such as their invertibility and periodicity. We describe then general cryptanalytic methods for difference ciphers that follow from these properties and are useful to assess the security. We illustrate such algebraic attacks in practice by means of the ciphers Bivium and Keeloq.

preprint2016arXiv

Monomial right ideals and the Hilbert series of noncommutative modules

In this paper we present a procedure for computing the rational sum of the Hilbert series of a finitely generated monomial right module $N$ over the free associative algebra $K\langle x_1,\ldots,x_n \rangle$. We show that such procedure terminates, that is, the rational sum exists, when all the cyclic submodules decomposing $N$ are annihilated by monomial right ideals whose monomials define regular formal languages. The method is based on the iterative application of the colon right ideal operation to monomial ideals which are given by an eventual infinite basis. By using automata theory, we prove that the number of these iterations is a minimal one. In fact, we have experimented efficient computations with an implementation of the procedure in Maple which is the first general one for noncommutative Hilbert series.

preprint2014arXiv

Extended letterplace correspondence for nongraded noncommutative ideals and related algorithms

Let $K\ < x_i\ >$ be the free associative algebra generated by a finite or countable number of variables $x_i$. The notion of "letterplace correspondence" introduced in [1,2] for the graded (two-sided) ideals of $K\ < x_i\ >$ is extended in this paper also to the nongraded case. This amounts to the possibility of modelizing nongraded noncommutative presented algebras by means of a class of graded commutative algebras that are invariant under the action of the monoid $\mathbb N$ of natural numbers. For such purpose we develop the notion of saturation for the graded ideals of $K\ < x_i,t\ >$, where $t$ is an extra variable and for their letterplace analogues in the commutative polynomial algebra $K[x_{ij},t_j]$, where $j$ ranges in $\mathbb N$. In particular, one obtains an alternative algorithm for computing inhomogeneous noncommutative Gröbner bases using just homogeneous commutative polynomials. The feasibility of the proposed methods is shown by an experimental implementation developed in the computer algebra system Maple and by using standard routines for the Buchberger algorithm contained in Singular. References [1] La Scala, R.; Levandovskyy, V., Letterplace ideals and non-commutative Gröbner bases. J. Symbolic Comput., 44 (2009), 1374--1393. [2] La Scala, R.; Levandovskyy, V., Skew polynomial rings, Gröbner bases and the letterplace embedding of the free associative algebra. J. Symbolic Comput., 48 (2013), 110--131

preprint2014arXiv

Noetherian quotients of the algebra of partial difference polynomials and Grobner bases of symmetric ideals

In this paper we develop a Grobner bases theory for ideals of partial difference polynomials with constant or non-constant coefficients. In particular, we introduce a criterion providing the finiteness of such bases when a difference ideal contains elements with suitable linear leading monomials. This can be explained in terms of Noetherianity of the corresponding quotient algebra. Among these Noetherian quotients we find finitely generated polynomial algebras where the action of suitable finite dimensional commutative algebras and in particular finite abelian groups is defined. We obtain therefore a consistent Grobner bases theory for ideals that possess such symmetries.

preprint2013arXiv

Groebner bases and gradings for partial difference ideals

In this paper we introduce a working generalization of the theory of Gröbner bases for algebras of partial difference polynomials with constant coefficients. One obtains symbolic (formal) computation for systems of linear or non-linear partial difference equations arising, for instance, as discrete models or by the discretization of systems of differential equations. From an algebraic viewpoint, the algebras of partial difference polynomials are free objects in the category of commutative algebras endowed with the action by endomorphisms of a monoid isomorphic to $\N^r$. Then, the investigation of Gröbner bases in this context contributes also to the current research trend consisting in studying polynomial rings under the action of suitable symmetries that are compatible with effective methods. Since the algebras of difference polynomials are not Noetherian ones, we propose in this paper a theory for grading them that provides a Noetherian subalgebras filtration. This implies that the variants of the Buchberger's algorithm we developed for difference ideals terminate in the finitely generated graded case when truncated up to some degree. Moreover, even in the non-graded case, we provide criterions for certifying completeness of eventually finite Gröbner bases when they are computed within sufficiently large bounded degrees. We generalize also the concepts of homogenization and saturation, and related algorithms, to the context of difference ideals. The feasibily of the proposed methods is shown by an implementation in Maple that is the first to provide computations for systems of non-linear partial difference equations. We make use of a test set based on the discretization of concrete systems of non-linear partial differential equations.

preprint2012arXiv

Skew polynomial rings, Groebner bases and the letterplace embedding of the free associative algebra

In this paper we introduce an algebra embedding $ι:K< X >\to S$ from the free associative algebra $K< X >$ generated by a finite or countable set $X$ into the skew monoid ring $S = P * Σ$ defined by the commutative polynomial ring $P = K[X\times N^*]$ and by the monoid $Σ= < σ>$ generated by a suitable endomorphism $σ:P\to P$. If $P = K[X]$ is any ring of polynomials in a countable set of commuting variables, we present also a general Gröbner bases theory for graded two-sided ideals of the graded algebra $S = \bigoplus_i S_i$ with $S_i = P σ^i$ and $σ:P \to P$ an abstract endomorphism satisfying compatibility conditions with ordering and divisibility of the monomials of $P$. Moreover, using a suitable grading for the algebra $P$ compatible with the action of $Σ$, we obtain a bijective correspondence, preserving Gröbner bases, between graded $Σ$-invariant ideals of $P$ and a class of graded two-sided ideals of $S$. By means of the embedding $ι$ this results in the unification, in the graded case, of the Gröbner bases theories for commutative and non-commutative polynomial rings. Finally, since the ring of ordinary difference polynomials $P = K[X\times N]$ fits the proposed theory one obtains that, with respect to a suitable grading, the Gröbner bases of finitely generated graded ordinary difference ideals can be computed also in the operators ring $S$ and in a finite number of steps up to some fixed degree.