Alessandro Budroni

Mr. Alessandro Budroni

orcid

Research Focus & Metrics

Academic Career Length

8Years (2019-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
11 June 2024
Verified
Book Chapter
Closed access
PDF file
BBBenjamin Benčina
Benjamin Benčina
ABAlessandro Budroni
Alessandro Budroni
JCJesús-Javier Chi-Domínguez
Jesús-Javier Chi-Domínguez
MKMukul Kulkarni
Mukul Kulkarni

12 December 2024
Verified
Book Chapter
Closed access
PDF file
ABAlessandro Budroni
Alessandro Budroni
JCJesús-Javier Chi-Domínguez
Jesús-Javier Chi-Domínguez
GDGiuseppe D’aLconzo
Giuseppe D’aLconzo
ASAntonio J. Di Scala
Antonio J. Di Scala
MKMukul Kulkarni
Mukul Kulkarni

8 December 2020
Verified
Book Chapter
Closed access
PDF file
ABAlessandro Budroni
Alessandro Budroni
QGQian Guo
Qian Guo
TJThomas Johansson
Thomas Johansson
EMErik Mårtensson
Erik Mårtensson
PWPaul Stankovski Wagner
Paul Stankovski Wagner

28 October 2021 in Cryptography
Verified
Journal Article
Open access
PDF file
ABAlessandro Budroni
Alessandro Budroni
QGQian Guo
Qian Guo
TJThomas Johansson
Thomas Johansson
EMErik Mårtensson
Erik Mårtensson
PWPaul Stankovski Wagner
Paul Stankovski Wagner
The learning with errors (LWE) problem is one of the main mathematical foundations of post-quantum cryptography. One of the main groups of algorithms for solving LWE is the Blum–Kalai–Wasserman (BKW) algorithm. This paper presents new improvements of BKW-style algorithms for solving LWE instances. We target minimum concrete complexity, and we introduce a new reduction step where we partially reduce the last position in an iteration and finish the reduction in the next iteration, allowing non-integer step sizes. We also introduce a new procedure in the secret recovery by mapping the problem to binary problems and applying the fast Walsh Hadamard transform. The complexity of the resulting algorithm compares favorably with all other previous approaches, including lattice sieving. We additionally show the steps of implementing the approach for large LWE problem instances. We provide two implementations of the algorithm, one RAM-based approach that is optimized for speed, and one file-based approach which overcomes RAM limitations by using file-based storage.

14 July 2020 in Applicable Algebra in Engineering, Communication and Computing
Verified
Journal Article
Open access
PDF file
ABAlessandro Budroni
Alessandro Budroni
FPFederico Pintore
Federico Pintore
When a pairing $$e: {\mathbb {G}}_1 \times {\mathbb {G}}_2 \rightarrow {\mathbb {G}}_{T}$$ e : G 1 × G 2 → G T , on an elliptic curve E defined over a finite field $${\mathbb {F}}_q$$ F q , is exploited for an identity-based protocol, there is often the need to hash binary strings into $${\mathbb {G}}_1$$ G 1 and $${\mathbb {G}}_2$$ G 2 . Traditionally, if E admits a twist $${\tilde{E}}$$ E ~ of order d, then $${\mathbb {G}}_1=E({\mathbb {F}}_q) \cap E[r]$$ G 1 = E ( F q ) ∩ E [ r ] , where r is a prime integer, and $${\mathbb {G}}_2={\tilde{E}}({\mathbb {F}}_{q^{k/d}}) \cap {\tilde{E}}[r]$$ G 2 = E ~ ( F q k / d ) ∩ E ~ [ r ] , where k is the embedding degree of E w.r.t. r. The standard approach for hashing into $${\mathbb {G}}_2$$ G 2 is to map to a general point $$P \in {\tilde{E}}({\mathbb {F}}_{q^{k/d}})$$ P ∈ E ~ ( F q k / d ) and then multiply it by the cofactor $$c=\#{\tilde{E}}({\mathbb {F}}_{q^{k/d}})/r$$ c = # E ~ ( F q k / d ) / r . Usually, the multiplication by c is computationally expensive. In order to speed up such a computation, two different methods—by Scott et al. (International conference on pairing-based cryptography. Springer, Berlin, pp 102–113, 2009) and by Fuentes-Castaneda et al. (International workshop on selected areas in cryptography)—have been proposed. In this paper we consider these two methods for BLS pairing-friendly curves having $$k \in \{12,24,30,42,48\}$$ k ∈ { 12 , 24 , 30 , 42 , 48 } , providing efficiency comparisons. When $$k=42,48$$ k = 42 , 48 , the application of Fuentes et al. method requires expensive computations which were infeasible for the computational power at our disposal. For these cases, we propose hashing maps that we obtained following Fuentes et al. idea.

13 June 2024 in Cryptography and Communications
Verified
Journal Article
Open access
PDF file
ABAlessandro Budroni
Alessandro Budroni
EMErik Mårtensson
Erik Mårtensson
In post-quantum cryptography, Learning With Errors (LWE) is one of the dominant underlying mathematical problems. The dual attack is one of the main strategies for solving the LWE problem, and it has recently gathered significant attention within the research community. The attack strategy consists of a lattice reduction part and a distinguishing part. The latter includes an enumeration subroutine over a certain number of positions of the secret key. Our contribution consists of giving a precise and efficient approach for calculating the expected complexity of such an enumeration procedure, which was missing in the literature. This allows us to decrease the estimated cost of the whole dual attack, both classically and quantumly, on well-known protocols such as Kyber, Saber, and TFHE. In addition, we explore different enumeration strategies to investigate some potential further improvements. As our method of calculating the expected cost of enumeration is pretty general, it might be of independent interest in other areas of cryptanalysis or even in different research areas.