Sven Puchinger

Sven Puchinger

Auto-generated profile, based on publicly available information

Sven Puchinger

Department of Applied Mathematics and Computer Science, Technical University of Denmark (DTU), Lyngby, Denmark

Research Focus & Metrics

Academic Career Length

10Years (2017-Present)

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

Representative Publications

View All Publications
25 January 2022 in IEEE Transactions on Information Theory
Verified
Journal Article
Open access
PBPeter Beelen
Peter Beelen
SPSven Puchinger
Sven Puchinger
JRJohan Rosenkilde
Johan Rosenkilde
In this article, we present a new construction of evaluation codes in the Hamming metric, which we call twisted Reed–Solomon codes. Whereas Reed–Solomon (RS) codes are MDS codes, this need not be the case for twisted RS codes. Nonetheless, we show that our construction yields several families of MDS codes. Further, for a large subclass of (MDS) twisted RS codes, we show that the new codes are not generalized RS codes. To achieve this, we use properties of Schur squares of codes as well as an explicit description of the dual of a large subclass of our codes. We conclude the paper with a description of a decoder, that performs very well in practice as shown by extensive simulation results.

14 April 2022 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
SPSven Puchinger
Sven Puchinger
JRJulian Renner
Julian Renner
JRJohan Rosenkilde
Johan Rosenkilde
We propose the first non-trivial generic decoding algorithm for codes in the sum-rank metric. The new method combines ideas of well-known generic decoders in the Hamming and rank metric. For the same code parameters and number of errors, the new generic decoder has a larger expected complexity than the known generic decoders for the Hamming metric and smaller than the known rank-metric decoders. Furthermore, we give a formal hardness reduction, providing evidence that generic sum-rank decoding is computationally hard. As a by-product of the above, we solve some fundamental coding problems in the sum-rank metric: we give an algorithm to compute the exact size of a sphere of a given sum-rank radius, and also give an upper bound as a closed formula; and we study erasure decoding with respect to two different notions of support.

1 June 2018
Verified
Conference Paper
Open access
PBPeter Beelen
Peter Beelen
MBMartin Bossert
Martin Bossert
SPSven Puchinger
Sven Puchinger
JRJohan Rosenkilde
Johan Rosenkilde
We present a generalisation of Twisted Reed-Solomon codes containing a new large class of MDS codes. We prove that the code class contains a large subfamily that is closed under duality. Furthermore, we study the Schur squares of the new codes and show that their dimension is often large. Using these structural properties, we single out a subfamily of the new codes which could be considered for code-based cryptography: These codes resist some existing structural attacks for Reed-Solomon-like codes, i.e. methods for retrieving the code parameters from an obfuscated generator matrix.

19 March 2021 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
HBHannes Bartz
Hannes Bartz
TJThomas Jerkovits
Thomas Jerkovits
SPSven Puchinger
Sven Puchinger
JRJohan Rosenkilde
Johan Rosenkilde
We speed up existing decoding algorithms for three code classes in different metrics: interleaved Gabidulin codes in the rank metric, lifted interleaved Gabidulin codes in the subspace metric, and linearized Reed-Solomon codes in the sum-rank metric. The speed-ups are achieved by new algorithms that reduce the cores of the underlying computational problems of the decoders to one common tool: computing left and right approximant bases of matrices over skew polynomial rings. To accomplish this, we describe a skew-analogue of the existing PM-Basis algorithm for matrices over ordinary polynomials. This captures the bulk of the work in multiplication of skew polynomials, and the complexity benefit comes from existing algorithms performing this faster than in classical quadratic complexity. The new algorithms for the various decoding-related computational problems are interesting in their own and have further applications, in particular parts of decoders of several other codes and foundational problems related to the remainder-evaluation of skew polynomials.

1 December 2018 in Designs, Codes and Cryptography
Verified
Journal Article
Closed access
PDF file
SPSven Puchinger
Sven Puchinger
JRJohan Rosenkilde
Johan Rosenkilde
IBIrene Bouw
Irene Bouw

18 April 2021 in Designs, Codes and Cryptography
Verified
Journal Article
Open access
PDF file
JRJulian Renner
Julian Renner
SPSven Puchinger
Sven Puchinger
AWAntonia Wachter-Zeh
Antonia Wachter-Zeh
We propose the new rank-metric code-based cryptosystem which is based on the hardness of list decoding and interleaved decoding of Gabidulin codes. is an improved variant of the Faure–Loidreau (FL) system, which was broken in a structural attack by Gaborit, Otmani, and Talé Kalachi (GOT, 2018). We keep the FL encryption and decryption algorithms, but modify the insecure key generation algorithm. Our crucial observation is that the GOT attack is equivalent to decoding an interleaved Gabidulin code. The new key generation algorithm constructs public keys for which all polynomial-time interleaved decoders fail—hence resists the GOT attack. We also prove that the public-key encryption version of is IND-CPA secure in the standard model and the key encapsulation mechanisms version is IND-CCA2 secure in the random oracle model, both under hardness assumptions of formally defined problems related to list decoding and interleaved decoding of Gabidulin codes. We propose and analyze various exponential-time attacks on these problems, calculate their work factors, and compare the resulting parameters to NIST proposals. The strengths of are short ciphertext sizes and (relatively) small key sizes. Further, guarantees correct decryption and has no decryption failure rate. It is not based on hiding the structure of a code. Since there are efficient and constant-time algorithms for encoding and decoding Gabidulin codes, timing attacks on the encryption and decryption algorithms can be easily prevented.