Search

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). [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

In digital systems such as fiber optical communications, the ratio between probability of errors of type 1 → 0 and 0 → 1 can be large. Practically, one can assume that only one type of error can occur. These errors are called asymmetric. Unidirectional errors differ from asymmetric type of errors; here both 1 → 0 and 0 → 1 type of errors are possible, but in any submitted codeword all the errors are of the same type. This can be generalized for the q -ary case. We consider q -ary unidirectional channels with feedback where the errors have magnitude one and give bounds for the capacity error function. It turns out that the bounds depend on the parity of the alphabet size q. Furthermore, we show that for feedback, the capacity error function for the binary asymmetric channel is different from the symmetric channel. This is in contrast to the behavior of the function without feedback. [ABSTRACT FROM AUTHOR]