In this paper, we introduce an oracle version of the Restricted Syndrome Decoding Problem (RSDP) and propose novel authentication protocols based on the hardness of this problem. They follow the basic structure of the HB-family of authentication protocols and later improvements but demonstrate several advantages.An appropriate choice of multiplicative subgroup and ring structure gives rise to a very efficient hardware implementation compared to other Learning Parity with Noise based approaches. In addition, the new protocols also have lower key size, lower communication costs, and potentially better completeness/soundness compared to learning-based alternatives. This is appealing in the context of low-cost, low-powered authenticating devices such as radio frequency identification (RFID) systems. Lastly, we show that with additional assumptions, RSDP can be used to instantiate a Man-in-the-Middle secured authentication protocol.

We present a simple key-recovery attack on the LCMQ Authentication Protocol, an RFID authentication protocol proposed by Li, Gong, and Qin in 2013. We show that a successful attack is performed by solving a Learning Parity with Noise instance in a not-too-large dimension. For the proposed LCMQ parameters, the attack requires only a few invocations with the tag under attack. When there is no restriction on the number of invocations, state-of-the-art LPN solvers recover the keys with complexity below$2^{51}$and$2^{86}$, when attacking LCMQ parameters for security levels 80-bit and 128-bit, respectively. To the best of our knowledge, this is the first attack on LCMQ with complexity below exhaustive key search.

The problem of decoding random codes is a fundamental problem for code-based cryptography, including recent code-based candidates in the NIST post-quantum standardization process. In this paper, we present a novel Sieving-style Information-set Decoding algorithm, addressing the task of solving the syndrome decoding problem. Our approach involves maintaining a list of weight-$2p$solution vectors to a partial syndrome decoding problem and then creating new vectors by identifying pairs of vectors that collide in p positions. By gradually increasing the parity-check condition by one and repeating this process iteratively, we find the final solution(s). We show that our novel algorithm performs better than other ISDs in the memory-restricted scenario when applied to McEliece. Notably, in the case of problem instances with very low relative weight, the sieving approach uses significantly less memory compared to other ISD algorithms while being competitive in terms of performance.

Pseudo-random functions are a fundamental building block in many cryptographic applications. In certain scenarios, a weaker notion (where security is restricted to uniformly random input), but more computationally efficient, called weak pseudo-random functions, is sufficient. In this work, we present new differential attacks on the main binary weak pseudo-random function constructions, namely the so-called Alternative Mod-2/Mod-3. For the Alternative Mod-2/Mod-3 wPRF, the best distinguisher proposed by Cheon et al. achieves O(20.21n) complexity, where n is the input length. We show that our attack asymptotically outperforms this and requires far fewer samples that can be applied in restricted oracle settings. By minimizing computational complexity, we can achieve O(20.166n) complexity. Additionally, in a small experiment, we indicate that their proposed fix of using keys with large Hamming weight is even more vulnerable to our attack.

Local pseudorandom generators are a class of fundamental cryptographic primitives having very broad applications in theoretical cryptography. Following Couteauet al.’swork at ASIACRYPT 2018, this paper further studies the concrete security of one important class of local pseudorandom generators, i.e., Goldreich’s pseudorandom generators. Our first attack is of the guess-and-determine type. Our result significantly improves the state-of-the-art algorithm proposed by Couteauet al., in terms of both asymptotic and concrete complexity, and breaks all the challenge parameters they proposed. For instance, for a parameter set suggested for 128 bits of security, we could solve the instance faster by a factor of about 277, thereby destroying the claimed security completely. Our second attack further exploits the extremely sparse structure of the predicate$P_{5}$and combines ideas from iterative decoding. This novel attack, named guess-and-decode, substantially improves the guess-and-determine approaches for cryptographic-relevant parameters. All the challenge parameter sets proposed in Couteauet al.’swork in ASIACRYPT 2018 aiming for 80-bit (128-bit) security levels can be solved in about 258(278) operations. We suggest new parameters for achieving 80-bit (128-bit) security with respect to our attacks. We also extend the attacks to other promising predicates and investigate their resistance.

A new “Weighted Bit-flipping” (WBF) iterative decoder is presented and analyzed with respect to its Decoding Failure Rate (DFR). We show that the DFR is indeed lower than that of the BGF decoder as suggested by the BIKE third round submission to the NIST PQC standardization process. The WBF decoder requires more iterations to complete than BGF, but by creating a hybrid decoder we show that a lower DFR compared to that of the BGF decoder can still be achieved while keeping the computational tradeoff to a minimum.

SNOW 3G is a stream cipher used as one of the standard algorithms for data confidentiality and integrity protection over the air interface in the 3G and 4G mobile communication systems. SNOW-V is a recent new version that was proposed as a candidate for inclusion in the 5G standard. In this paper, we propose a faster variant of SNOW-V, called SNOW-Vi, that can reach the targeted speeds for 5G in a software implementation on a larger variety of CPU architectures. SNOW-Vi differs in the way how the LFSR is updated and also introduces a new location of the tap T2 for stronger security, while everything else is kept the same as in SNOW-V. The throughput in a software environment is increased by around 50% in average, up to 92 Gbps. This makes the applicability of the cipher much wider and more use cases are covered. The security analyses previously done for SNOW-V are not affected in most aspects, and SNOW-Vi provides the same 256-bit security level as SNOW-V.

Abstract This survey overviews the potential use of cryptographic primitives in the fifth-generation mobile communications system (aka 5G) and beyond. It discusses the new security challenges that come with 5G and presents the upcoming security architecture. It shows the use of current cryptographic algorithms and discusses new algorithms or modifications of existing ones, that can be relevant. It also discusses the need for lightweight algorithms to meet the new use cases as well as the general demand for algorithms secure even when large quantum computers are available.

Abstract We present a new algorithm for solving the LPN problem. The algorithm has a similar form as some previous methods, but includes a new key step that makes use of approximations of random words to a nearest codeword in a linear code. It outperforms previous methods for many parameter choices. In particular, we can now solve the $$(512,\frac{1}{8})$$ (512,18) LPN instance with complexity less than $$2^{80}$$ 280 operations in expectation, indicating that cryptographic schemes like HB variants and LPN-C should increase their parameter size for 80-bit security.

We improve iterative decoding of the moderate density parity-check codes, recently suggested as code candidates in the McEliece public key cryptosystem. In case of bit-flipping (BF) decoder failure, the code parity-check matrix is extended by adding auxiliary variable nodes based on reliability information from the BF decoder. Then iterative decoding is applied to the extended parity-check matrix. The proposed decoding algorithm is analyzed and its frame error rate performance is compared to the same performance of both the best implementations of BF decoding and its modifications. It is demonstrated an improved performance for the iterative decoding step in decryption, which allows to increase the resistance against recent attacks based on taking advantage of the somewhat large failure probability of the BF algorithm.

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 = n2and √ noise level σ = n1.5/( 2π log22 n), the asymptotic complexity is 20.893nin the standard setting, improving 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.

Algorithms for secure encryption in a post-quantum world are currently receiving a lot of attention in the research community. One of the most promising such algorithms is the code-based scheme called QC-MDPC, which has excellent performance and a small public key size. In this paper, we present a very efficient key recovery attack on the QC-MDPC scheme using the fact that decryption uses an iterative decoding step, and this can fail with some small probability. We identify a dependence between the secret key and the failure in decoding. This can be used to build what we refer to as a distance spectrum for the secret key, which is the set of all distances between any two ones in the secret key. In a reconstruction step, we then determine the secret key from the distance spectrum. The attack has been implemented and tested on a proposed instance of QC-MDPC for 80-bit security. It successfully recovers the secret key in minutes. A slightly modified version of the attack can be applied on proposed versions of the QC-MDPC scheme that provides IND-CCA security. The attack is a bit more complex in this case, but still very much below the security level. The reason why we can break schemes with proved CCA security is that the model for these proofs typically does not include the decoding error possibility. At last, we present several algorithms for key reconstruction from an empirical distance spectrum. We first improve the naïve algorithm for key reconstruction by a factor of about 3 0000, when the parameters for 80-bit security are implemented. We further develop the algorithm to deal with errors in the distance spectrum. This ultimately reduces the requirement on the number of ciphertexts that need to be collected for a successful key recovery.

The Bit Flipping algorithm is a hard decision decoding algorithm originally designed by Gallager in 1962 to decode Low Density Parity Check Codes (LDPC). It has recently proved to be much more versatile, for Moderate Parity Check Codes (MDPC) or Euclidean metric. We further demonstrate its power by proposing a noisy Euclidean version of it. This tweak allows to construct a lattice based key exchange analogous to the Ouroboros protocol for Hamming metric but with a reduction to the Short Integer Solution (SIS) problem. The very efficient decoding algorithm permits to consider smaller alphabets than for NTRU or Ring-LWE decryption algorithms. Overall we obtain a new protocol which competes with the recent NEWHOPE and Kyber proposals, and also with NTRU. The resulting scheme exploits the cyclicity of the error, and benefits from the security of the renowned SIS problem.

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. Stern's algorithm is the origin of the most efficient algorithms in this class. In this paper we consider the same decoding problem but for a channel with soft information. We give a version of Stern's algorithm for a channel with soft information that includes some novel steps of ordering vectors in lists, based on reliability values. We then demonstrate how this new algorithm can be used in a few cryptographic applications, including a very efficient attack on a recently proposed McEliece-type cryptosystem.

The McEliece public key cryptosystem is an attractive general construction that has received extensive attention over the years. Recently, a very promising version called QC-MDPC, was proposed. By using binary quasi-cyclic codes, the size of the public key can be decreased significantly. The decryption step involves iterative decoding of moderate density parity check codes (MDPC). In this paper we propose a non-binary version of QC-MDPC. The errors in the new scheme are discrete Gaussian and the decryption involves a new type of iterative decoding with a non-binary alphabet. The resulting scheme improves upon the binary QC-MDPC in that the size of the pubic key can be even smaller.

One of the approaches to modify the McEliece cryptosystem to overcome its large key size is replacing binary Goppa codes with a new structured code. However, this modification makes such cryptosystems encounter some new attacks. There are a few modified McEliece cryptosystem variants which are known to be secure. One of them is the cryptosystem introduced by Baldi et al . which uses quasi‐cyclic low‐density parity check (QC‐LDPC) codes. This cryptosystem is still unbroken as no efficient attack has been reported against it since 2008. In this study, an attack has been applied to this cryptosystem which is feasible when the code length is a multiple of a power of 2. Also an important weakness of this kind of cryptosystem has been pointed out, namely utilising a too low‐weight intentional error vector. The authors have established a new security level for this cryptosystem which is applicable to other McEliece‐like cryptosystems using QC‐LDPC codes. This security level for instance is 2 9.18 times lower than previous ones in the case of n = 4 × 4096 when only one ciphertext is available. The gain of the attack in this study can be increased if more than one ciphertext is available.

The learning parity with noise (LPN) problem has recently proved to be of great importance in cryptology. A special and very useful case is the Ring-LPN problem, which typically provides improved efficiency in the constructed cryptographic primitive. We present a new algorithm for solving the Ring-LPN problem in the case when the polynomial used is reducible. It greatly outperforms the previous algorithms for solving this problem. Using the algorithm, we can break the Lapin authentication protocol for the proposed instance using a reducible polynomial, in ~271bit operations.

The authors consider hardware-oriented message authentication, more specifically universal hash functions. The authors propose a new type of constructions that appear promising. These constructions are based on the framework of universal hash functions, Toeplitz matrices and ɛ-biased sample spaces. Some new theoretical results in this area are derived. The new constructions come at the price of not being able to prove the exact substitution probability. The expected probability is examined both through theoretical methods as well as through simulation.

In this study, the authors investigate the resistance of Boolean functions against fast algebraic attacks and deduce a bound between fast algebraic immunity and higher-order non-linearity (it is the first time that a bound between these two cryptographic criteria is given). The authors then show that the fast algebraic immunity of the following two classes of Boolean functions is not good: (a) The repaired functions of the Tu–Deng function proposed by Carlet. The Tu–Deng function has optimum algebraic degree, optimum algebraic immunity and a very good non-linearity. However, it is weak against fast algebraic attacks. Carlet found this weakness and also tried to repair it. (b) An infinite class of balanced functions proposed by Tang et al., having optimum algebraic degree, optimum algebraic immunity and a very high non-linearity.

It is well known that fast correlation attacks can be very efficient if the feedback polynomial is of low weight. These feedback polynomials can be considered weak in the context of stream ciphers. This paper generalizes the class of weak feedback polynomials into polynomials were taps are located in several groups, possibly far apart. Low-weight feedback polynomials are thus a special case of this class. For the general class, it is shown that attacks can sometimes be very efficient even though the polynomials are of large weight. The main idea is to consider vectors of noise variables. It is shown how the complexity of a distinguishing attack can be efficiently computed and that the complexity is closely related to the minimum row distance of a generator matrix for a convolutional code. Moreover, theoretical results on the size of the vectors are given.

A new distinguishing attack scenario for stream ciphers, allowing a resynchronization collision attack, is presented. The attack can succeed if the part of the state that depends on both the key and the IV is smaller than twice the key size. It is shown that the attack is applicable to block ciphers in OFB mode. For OFB mode, the attack is more powerful than the previously known generic distinguishing attack since it will directly recover a part of the plaintext while having the same asymptotic complexity as the generic distinguishing attack. The attack is also demonstrated on the eSTREAM candidate LEX. LEX is not vulnerable to any of the previously known generic distinguishing attack but is vulnerable to the new attack. It is shown that if approximately 265.7resynchro-nizations using LEX are performed for the same key, some plaintext might be recovered.

A key recovery attack on the stream cipher Achterbahn-128/80, a cipher in the second phase of eSTREAM, is given. The key observation is a high dependency between some input bits to the Boolean combining function generating the keystream. It results in the first known attacks on both the 128-bit and the 80-bit variants of the cipher. The number of keystream bits required in the attacks is less than 264, the maximum frame length.

A linear distinguishing attack on the stream cipher Scream is proposed. When the keystream is of length 298words, the distinguisher has a detectable advantage. When the keystream length is around 2120the advantage is very close to 1. This shows certain weaknesses of Scream. In the process, the paper introduces new general ideas on how to improve the performance of linear distinguishing attacks on stream ciphers.

A new stream cipher, Grain-128, is proposed. The design is very small in hardware and it targets environments with very limited resources in gate count, power consumption, and chip area. Grain-128 supports key size of 128 bits and IV size of 96 bits. The design is very simple and based on two shift registers, one linear and one nonlinear, and an output function

The self-shrinking generator was introduced in 1994. It is based on the idea behind the shrinking generator and despite its simplicity it has remained remarkably resistant to efficient attacks. Several known plaintext attacks have been proposed on the generator, some operating on a short keystream and others requiring a longer sequence to succeed. In this paper, two new attacks on the self-shrinking generator are proposed. The first attack, using a short known keystream, has the same complexity as the BDD-based attack, which is the best previously known attack. However, while the BDD-based attack requires a huge amount of memory, the proposed algorithm uses almost no memory, leaving it as the preferred alternative. The second attack operates on a longer known keystream, exponential in the length of the LFSR. The attack considers one or several segments of keystream bits and guesses that these bits stem from LFSR segments of some size. It is shown that this attack achieves better complexity than any previously known attack

Stream ciphers like Snow 2.0 are very promising techniques for encryption in trusted hardware, but demand specialized IP cores to enhance conventional architectures. The paper describes the design of such a core that can be adapted to the system needs according to a ratio of throughput and effective slice usage of 3.2 to 3.5. The footprint is comparable with a commercial floating-point unit.

We propose a simple modification of the famous Bahl-Cocke-Jelinek-Raviv (BCJR) algorithm for linear block codes. The modified algorithm requires one forward and two backward recursions in the code trellis, but eliminates the need to store the whole trellis. Compared with the BCJR algorithm, the computational complexity is slightly increased, but the storage requirement is reduced.

A5/1 is a stream cipher used in the Global System for Mobile Communications (GSM) standard. Several time-memory tradeoff attacks against A5/1 have been proposed, most notably the attack by Biryukov, Shamir and Wagner (1978), which can break A5/1 in seconds using huge precomputation time and memory. This article presents a completely different attack on A5/1, based on ideas from correlation attacks. Whereas time-memory tradeoff attacks have a complexity which is exponential with the shift-register length, the complexity of the proposed attack is almost independent of the shift-register length. Our implementation of the suggested attack breaks A5/1 in a few minutes using 2-5 min of conversation plaintext.

We provide a construction technique for multiple-output resilient functions F:F/sub 2//sup n//spl rarr/F/sub 2//sup m/ with high nonlinearity. The construction leads to the problem of finding a set of linear codes with a fixed minimum distance, having the property that the intersection between any two codes is the all-zero codeword only. This problem is considered, and existence results are provided. Moreover, the constructed functions obtain a nonlinearity superior to previous construction methods.

One general class of attacks on stream ciphers is correlation attacks. Most of previous results regarding performance of correlation attacks have been based entirely on simulations. We use random coding bounds for convolutional codes to give a theoretical analysis of a previously proposed correlation attack based on convolutional codes. The results from the theoretical derivation are verified by simulations.

A new probabilistic algorithm for decoding one received word from a set of many given received words, into a codeword such that the Hamming distance between the received word and the codeword is at most t, is proposed. The new algorithm is applicable to several cryptographic problems, such as the Stern (1989, 1994) identification scheme, the McEliece (1978) public-key cryptosystem, and in correlation attacks on stream ciphers. When applicable, it runs significantly faster than previous algorithms used for attacks on these cryptosystems.

Soft-input/soft-output symbol decoding plays a significant role in iterative decoding. We propose a simple optimal soft-input/soft-output symbol decoding algorithm for linear block codes which requires one forward recursion using a trellis. For many codes the decoding complexity is lower than previous methods, such as the algorithm by Bahl et al. (1974), and the decrease is shown at its most when decoding Hamming codes.

In both open and private communication the participants face potential threats from a malicious enemy who has access to the communication channel and can insert messages (impersonation attack) or alter already transmitted messages (substitution attack). Authentication codes (A-codes) have been developed to provide protection against these threats. In this paper we introduce a new distance, called the authentication distance (A-distance), and show that an A-code can be described as a code for the A-distance. The A-distance is directly related to the probability P/sub S/ of success in a substitution attack. We show how to transform an error-correcting code into an A-code and vice versa. We further use these transformations to provide both upper and lower bounds on the size of the information to be authenticated, and study their asymptotic behavior. As examples of obtained results, we prove that the cardinality of the source state space grows exponentially with the number of keys provided P/sub S/>P/sub I/, we generalize the square-root bound given by Gilbert, MacWilliams, and Sloane in 1979, and we provide very efficient constructions using concatenated Reed-Solomon codes.

For SIMD computers, using virtual processors, a common strategy for mapping the processors on the image data is to apply one processor per pixel. For operations on gray level images it is a good approach, but for operations on binary images many of the available processors are idle and not used in the calculation. This paper presents some common binary operations on a new and more compact representation of the binary objects in an image, which leads to a more efficient processor utilisation and faster algorithms. The implementations are for a Connection Machine/200. The new data representation is tested on a typical application: the separation of touching objects.

The paper investigates a model for authentication in which not only an outsider, but also the transmitter or the receiver, may cheat. Lower bounds on the probability of success for different types of deception as well as on the parameters of secure authentication codes are derived. The latter bounds are shown to be tight by demonstrating codes in projective space that meet the bounds with equality.>