The concatenation of encryption and decryption can be interpreted as data transmission over a noisy communication channel. In this work, we use finite blocklength methods (normal approximation and random coding union bound) as well as asymptotics to show that ciphertext and key sizes of the state-of-the-art post-quantum secure key encapsulation mechanism (KEM) Kyber can be reduced without compromising the security of the scheme. We show that in the asymptotic regime, it is possible to reduce the sizes of ciphertexts and secret keys by 25% for the parameter set Kyber1024 while keeping the bitrate at 1 as proposed in the original scheme. For a single Kyber encryption block used to share a 256-bit AES key, we furthermore show that reductions in ciphertext size of 39% and 33% are possible for Kyber1024 and Kyber512, respectively.

Several cryptosystems based on the Ring Learning with Errors (RLWE) problem have been proposed within the NIST post-quantum cryptography standardization process, e.g., NewHope. Furthermore, there are systems like Kyber which are based on the closely related MLWE assumption. Both previously mentioned schemes result in a non-zero decryption failure rate (DFR). The combination of encryption and decryption for these kinds of algorithms can be interpreted as data transmission over a noisy channel. To the best of our knowledge this paper is the first work that analyzes the capacity of this channel. We show how to modify the encryption schemes such that the input alphabets of the corresponding channels are increased. In particular, we present lower bounds on their capacities which show that the transmission rate can be significantly increased compared to standard proposals in the literature. Furthermore, under the common assumption of stochastically independent coefficient failures, we give lower bounds on achievable rates based on both the Gilbert-Varshamov bound and concrete code constructions using BCH codes. By means of our constructions, we can either increase the total bitrate (by a factor of 1.84 for Kyber and by factor of 7 for NewHope) while guaranteeing the same DFR or for the same bitrate, we can significantly reduce the DFR for all schemes considered in this work (e.g., for NewHope from 2−216 to 2−12769).

In this work, we consider q-ary signature codes of length k and size n for a noisy adder multiple access channel. A signature code in this model has the property that any subset of codewords can be uniquely reconstructed based on any vector that is obtained from the sum (over integers) of these codewords. We show that there exists an algorithm to construct a signature code of length $k = \frac{{2n\log 3}}{{(1 - 2\tau )\left( {\log n + (q - 1)\log \frac{\pi }{2}} \right)}} + \mathcal{O}\left( {\frac{n}{{\log n(q + \log n)}}} \right)$ capable of correcting τk errors at the channel output, where $0 \leq \tau < \frac{{q - 1}}{{2q}}$. Furthermore, we present an explicit construction of signature codewords with polynomial complexity being able to correct up to $\left( {\frac{{q - 1}}{{8q}} - \varepsilon } \right)k$ errors for a codeword length $k = \mathcal{O}\left( {\frac{n}{{\log \log n}}} \right)$, where ε is a small non-negative number. Moreover, we prove several non-existence results (converse bounds) for q-ary signature codes enabling error correction.

In this paper, we consider encoding strategies for the Z-channel with noiseless feedback. We analyze the combinatorial setting where the maximum number of errors inflicted by an adversary is proportional to the number of transmissions, which goes to infinity. Without feedback, it is known that the rate of optimal asymmetric-error-correcting codes for the error fraction$\tau \ge 1/4$vanishes as the blocklength grows. In this paper, we give an efficient feedback encoding scheme with$n$transmissions that achieves a positive rate for any fraction of errors$\tau < 1$and$n\to \infty $. Additionally, we state an upper bound on the rate of asymptotically long feedback asymmetric error-correcting codes.

A new problem of transmitting information over the adversarial insertion-deletion channel with feedback is introduced. Assume that the encoder transmits $$n$$ binary symbols one by one over a channel in which some symbols can be deleted and some additional symbols can be inserted. After each transmission, the encoder is notified about insertions or deletions that have occurred within the previous transmission, and the encoding strategy can be adapted accordingly. The goal is to design an encoder that is able to transmit error-free as much information as possible under the assumption that the total number of deletions and insertions is limited by $$\tau n$$ , $$0<\tau<1$$ . We show how this problem can be reduced to the problem of transmitting messages over the substitution channel. Thereby, the maximal asymptotic rate of feedback insertion-deletion codes is completely established. The maximal asymptotic rate for the adversarial substitution channel has been partially determined by Berlekamp and later completed by Zigangirov. However, the analysis of the lower bound by Zigangirov is quite complicated. We revisit Zigangirov's result and present a more elaborate version of his proof.

TheLearningwithErrors(LWE) problem is considered to be a hard problem and lies the foundation of various cryptographic algorithms. Several cryptosystems based on the closely relatedRingLearningwithErrors(RLWE) problem have been proposed within the NIST PQC standardization process, e.g., the systems LAC and NewHope. The combination of encryption and decryption for these kinds of algorithms can be interpreted as data transmission over noisy channels. To the best of our knowledge this paper is the first work that analyzes the capacity of this channel. We extend this channel from binary toq-ary alphabets and show that this does not compromise the security of the related RLWE-based schemes if appropriate error correcting codes are used to prevent thedecryptionfailurerate(DFR) from increasing. We give a lower bound on the capacity of this channel showing that the achievable asymptotic rates are substantially (5.7 times for LAC and 10.7 times for NewHope) higher than the currently deployed ones for the finite length regime. Furthermore, under the assumption of stochastically independent coefficient failures, we show that substantially higher rates can also be achieved in the finite length setting by using the Gilbert-Varshamov bound. Moreover, we give explicit code constructions increasing the achievable rate by a factor of 2 for LAC and a factor of 7 for NewHope without increasing the DFR for the respective parameter sets achieving a security level equivalent to AES256.

The foreseeable breakthrough of quantum computers represents a risk for secure communications. In order to prepare for such an event, electronic systems must integrate secure quantum-computer-resistant (post-quantum) cryptography protected against implementation attacks. The NTRU cryptosystem is one of the main alternatives for practical implementations of post-quantum public-key cryptography. The standardized version of NTRU (IEEE 1363.1) provides security against chosen ciphertext attacks (CCA) through a padding scheme that limits ciphertext malleability, thus restricting a large range of attacks. So far, previous NTRU hardware implementations do not include the NTRU padding scheme. Moreover, a previously proposed NTRU optimization of the polynomial multiplication leads to a degradation of the security level. Therefore, previous works provide a wrong impression regarding the real implementation cost of NTRU. In this work, we present two contributions: i) the first complete and compact NTRU hardware implementation; and ii) the analysis of the security degradation due to the NTRU multiplication optimization proposed in previous works.