Refine
Document Type
- Conference Proceeding (10)
- Article (8)
- Doctoral Thesis (1)
Language
- English (19) (remove)
Keywords
- Channel capacity (1)
- Channel coding (1)
- Channel estimation (1)
- Code-based cryptography (2)
- Code-based cryptosystem (1)
- Computational complexity (1)
- Computer Science Applications (1)
- Concatenated codes (2)
- Data retention time (1)
- Decoding (1)
- Decoding attack (1)
- Electrical and Electronic Engineering (1)
- Elliptic curve cryptography (2)
- Elliptic curve point multiplication (1)
- Error correction codes (1)
- Error correction coding (1)
- Gaussian integers (2)
- Gaussian processes (1)
- Generalized concatenated codes (2)
- Hardware and Architecture (1)
- Human-Computer Interaction (1)
- Information-set decoding (1)
- McEliece cryptosystem (4)
- Montgomery modular multiplication (1)
- Montgomery modular reduction (1)
- Niederreiter cryptosystem (1)
- Non-volatile memory (1)
- Nonvolatile NAND flash (1)
- Point multiplication (1)
- Polar codes (1)
- Post-quantum public-key cryptography (1)
- Processor (1)
- Program/erase cycles (1)
- Public key cryptography (1)
- Public-key cryptography (3)
- Reed-Muller (RM) codes (1)
- Resource-constrained systems (1)
- Restricted error values (1)
- Solinas primes (1)
- Threshold calibration (1)
- concatenated codes (1)
- maximum distance separable codes (1)
Institute
Large-scale quantum computers threaten the security of today's public-key cryptography. The McEliece cryptosystem is one of the most promising candidates for post-quantum cryptography. However, the McEliece system has the drawback of large key sizes for the public key. Similar to other public-key cryptosystems, the McEliece system has a comparably high computational complexity. Embedded devices often lack the required computational resources to compute those systems with sufficiently low latency. Hence, those systems require hardware acceleration. Lately, a generalized concatenated code construction was proposed together with a restrictive channel model, which allows for much smaller public keys for comparable security levels. In this work, we propose a hardware decoder suitable for a McEliece system based on these generalized concatenated codes. The results show that those systems are suitable for resource-constrained embedded devices.
Public-key cryptographic algorithms are an essential part of todays cyber security, since those are required for key exchange protocols, digital signatures, and authentication. But large scale quantum computers threaten the security of the most widely used public-key cryptosystems. Hence, the National Institute of Standards and Technology ( NIST ) is currently in a standardization process for post-quantum secure public-key cryptography. One type of such systems is based on the NP-complete problem of decoding random linear codes and therefore called code-based cryptography. The best-known code-based cryptographic system is the McEliece system proposed in 1978 by Robert McEliece. It uses a scrambled generator matrix as a public key and the original generator matrix as well as the scrambling as private key. When encrypting a message it is encoded in the public code and a random but correctable error vector is added. Only the legitimate receiver can correct the errors and decrypt the message using the knowledge of the private key generator matrix. The original proposal of the McEliece system was based on binary Goppa codes, which are also considered for standardization. While those codes seem to be a secure choice, the public keys are extremely large, limiting the practicality of those systems. Many different code families were proposed for the McEliece system, but many of them are considered insecure since attacks exist, which use the known code structure to recover the private key. The security of code-based cryptosystems mainly depends on the number of errors added by the sender, which is limited by the error correction capability of the code. Hence, in order to obtain a high security for relatively short codes one needs a high error correction capability. Therefore maximum distance separable ( MDS ) codes were proposed for those systems, since those are optimal for the Hamming distance. In order to increase the error correction capability we propose q -ary codes over different metrics. There are many code families that have a higher minimum distance in some other metric than in the Hamming metric, leading to increased error correction capability over this metric. To make use of this one needs to restrict not only the number of errors but also their value. In this work, we propose the weight-one error channel, which restricts the error values to weight one and can be applied for different metrics. In addition we propose some concatenated code constructions, which make use of this restriction of error values. For each of these constructions we discuss the usability in code-based cryptography and compare them to other state-of-the-art code-based cryptosystems. The proposed code constructions show that restricting the error values allows for significantly lower public key sizes for code-based cryptographic systems. Furthermore, the use of concatenated code constructions allows for low complexity decoding and therefore an efficient cryptosystem.
Code-based cryptosystems are promising candidates for post-quantum cryptography. Recently, generalized concatenated codes over Gaussian and Eisenstein integers were proposed for those systems. For a channel model with errors of restricted weight, those q-ary codes lead to high error correction capabilities. Hence, these codes achieve high work factors for information set decoding attacks. In this work, we adapt this concept to codes for the weight-one error channel, i.e., a binary channel model where at most one bit-error occurs in each block of m bits. We also propose a low complexity decoding algorithm for the proposed codes. Compared to codes over Gaussian and Eisenstein integers, these codes achieve higher minimum Hamming distances for the dual codes of the inner component codes. This property increases the work factor for a structural attack on concatenated codes leading to higher overall security. For comparable security, the key size for the proposed code construction is significantly smaller than for the classic McEliece scheme based on Goppa codes.
The growing error rates of triple-level cell (TLC) and quadruple-level cell (QLC) NAND flash memories have led to the application of error correction coding with soft-input decoding techniques in flash-based storage systems. Typically, flash memory is organized in pages where the individual bits per cell are assigned to different pages and different codewords of the error-correcting code. This page-wise encoding minimizes the read latency with hard-input decoding. To increase the decoding capability, soft-input decoding is used eventually due to the aging of the cells. This soft-decoding requires multiple read operations. Hence, the soft-read operations reduce the achievable throughput, and increase the read latency and power consumption. In this work, we investigate a different encoding and decoding approach that improves the error correction performance without increasing the number of reference voltages. We consider TLC and QLC flashes where all bits are jointly encoded using a Gray labeling. This cell-wise encoding improves the achievable channel capacity compared with independent page-wise encoding. Errors with cell-wise read operations typically result in a single erroneous bit per cell. We present a coding approach based on generalized concatenated codes that utilizes this property.
Reed-Muller (RM) codes have recently regained some interest in the context of low latency communications and due to their relation to polar codes. RM codes can be constructed based on the Plotkin construction. In this work, we consider concatenated codes based on the Plotkin construction, where extended Bose-Chaudhuri-Hocquenghem (BCH) codes are used as component codes. This leads to improved code parameters compared to RM codes. Moreover, this construction is more flexible concerning the attainable code rates. Additionally, new soft-input decoding algorithms are proposed that exploit the recursive structure of the concatenation and the cyclic structure of the component codes. First, we consider the decoding of the cyclic component codes and propose a low complexity hybrid ordered statistics decoding algorithm. Next, this algorithm is applied to list decoding of the Plotkin construction. The proposed list decoding approach achieves near-maximum-likelihood performance for codes with medium lengths. The performance is comparable to state-of-the-art decoders, whereas the complexity is reduced.
Code-based cryptography is a promising candidate for post-quantum public-key encryption. The classic McEliece system uses binary Goppa codes, which are known for their good error correction capability. However, the key generation and decoding procedures of the classic McEliece system have a high computation complexity. Recently, q-ary concatenated codes over Gaussian integers were proposed for the McEliece cryptosystem together with the one-Mannheim error channel, where the error values are limited to Mannheim weight one. For this channel, concatenated codes over Gaussian integers achieve a higher error correction capability than maximum distance separable (MDS) codes with bounded minimum distance decoding. This improves the work factor regarding decoding attacks based on information-set decoding. This work proposes an improved construction for codes over Gaussian integers. These generalized concatenated codes extent the rate region where the work factor is beneficial compared to MDS codes. They allow for shorter public keys for the same level of security as the classic Goppa codes. Such codes are beneficial for lightweight code-based cryptosystems.
Large-scale quantum computers threaten today's public-key cryptosystems. The code-based McEliece and Niederreiter cryptosystems are among the most promising candidates for post-quantum cryptography. Recently, a new class of q-ary product codes over Gaussian integers together with an efficient decoding algorithm were proposed for the McEliece cryptosystems. It was shown that these codes achieve a higher work factor for information-set decoding attacks than maximum distance separable (MDS) codes with comparable length and dimension. In this work, we adapt this q-ary product code construction to codes over Eisenstein integers. We propose a new syndrome decoding method which is applicable for Niederreiter cryptosystems. The code parameters and work factors for information-set decoding are comparable to codes over Gaussian integers. Hence, the new construction is not favorable for the McEliece system. Nevertheless, it is beneficial for the Niederreiter system, where it achieves larger message lengths. While the Niederreiter and McEliece systems have the same level of security, the Niederreiter system can be advantageous for some applications, e.g., it enables digital signatures. The proposed coding scheme is interesting for lightweight Niederreiter cryptosystems and embedded security due to the short code lengths and low decoding complexity.
The code-based McEliece cryptosystem is a promising candidate for post-quantum cryptography. The sender encodes a message, using a public scrambled generator matrix, and adds a random error vector. In this work, we consider q-ary codes and restrict the Lee weight of the added error symbols. This leads to an increased error correction capability and a larger work factor for information-set decoding attacks. In particular, we consider codes over an extension field and use the one-Lee error channel, which restricts the error values to Lee weight one. For this channel model, generalized concatenated codes can achieve high error correction capabilities. We discuss the decoding of those codes and the possible gain for decoding beyond the guaranteed error correction capability.
Generalized Concatenated Codes over Gaussian and Eisenstein Integers for Code-Based Cryptography
(2021)
The code-based McEliece and Niederreiter cryptosystems are promising candidates for post-quantum public-key encryption. Recently, q-ary concatenated codes over Gaussian integers were proposed for the McEliece cryptosystem together with the one-Mannheim error channel, where the error values are limited to Mannheim weight one. Due to the limited error values, the codes over Gaussian integers achieve a higher error correction capability than maximum distance separable (MDS) codes with bounded minimum distance decoding. This higher error correction capability improves the work factor regarding decoding attacks based on information-set decoding. The codes also enable a low complexity decoding algorithm for decoding beyond the guaranteed error correction capability. In this work, we extend this coding scheme to codes over Eisenstein integers. These codes have advantages for the Niederreiter system. Additionally, we propose an improved code construction based on generalized concatenated codes. These codes extent the rate region where the work factor is beneficial compared to MDS codes. Moreover, generalized concatenated codes are more robust against structural attacks than ordinary concatenated codes.
The McEliece cryptosystem is a promising candidate for post-quantum public-key encryption. In this work, we propose q-ary codes over Gaussian integers for the McEliece system and a new channel model. With this one Mannheim error channel, errors are limited to weight one. We investigate the channel capacity of this channel and discuss its relation to the McEliece system. The proposed codes are based on a simple product code construction and have a low complexity decoding algorithm. For the one Mannheim error channel, these codes achieve a higher error correction capability than maximum distance separable codes with bounded minimum distance decoding. This improves the work factor regarding decoding attacks based on information-set decoding.