Abstract The regular decoding problem asks for (the existence of) regular solutions to a syndrome decoding problem (SDP). This problem has increased applications in post-quantum cryptography and cryptanalysis. Recently, Esser and Santini explored in depth the connection between the regular (RSD) and classical syndrome decoding problems. They have observed that while RSD to SDP reductions are known (in any parametric regime), a similar generic reduction from SDP to RSD is not known. In our contribution, we examine two different generic polynomial reductions from a syndrome decoding problem to a regular decoding problem instance. The first reduction is based on constructing a special parity check matrix that encodes weight counter progression inside the parity check matrix, which is then the input of the regular decoding oracle. The target regular decoding problem has a significantly longer code length, that depends linearly on the weight parameter of the original SDP. The second reduction is based on translating the SDP to a non-linear system of equations in the Multiple Right-Hand Sides form, and then applying RSD oracle to solve this system. The second reduction has better code length. The ratio between RSD and SDP code length of the second reduction can be bounded by a constant (less than 8).

We propose a new hybrid encryption scheme to use with McEliece cryptosystem. The hybrid scheme uses specific authenticated encryption scheme for the encryption of the plaintext. The symmetric key is embedded in reversible way into the error vector of the McEliece cryptosystem. CCA2 security is prov ided by the symmetric part of the scheme. The embedding is done in such a way, that the error vector cannot be distinguished from a randomly chosen one. An eXtensible Output Function can be used to enable variable length conversion from (pseudo-random) bit strings to error vectors. The encryption part can be implemented in a streamed way, so the sender does not have to store the whole message in the memory.

The article examines a practical application of the method of syllogisms to solve a system of Boolean equations arising in the cryptanalysis of the stream cipher Trivium. Experimental results show that different guessing strategies lead to significan