Erik Mårtensson

Erik Mårtensson

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
19 March 2019 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
QGQian Guo
Qian Guo
TJThomas Johansson
Thomas Johansson
EMErik Mårtensson
Erik Mårtensson
PWPaul Stankovski Wagner
Paul Stankovski Wagner
The Learning with Errors problem (LWE) has become a central topic in recent cryptographic research. In this paper, we present a new solving algorithm combining important ideas from previous work on improving the Blum- Kalai-Wasserman (BKW) algorithm and ideas from sieving in lattices. The new algorithm is analyzed and demonstrates an improved asymptotic performance. For the Regev parameters q = n2 and noise level σ = n1:5/(√2π log2 2 n), the asymptotic complexity is 20:893n in the standard setting, improving on the previously best known complexity of roughly 20:930n. The newly proposed algorithm also provides asymptotic improvements when a quantum computer is assumed or when the number of samples is limited.

31 August 2023 in IACR Transactions on Cryptographic Hardware and Embedded Systems
Verified
Journal Article
Open access
PDF file
JHJulius Hermelink
Julius Hermelink
EMErik Mårtensson
Erik Mårtensson
Simona SamardjiskaSimona Samardjiska
Simona Samardjiska
PPPeter Pessl
Peter Pessl
GRGabi Dreo Rodosek
Gabi Dreo Rodosek
In LWE-based KEMs, observed decryption errors leak information about the secret key in the form of equations or inequalities. Several practical fault attacks have already exploited such leakage by either directly applying a fault or enabling a chosen-ciphertext attack using a fault. When the leaked information is in the form of inequalities, the recovery of the secret key is not trivial. Recent methods use either statistical or algebraic methods (but not both), with some being able to handle incorrect information. Having in mind that integration of the side-channel information is a crucial part of several classes of implementation attacks on LWEbased schemes, it is an important question whether statistically processed information can be successfully integrated in lattice reduction algorithms.We answer this question positively by proposing an error-tolerant combination of statistical and algebraic methods that make use of the advantages of both approaches. The combination enables us to improve upon existing methods – we use both fewer inequalities and are more resistant to errors. We further provide precise security estimates based on the number of available inequalities.Our recovery method applies to several types of implementation attacks in which decryption errors are used in a chosen-ciphertext attack. We practically demonstrate the improved performance of our approach in a key-recovery attack against Kyber with fault-induced decryption errors.

9 August 2022 in Cryptography and Communications
Verified
Journal Article
Open access
PDF file
QGQian Guo
Qian Guo
EMErik Mårtensson
Erik Mårtensson
PWPaul Stankovski Wagner
Paul Stankovski Wagner
The Learning with Errors (LWE) problem receives much attention in cryptography, mainly due to its fundamental significance in post-quantum cryptography. Among its solving algorithms, the Blum-Kalai-Wasserman (BKW) algorithm, originally proposed for solving the Learning Parity with Noise (LPN) problem, performs well, especially for certain parameter settings with cryptographic importance. The BKW algorithm consists of two phases, the reduction phase and the solving phase. In this work, we study the performance of distinguishers used in the solving phase. We show that the Fast Fourier Transform (FFT) distinguisher from Eurocrypt’15 has the same sample complexity as the optimal distinguisher, when making the same number of hypotheses. We also show via simulation that it performs much better than previous theory predicts and develop a sample complexity model that matches the simulations better. We also introduce an improved, pruned version of the FFT distinguisher. Finally, we indicate, via extensive experiments, that the sample dependency due to both LF2 and sample amplification is limited.

1 January 2019 in Advances in Mathematics of Communications
Verified
Journal Article
Open access
PDF file
QGQian Guo
Qian Guo
TJThomas Johansson
Thomas Johansson
EMErik Mårtensson
Erik Mårtensson
PWPaul Stankovski Wagner
Paul Stankovski Wagner
Using the class of information set decoding algorithms is the best known way of decoding general codes, i.e. codes that admit no special structure, in the Hamming metric. The Stern algorithm is the origin of the most efficient algorithms in this class. We consider the same decoding problem but for a channel with soft information. We give a version of the Stern algorithm for a channel with soft information that includes some novel steps of ordering vectors in lists, based on reliability values. We demonstrate how the algorithm constitutes an improvement in some cryptographic and coding theoretic applications. We also indicate how to extend the algorithm to include multiple iterations and soft output values.

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.

28 April 2025
Verified
Book Chapter
Closed access
PDF file
JHJulius Hermelink
Julius Hermelink
SSSilvan Streit
Silvan Streit
EMErik Mårtensson
Erik Mårtensson
RPRichard Petri
Richard Petri