Syndrome Trellis Decryption in Post-Quantum Cryptography

SYNDROME-TRELLIS DECRYPTION IN CODEBASED POST-QUANTUM CRYPTOGRAPHY Meir Ariel School of Electrical and Computer Engineering, Faculty of Engineering, Tel Aviv University, Tel Aviv, Israel

ABSTRACT We present a novel post-quantum cryptographic framework based on masked highmemory convolutional codes in the Niederreiter paradigm. The public key is derived from a high-memory polynomial parity-check matrix augmented by dense random masking and additional invertible linear transformations. The resulting matrix exhibits strong random-like properties, effectively concealing its algebraic structure and resisting known structural and algebraic attacks. Legitimate recipients retain polynomial-time decoding capability, whereas adversaries appear to be limited to generic information-set decoding with exponential complexity. Under standard cryptanalytic estimates, the proposed construction achieves security margins exceeding those of classical McEliece- and Niederreiter-based systems by factors greater than 2²⁰⁰. Beyond its enhanced security profile, the construction offers considerable design flexibility, supporting arbitrary plaintext lengths, linear-time decryption, and a uniform per-bit computational cost, enabling efficient scalability to very long messages. Practical implementation is facilitated by a parallel array of syndrome-trellis decoders, dynamically instantiated according to candidate syndrome values, enabling efficient hardware and software implementations with high throughput. Overall, the proposed scheme is a promising candidate for robust, scalable, quantum-resistant public-key cryptography.

KEYWORDS Code-based cryptography, post-quantum cryptography, convolutional codes, syndrome trellis

1. INTRODUCTION Code-based cryptography, first proposed by Robert McEliece in 1978 [1], employs binary Goppa codes to construct a public-key encryption scheme. Its central idea is to disguise an errorcorrecting code through invertible linear transformations, thereby producing a public key that conceals the underlying algebraic structure. During encryption, the sender deliberately introduces controlled errors into the codeword, making decryption computationally infeasible for adversaries, while the legitimate recipient—who possesses the private key—can efficiently correct the errors and recover the original plaintext. Since its inception, numerous variants of the McEliece cryptosystem have been proposed, typically by replacing Goppa codes with alternative code families [2–3]. However, most of these alternatives have failed to preserve the strong security guarantees of the original construction. David C. Wyld et al. (Eds): CAIML, CRYPIS, NC, ITCSE – 2026 pp. 61-84, 2026. CS & IT - CSCP 2026

DOI: 10.5121/csit.2026.162004

62

Computer Science & Information Technology (CS & IT)

Consequently, Classic McEliece advanced to Round 4 of the NIST Post-Quantum Cryptography (PQC) standardization process [4], although it was ultimately not selected for standardization. Comprehensive surveys of code-based cryptography and its role in the PQC landscape are provided in [5–6]. Despite its robustness and long-standing security record, Classic McEliece suffers from several practical limitations. Its reliance on fixed Goppa codes imposes relatively rigid error-correction capabilities, limits adaptability across different security levels, and complicates deployment in diverse application environments. To address these limitations, Ariel [7–8] proposed a novel post-quantum cryptographic framework based on noise-enhanced high-memory convolutional codes. This approach enables dynamic code construction and selection while enhancing publickey security through dense, random-like generator matrices that conceal structural information more effectively than low-density or structurally recognizable matrices [9]. Moreover, the use of powerful convolutional codes with greater error-correcting capability permits the deliberate introduction of higher noise levels, thereby increasing resistance to cryptanalytic attacks by factors exceeding 2²⁰⁰ (depending on the selected parameters) compared with Classic McEliece. In addition, the framework supports scalability to very long plaintexts, linear-time decoding, and efficient hardware and software implementations with uniform per-bit computational complexity. The “Niederreiter Cryptosystem” was first proposed by Harald Niederreiter in 1986 [10] as a variant of the McEliece encryption scheme, using the parity-check matrix of a linear errorcorrecting code as the public key rather than the generator matrix. In this formulation, the plaintext is a coset leader𝒆, i.e., the minimum-Hamming-weight error vector associated with a given coset. The ciphertext is the syndrome 𝒔, obtained by multiplying 𝒆 by the public paritycheck matrix. Unlike the McEliece system, the ciphertext contains no additional injected errors. Nevertheless, the scheme remains probabilistic because the plaintext itself is a randomly selected error vector, while the public parity-check matrix appears random and has no known efficient decoder. The decryption problem in the Niederreiter cryptosystem is therefore equivalent to the classical syndrome decoding problem, which is known to be NP-hard. Moreover, as noted in [11], McEliece and Niederreiter cryptosystems are considered equivalent from the security perspective when corresponding parameter sets are used. Consequently, the Niederreiter scheme inherits many of the same limitations as Classic McEliece, including reliance on Goppa codes with rigid parameter selection, relatively limited error correction capabilities, and algebraic decoding procedures that are not well suited for efficient hardware implementations. In this paper we extend the framework presented in [7–8] by employing masked high-memory parity-check matrices derived from high-performance convolutional codes as public keys, thereby overcoming several limitations of the Niederreiter approach. The proposed post-quantum cryptographic framework offers the following advantages: Diverse Code Selection: A broad family of convolutional codes can serve as public keys, enabling flexible adaptation to different performance and security levels. Enhanced Public Key Security: The proposed scheme generates dense, random-like paritycheck matrices that effectively conceal structural information. Moreover, the use of powerful convolutional codes with high error-correcting capacity allows the selection of error vectors (plaintexts) with significantly larger Hamming weights, thereby increasing resistance to cryptanalytic attacks by factors exceeding 2²⁰⁰ (depending on the selected parameters) compared with the classical Niederreiter scheme.

Computer Science & Information Technology (CS & IT)

63

Scalability and Linear-Time Decoding: Unlike fixed-dimension block code constructions, the proposed framework supports plaintexts of arbitrary length. Decoding complexity grows linearly with plaintext size, enabling scalability without loss of efficiency. Efficient Implementation: Decryption is performed by an array of unique directed-graph decoders, referred to as Syndrome Trellises, that identify the correct plaintext while supporting efficient and straightforward hardware and software implementations. The remainder of this paper is organized as follows. Section 2 describes the construction of the public and private keys based on masked high-memory convolutional codes, which form the foundation of the proposed framework. Section 3 presents the encryption process, based on the selection of random error vectors, which is central to both security and reliable decryption. Section 4 introduces the construction of an array of syndrome-trellis decoders, and Section 5 details the corresponding decryption procedure performed by the legitimate recipient. Section 6 provides a worked implementation example, while Section 7 analyses potential attacks and evaluates the cryptanalytic resistance and computational complexity of the proposed scheme. Finally, Section 8 concludes the paper and summarizes the main findings. The principal contributions of this paper are as follows: • Extension of the previously proposed masked high-memory convolutional-code cryptographic framework from generator matrices to parity-check matrices, thereby enabling a Niederreiter-type post-quantum cryptosystem. • A novel directed-graph decryption algorithm for masked parity-check cryptosystems, based on high-memory convolutional codes. • A practical method for constructing syndrome trellises corresponding to arbitrary received syndromes, enabling efficient maximum-likelihood decoding in polynomial time. • A polynomial-time ambiguity-resolution technique that identifies the correct plaintext by minimum-weight decoding over multiple candidate syndrome trellises. • A complexity and security analysis showing that legitimate decryption scales linearly with the plaintext length while the best-known attacks remain exponential. • A complete worked implementation example illustrating key generation, encryption, syndrome-trellis construction, and decryption.

2. PUBLIC AND PRIVATE KEY CONSTRUCTION Throughout this paper, the notation follows that of [8] and is also summarized here for completeness. Binary vectors are denoted by bold lowercase letters (e.g., a, b) while their corresponding polynomial representations are written as a(x), b(x). The notations a and a(x) are used interchangeably whenever context is clear. The Hamming weight of a vector a is denoted by wt(a).Standard coding-theorynotation is adopted throughout: 𝒆 denotes an error vector,s denotes a syndrome, and polynomial generator or parity-check matrices associated with convolutional codes are denoted by uppercase letters such as G(x)and H(x), with their corresponding scalar representations written as G and H. Calligraphic letters, such as 𝒟 and ℒ, denote sets of binary vectors. To establish a clear foundation for the proposed cryptosystem, we first briefly review the classical Niederreiter cryptosystem: NiederreiterKey Generation (Bob) Let C be a binary (n, k) linear code capable of correcting up to t errors, with parity-check matrix

64

Computer Science & Information Technology (CS & IT) (𝑛−𝑘)×𝑛

H∈ 𝔽2 Bob randomly selects: (𝑛−𝑘)×(𝑛−𝑘) • a nonsingular matrix S∈ 𝔽2 , • a permutation matrix P∈ 𝔽𝑛×𝑛 . 2

He then publishes the obfuscated parity-check matrix: ̂ = 𝑆𝐻𝑃 𝐻

(1)

̂ , t), while the private key is (𝑆, 𝐻, 𝑃). The public key is (𝐻 Niederreiter Encryption (Alice) To encrypt a message Alice selects an error vector 𝒆 ∈ 𝔽𝑛2 with Hamming weight wt(𝒆) ≤ t, and computes the syndrome: ̂ 𝒆𝑇 𝒔=𝐻

(2)

The ciphertext is 𝒔 ∈ 𝔽𝑛−𝑘 2 . Niederreiter Security (Eve) ̂ and the intercepted 𝒔, Eve must solve Given 𝐻 ̂ 𝒆̂𝑇 𝒔=𝐻

(3)

for a low-weight vector 𝒆̂. This constitutes an instance of the classical syndrome decoding problem, which is believed to be computationally intractable for suitably chosen parameters. ̂ appears random and admits no efficient decoding algorithm, recovering𝒆̂is Since𝐻 computationally infeasible. Niederreiter Decryption (Bob) Bob first computes 𝒔′ = 𝑆 −1 𝒔 = 𝐻𝑃𝒆𝑇

(4)

′

Let 𝒆 = 𝒆𝑃, then 𝒔′ = 𝐻𝒆′

𝑇

(5)

Using the decoder associated with the codeC, Bob recovers the unique low-weight vector𝒆′ , and finally computes 𝒆̂ = 𝒆′ 𝑃−1

(6)

Correctness follows directly from the decoding capability of C for all error vectors satisfying ̂ does not wt(𝒆) ≤ t. Security relies on selecting a code such that the public matrix 𝐻 revealexploitable algebraic structure.

Computer Science & Information Technology (CS & IT)

65

We now describe the construction of the public and private keys in the proposed framework, based on a masked high-memory parity-check matrix derived from a convolutional code, which forms the foundation of the proposed cryptographic scheme. Denote by pi(x) a binary polynomial of memory at mostp 𝑝

pi(x)= ∑𝑗=0 𝑎𝑗 𝑥 𝑗 ,

(7)

𝑎𝑗 ∈ 𝔽2

A Convolutional Code (CC) is defined as a set of n constituent polynomials, commonly structured into the form of a polynomial generator matrix 𝐺(x) = [p0(x), p1(x), …, pn-1(x)]

(8)

The matrix 𝐺(x) determines both the code rate and the error-correction capability of the CC, typically characterized by its free distance dfree. The polynomial matrix 𝐺(x) admits an equivalent infinite-dimensional scalar representation 𝐺, whose coefficient k × n matrices 𝒈𝑖 corresponds to the coefficients of xi: 𝒈0 𝟎 𝐺= 𝟎 [ ⋮

𝒈1 𝒈0 𝟎

𝒈2 𝒈1 𝒈0

... ... ...

𝒈𝑝 𝒈𝑝−1 𝒈𝑝−2

𝟎 𝒈𝑝 𝒈𝑝−1

𝟎 𝟎 𝒈𝑝

𝟎 𝟎 𝟎

... ... ...

(9) ]

For example, for 𝐺(x) = [1+x+x2, 1+x2], the corresponding coefficient vectors are 𝒈0 = [1 1], 𝒈1 = [10], 𝒈2 = [1 1]. A CC mayalso be defined by its (n – k) × npolynomial parity-check matrix𝐻(x) satisfying 𝐺(x) 𝐻(x)T= 0

(10)

For rate-½ CCs, 𝐻(x) is obtained simply by reversing the order of the generator polynomials. Like 𝐺(x), 𝐻(x) admits a scalar representation 𝐻, whose coefficients(n – k) × n matrices

𝒉𝑖 correspond to the coefficients of xi.

𝒉0 𝒉1 𝒉2 ⋮ 𝐻 = 𝒉𝑝−1 𝒉𝑝 𝟎 𝟎 [ ⋮

𝟎 𝒉0 𝒉1 𝒉2 ⋮ 𝒉𝑝−1 𝒉𝑝 𝟎

𝟎 𝟎 𝒉0 𝒉1 𝒉2 ⋮ 𝒉𝑝−1 𝒉𝑝

...

(11)

]

For simplicity, we focus on CCs of rate 1/n (i.e., n–k=1). The proposed construction, however, is readily applicable to arbitrary CCs, including punctured codes. Each constituent polynomial pi(x)is multiplied by a high-memory polynomial𝒒(𝑥)of degree q,

66

Computer Science & Information Technology (CS & IT) 𝑞

𝒒(𝑥) = ∑𝑗=0 𝑏𝑗 𝑥 𝑗 , 𝑏𝑗 ∈ 𝔽2

(12)

yieldinga high-memory parity-check matrix 𝐻 ′ (x) = 𝐻(x)𝒒(𝑥)= [p0(x)𝒒(𝑥), p1(x)𝒒(𝑥), …, pn-1(x)𝒒(𝑥)]

(13)

The proposed framework imposes no strict constraints on the choiceof 𝒒(𝑥). In practice, however, the parameters p and q are chosen such that p + q> 200,p≪q thereby providing a very large effective memory. The corresponding scalar representation𝐻 ′ therefore exhibits substantially longer column run lengths and significantly higher density than the original parity-check matrix 𝐻 𝒉0 𝒉1 𝒉2 ⋮ 𝐻 ′ = 𝒉𝑝+𝑞−1 𝒉𝑝+𝑞 𝟎 𝟎 [ ⋮

𝟎 𝒉0 𝒉1 𝒉2 ⋮ 𝒉𝑝+𝑞−1 𝒉𝑝+𝑞 𝟎

𝟎 𝟎 𝒉0 𝒉1 𝒉2 ⋮

...

(14)

𝒉𝑝+𝑞−1 𝒉𝑝+𝑞 ]

The desired plaintext length N determines the dimensions of a truncated matrix𝐻 ′ . Specifically, the number of columns is fixed atN, while the number of rows, denoted byN – K, depends on both the coderate and the overall memory length of the CC. For rate-1/nCCs 𝑁

N – K = N + p + q– 𝑛

Increasing the degree of the high-memory polynomial 𝒒(𝑥)not only increases the density and apparent randomness of the resulting public matrix, making it more suitable for subsequent concealing transformations, but also enlarges both the associated syndrome and decoder state spaces. Together, these effects increase the complexity of structural analysis and decoding attacks, thereby strengthening the cryptographic security of the proposed framework. For a CC with memory m, a Viterbi decoder employs a trellis with 2mstates. Appending m zero bits to the encoder input forces the trellis into a unique terminal state. Similarly, in the proposed framework, decoding is formulated as a search for the most likely error vector within a given coset. This search is performed on a directed graph representing the coset, known as a syndrome trellis [12–13]. The last m syndrome bits drive the syndrome trellis to a unique terminal state, as described in Section 4. Since each coset has its own syndrome trellis, the graph is generated dynamically, section by section, according to the syndrome values. Such on-the-fly generation is essential because the number of cosets—and hence syndrome trellises—is astronomically large, making precomputation impractical. As follows from Equation (14), each group of n columns of 𝐻 ′ is obtained by shifting the preceding group downward byn – k bits. Although multiplication by the high-memory polynomial 𝒒(𝑥)significantlyincreases column run lengths of𝐻 ′ , permutation alone cannot

Computer Science & Information Technology (CS & IT)

67

conceal its structure, since the remaining zero sequences still reveal recognizable diagonal patterns. To eliminate this structure and maximize density, we introduce an(N – K) × N masking ̃ of rank l. Each column of 𝐻 ̃ is selected randomly from the linear span of a predefined matrix𝐻 set ℒ of l random binary vectors of length N – K. Denoting this span by LS(ℒ) = {𝒍0 , 𝒍1 , … , 𝒍2𝑙 −1 }

(15)

where each𝒍𝑖 isa distinct linear combination of the vectors inℒ, the masked parity-check matrix is ̃ 𝐻′ ⊕ 𝐻 where ⊕denotes bitwise addition over 𝔽2 .This operation destroys the original diagonal structure ̃ may be chosen so that of 𝐻 ′ , producing a dense random-like matrix. Since 𝐻 ′ has full rank,𝐻 ′ ̃ also has full rank, enabling subsequent invertible transformations. The public key 𝐻 ⊕𝐻 ̂ is then defined as matrix𝐻 ̂ = 𝑆(𝐻 ′ ⊕ 𝐻 ̃ )𝑃 𝐻 (16) where S is a random nonsingular (N – K) × (N – K)matrix and 𝑃is a random N × N permutation matrix. The matrix Sobscures the correspondence between error vectors (plaintexts) and syndromes (ciphertexts),while 𝑃concealsthe column positions. Consequently, the transformation ̂ combines reversible operations𝒒(𝑥),𝑆 and 𝑃withthe random masking operation 𝐻 ̃, from 𝐻 to 𝐻 ̂ yieldinga dense random-like public matrix. We refer to 𝐻as theHigh-Memory Masked ParityCheck(MPC) matrix. To ensure reliable decryption despite the syndrome perturbation introduced by masking, the correct plaintext is identified as the candidate coset leader with minimum Hamming weight, while all other candidates behave essentially as random coset leaders.An error vector 𝒆is generated by independently injecting errors into an all-zero sequence of length Nwith probability ε, yielding wt(𝒆) ≈εN (17) In contrast, a random coset leader 𝒆̃ typically has Hamming weight wt(𝒆̃) ≈ 𝛿

(18)

where 𝛿denotes the typical nearest-neighbor distance given by the Gilbert bound 𝛿 𝑁

𝐸( )≈ 1−

𝐾 𝑁

(19)

and 𝐸(⋅)denotes the binary entropy function. Incorrect masking vectors produce essentially random cosets. Consequently, their minimum-weight representatives concentrate around 𝛿. Since εN<<𝛿 the probability that an incorrect candidate attains weight close to εN decreases exponentially with N. The parameter ε is chosen to balance reliable decryption against cryptanalytic resistance. An important advantage of this approach is that the error vector is statistically random. Correct decryption, however, is not guaranteed, since localized clusters of errors may occasionally cause decoding failure. The probability of such failures can be estimated in advance, allowing ε to be selected accordingly, as discussed in Section 7. Finally, the decoder described in Section 4

68

Computer Science & Information Technology (CS & IT)

performs optimum decoding and therefore requires no prior knowledge of either the number or distribution of injected errors. Decryption failure may be eliminated by constraining the error injection process as follows: Partition the error vector into “windows” of length 𝑤 = n(p+1) For a CC with free distance dfree, any two trellis paths that diverge and remerge within such window differ in at least dfree positions.Consequently, up to 𝑡𝑖 ≤

𝑑𝑓𝑟𝑒𝑒 − 1

2

(20)

errors can be corrected reliably within the i-thwindow. The resulting error vector therefore has Hamming weight 𝑁

wt(𝒆) = ∑𝑤 𝑡 𝑖=1 𝑖

(21)

Under this constraint, correct decoding is guaranteed. Even so, the number of possible plaintexts remains astronomically large. Assuming, for simplicity, a fixed value of𝑡𝑖 for all windows. The total number of possible plaintexts is 𝑤 𝑁/𝑤 (𝑡 ) 𝑖 For the CC parameters considered in Section 7, namelyw = 30, dfree=20 (hence 9 correctable errors per window), 𝑡𝑖 = 7 and N = 8200 30 273 ( ) ≈ 2 × 101722 7 demonstrating the enormous plaintext space obtainable even under constrained error injection. Nevertheless, this approach is less desirable than fully random error generation, since imposing structure on the plaintext may introduce potential avenues for cryptanalytic attacks. The public and private keys are therefore defined as follows: ̂ , 𝜀} Public key: {𝐻 ̃} Private key: {𝑆, 𝑃, 𝐻, 𝒒(𝑥), 𝐻 Decryption proceeds in several stages. First, the inverse transformation S-1 is applied to the ̃ must then be removed; however, this operation received syndrome. The masking introduced by 𝐻 ̃ is not fully reversible. Although 𝐻 is known to the legitimate recipient, the plaintext error vector is unknown, and consequently the corresponding linear combination of masking vectors added during encryption is also unknown, resulting in ambiguity. Next, the obfuscation introduced by the high-memory polynomial 𝒒(𝑥)is reversed, since practical decoding can be performed only with the original parity-check matrix 𝐻, not its highmemory counterpart 𝐻 ′ .Accordingly, all candidate syndromes are first unmasked and then divided by 𝒒(𝑥). An array of syndrome-trellis decoders then searches the corresponding candidate cosets of 𝐻 for the most likely error vector. Among all decoded candidates, the one

Computer Science & Information Technology (CS & IT)

69

with minimum Hamming weight is selected, and the plaintext is finally recovered by applying the inverse permutation P-1.The complete decryption procedure is presented in Section 5.

3. ENCRYPTION BY SENDER Assuming the sender possesses the public key, encryption proceeds as follows. Step1-Plaintext Generation: A random error vector 𝒆 ∈ 𝔽𝑁 2 is generatedby independently flipping each bit of an all-zero sequence of length N with probability ε. Step 2–Syndrome Computation: The ciphertext, represented by the syndrome s∈ 𝔽𝑁−𝐾 2

is computed as

̂ 𝒆𝑇 . s=𝐻

(22)

Step 3-Transmission: The syndrome 𝒔is transmitted to the recipient. In practice, rare decoding failures can be detected reliably either by appending a CRC during encryption or by verifying that the Hamming weight of the decoded error vector matches its expected value (see Section 5). Upon detection of a failure, retransmission may be requested.

4. CONSTRUCTION OF SYNDROME TRELLISES We now describe the construction of a directed graph representing a coset of a CC. The procedure is most easily illustrated by the example introduced in Section 2 with 𝐻(x) = [1+x2, 1+x+x2] The corresponding scalar parity-check matrix H, given by Equation (11), is 11 𝟎𝟏 H= 𝟏𝟏 [

Let

11 01 11

11 01 11

… 11 01 11]

𝒔 = (𝑠0 , 𝑠1 , 𝑠2 , … , 𝑠𝑁−𝐾−1 )T denote the syndrome vector, and let 𝒆 = (𝑒0 , 𝑒1 , 𝑒2 , … , 𝑒𝑁−1 )

70

Computer Science & Information Technology (CS & IT)

denote the error vector. Each syndrome bit is obtained as the modulo-2 sum of the columns of H corresponding to positions where𝑒𝑖 = 1. Suppose first that 𝑠0 = 0. The two possible pairs of error bits that generate this syndrome bit are (𝑒0 , 𝑒1 ) = 00 or(𝑒0 , 𝑒1 ) =11 These error pairs determine not only the syndrome bit 𝑠0 , but also contribute to the subsequent syndrome bits 𝑠1 and 𝑠2 through the corresponding submatrix 01 𝜏=[ ] 11

shown in bold in H above. We refer to the linear combinations of the columns of 𝜏 as the statesof the syndrome trellis. For the pair (𝑒0 , 𝑒1 ) = 00, the resulting state is [00]T, whereas for(𝑒0 , 𝑒1 ) = 11,it is[10]T . Similarly, when𝑠0 = 1 the admissible error pairs become (𝑒0 , 𝑒1 ) = 01 or(𝑒0 , 𝑒1 ) = 10 yielding the states [11]T and [01]T, respectively. Thus, the syndrome trellis has two possible initial configurations, depending on the value of the syndrome bit. For 𝑠0 = 0, the trellis begins as

while for 𝑠0 = 1 it begins as

Consider now the i-thsyndrome bit 𝑠𝑖 .Its value depends not only on the corresponding pair of error bits (𝑒2𝑖 , 𝑒2𝑖+1 ), but also on the source statefrom which the trellis transition originates. The syndrome-trellis segments corresponding to 𝑠𝑖 = 0 for each of the four possible source states, are shown in Fig.1.

(a)

(b) (c) (d)

Figure 1. Syndrome trellis segments corresponding to 𝑠𝑖 = 0 andsource states: (a) [00]T, (b) [01]T , (c) [10]T and (d) [11]T.

Computer Science & Information Technology (CS & IT)

71

Similarly, the syndrome-trellis segments corresponding to 𝑠𝑖 = 1, for each of the four possible source states, are shownin Fig.2.

(a) (b) (c) (d) Figure 2. Syndrome trellis segments corresponding to 𝑠𝑖 = 1 and source states: (a) [00]T, (b) [01]T , (c) [10]T and (d) [11]T.

These segments define two building blocks ofthe syndrome trellis: one corresponds to 𝑠𝑖 = 0 and the other to 𝑠𝑖 = 1, as illustrated in Fig. 3

(a) (b) Figure 3. Syndrome-trellisbuilding blocks corresponding to: (a) 𝑠𝑖 = 0, (b) 𝑠𝑖 = 1. Since both building blocks share the same state space, they can be interconnected through their common states, allowing the syndrome trellis for any coset of the CC to be generated dynamically according to the syndrome values. The trellis always starts from the state [00…0] T and terminates at a unique state determined by the p tail syndrome bits. In the present example, p=2. Branch Metrics of Syndrome Trellises: The metric assigned to each trellis branch is simply its Hamming weight, namely the number of ones in the corresponding pair of error bits. Maximum-Likelihood Decoding of Syndrome Trellises: Decoding consists of searching the syndrome trellis for the minimum-Hamming-weight path. The procedure is as follows. 1. Initialization:At time 0, the state[00…0]Tis assigned metric 0, while all other states are assigned a sufficiently large positive value to prevent their selected during the search. 2. Branch Metric Assignment:Assigneach trellis branch a metric equal to the Hamming weight of the corresponding error vector segment. 3. State Metric Computation:For each state, compute the accumulated metric of the minimum-weight path terminating at that state.

72

Computer Science & Information Technology (CS & IT)

4. Survivor Selection: For each state, retain only the incoming branch belonging to the minimum-weight path determined in Step 3 and discard the others. The retained branch is referred to as the survivor branch. 5. Trace back: Starting from the terminal state, trace back through the survivor branches to the initial state, thereby reconstructing the minimum-weight error vector 𝒆̂.

5. DECRYPTION BY THE RECIPIENT The recipient possesses the public and private keys together with the received cipher text: ̃, 𝐻 ̂ , 𝑆, 𝑃, 𝒒(𝑥), 𝜀 , 𝒔} {𝐻, 𝐻 Decryption proceeds as follows. Step 1–Inversion of the Non singular transformation The inverse transformation 𝑆 −1 is applied to the received syndrome 𝒔̃ = 𝑆 −1 𝒔

(23)

Step 2–Unmasking The transformed syndrome can be written as ̃ )𝑃𝒆𝑇 = 𝐻 ′ 𝑃𝒆𝑇 ⊕ 𝐻 ̃ 𝑃𝒆𝑇 = 𝐻 ′ 𝑃𝒆𝑇 ⊕ 𝒍𝑖 ,𝒍𝑖 ∈ LS(ℒ) 𝒔̃ = (𝐻 ′ ⊕ 𝐻

(24)

̃ 𝑃has the same column span as 𝐻 ̃ , the masking contribution 𝒍𝑖 belongs to LS(ℒ). Since 𝐻 ̃ areknown to the recipient, the particular masking vector 𝒍𝑖 is unknown and may Although𝑃 and𝐻 assume any of the 2lvalues in LS(ℒ). Consequently, the set of candidate unmasked syndromes is 𝔇′ = {𝒔̃ ⊕ 𝒍𝑖 | 𝒍𝑖 ∈ LS(ℒ)}

(25)

Step 3–Division by the High-Memory Polynomial The memory of the CC is then reduced by dividing each candidate unmasked syndrome in 𝔇′ bythe high-memory polynomial 𝒒(𝑥), yielding the set of “low-memory” candidate syndromes 𝒔̃ ⊕ 𝒍

𝔇 = { 𝒒(𝒙)𝑖 | 𝒍𝑖 ∈ LS(ℒ)}

(26)

If no transmission errors have occurred and the correct masking was removed at Step 2,the division by 𝒒(𝑥)produceszero remainder. Step 4–Parallel Syndrome-Trellis Decoding The objective is to determine the most likely value of𝑃𝒆𝑇 by decoding all members of𝔇. Since each member of 𝔇 defines a distinct coset of the CC, it also defines a distinct syndrome trellis. because |𝔇| = 2l all candidate trellises may be decoded in parallel. The estimated error vector 𝑃𝒆̂𝑇 is then selected as the minimum-weight solution among the2ldecoded candidates.

Computer Science & Information Technology (CS & IT)

73

A key distinction exists between the candidate low-memory syndromes. If the correct masking vector was removed in Step 2, decoding yields an error vector satisfying wt(𝑃𝒆̂𝑇 ) ≈ 𝜀𝑁

(27)

In contrast, removing an incorrect masking vector effectively injects random errors into the syndrome, shifting the corresponding coset to an essentially arbitrary one. Consequently, the decoded error vectors𝑃𝒆̃𝑇 associated with incorrect candidates typically exhibit substantially larger weight, wt(𝑃𝒆̃𝑇 ) ≈ 𝛿 (28) where 𝛿 is the typical nearest-neighbor distance defined by Equation (19). This separation in Hamming weight enables reliable identification of the correct plaintext. Step 5 - Plaintext Recovery Since Pis a permutation matrix, 𝑃−1 = 𝑃𝑇 The plaintext is therefore recovered as 𝒆̂𝑇 = 𝑃𝑇 𝑃𝒆̂𝑇

(29)

If a CRC was appended to the plaintext during encryption, it is verified at this stage. If the CRC check fails, the next most likely decoded candidate is examined. The process continues until a valid plaintext is identified or all candidates have been exhausted, in which case retransmission may be requested. The complete encryption and decryption procedures are summarized in the block diagram shown in Fig. 4.

Figure 4. Encryption and Decryption block diagram.

74

Computer Science & Information Technology (CS & IT)

6. WORKED EXAMPLE Consider the CC defined by 𝐻(𝑥) = [1+x2, 1+x+x2] and select the high-memory polynomial 𝒒(𝑥) =1+x3 The resulting high-memory parity-check matrix is 𝐻 ′ (x) = [1+x2+x3+x5, 1+x+x2+x3+x4+x5] Assume aplaintext of length 16, with no CRC appended. The corresponding finite-dimensional matrix 𝐻 ′ is of size13×16 1100000000000000 0 11 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 11 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 11 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 11 1 0 0 0 0 0 0 1101111101110000 𝐻′= 0 0 1 1 0 1 1 1 1 1 0 1 1 1 0 0 0000110111110111 0000001101111101 0000000011011111 0000000000110111 0000000000001101 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1]

̃ by selecting its columns randomly from the linear We now construct the masking matrix𝐻 spanLS(ℒ), where ℒ is a set of l random vectors of length 13. Although ℒmay contain arbitrary random vectors of length 13, for simplicity we choose two alternating patterns with Hamming weight approximately equal to(N−K)/2, thereby ensuring statistical balance: ℒ = {(1010101010101)T, (0101010101010)T} The corresponding linear span is therefore LS(ℒ) = {0T, (0101010101010)T, (1010101010101)T,1T} ̃ is where 0 and 1denote the all-zero and all-one vectors, respectively. A dense masking matrix 𝐻 then formed by selecting each of its columns independently fromLS(ℒ)

Computer Science & Information Technology (CS & IT)

75

1001110010011101 0101001101100010 1001110010011101 0101001101100010 1001110010011101 0101001101100010 ̃ = 1001110010011101 . 𝐻 0101001101100010 1001110010011101 0101001101100010 1001110010011101 0101001101100010 [1 0 0 1 1 1 0 0 1 0 0 1 1 1 0 1]

The masked parity-check matrix is obtained as 0101110010011101 0010001101100010 0100000010011101 1010010001100010 1110000101011101 1000110000010010 ̃= 1 0 1 0 1 0 1 1 0 1 0 0 0 0 0 1 . 𝐻′ ⊕ 𝐻 0101111010010101 1001111111100000 0101001110111101 1001110010101010 0101001101101111 [1 0 0 1 1 1 0 0 1 0 0 1 1 1 1 0]

The resulting matrix is dense, with approximately half of its entries are equal to 1, while the row and column weights are concentrated around (N−K)/2 and N/2, respectively. Consequently, the original diagonal structure of His effectively concealed. Next, a random column permutation is applied using a 16×16 permutation matrix P 0000000000000100 0000000000000010 0000000010000000 0000000100000000 0000000001000000 0000000000100000 1000000000000000 0001000000000000 𝑃= 0000000000010000 0010000000000000 0000100000000000 0000010000000000 0100000000000000 0000000000001000 0000001000000000 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1]

Applying this permutation to the masked matrix produces

76

Computer Science & Information Technology (CS & IT) 0100010101111011 1 01 1 1 0 1 0 1 0 0 0 0 0 0 0 0 1 0 00 1 0 0 0 0 0 1 1 0 1 1 0 0 1 0 1 01 0 1 0 1 0 0 1 0 0 0 1 1 1 0 1 0 01 0 0 0 1 1 1 1 0000011001100100 ̃ )𝑃 = 1 0 1 1 0 0 0 0 1 1 0 0 0 1 0 1 (𝐻 ′ ⊕ 𝐻 1000010101111011 1011100101110100 1101110100011011 0100101101110100 1111101100001011 [0 1 0 0 0 1 1 1 0 1 1 1 1 1 0 0 ]

The permutation destroys the remaining positional ordering of the columns, further concealing the original convolutional structure.We then select a nonsingular matrix S, together with its inverse S-1 1100000000000 1111111111111 0110000000000 0111111111111 0011000000000 0011111111111 0001100000000 0001111111111 0000110000000 0000111111111 0000011000000 0000011111111 S= 0 0 0 0 0 0 1 1 0 0 0 0 0 , S-1= 0 0 0 0 0 0 1 1 1 1 1 1 1 0000000110000 0000000111111 0 0 0 0 0 0 0 0 1 10 0 0 0000000011111 0 0 0 0 0 0 0 0 0 11 0 0 0000000001111 0 0 0 0 0 0 0 0 0 01 1 0 0000000000111 0 0 0 0 0 0 0 0 0 00 1 1 0000000000011 [ 0 0 0 0 0 0 0 0 0 00 0 1 ] [0 0 0 0 0 0 0 0 0 0 0 0 1]

and construct the final public matrix 1111111111111011 1111111010011011 0110100010111111 0101111000101011 0111001011101011 1011011010100001 ̂ = 𝑆(𝐻 ′ ⊕ 𝐻 ̃ )𝑃 = 0 0 1 1 0 1 0 1 1 0 1 1 1 1 1 0 𝐻 0011110000001111 0110010001101111 1001011001101111 1011000001111111 1011110001110111 [0 1 0 0 0 1 1 1 0 1 1 1 1 1 0 0]

̂ is dense and exhibits strong random-like statistical properties, with no The resulting matrix 𝐻 visible diagonal or convolutional structure remaining. Since S is non singular and P is a ̃ has full permutation matrix, both transformations preserve matrix rank. Consequently, if 𝐻 ⊕ 𝐻 ̂ also has full rank. rank, then the public matrix 𝐻

Computer Science & Information Technology (CS & IT)

77

Encryption: Consider the plain text error vector 𝒆 = [0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0]

which is a unique coset leader due to its low weight and error distribution. The cipher text syndrome is computed as ̂ 𝒆𝑇 =[1000001000001]T. 𝒔 =𝐻 Decryption: Step1- Inverse Row Operations Apply the inverse row transformation to the received syndrome: 𝒔̃ = 𝑆 −1 𝒔 =[1000000111111]T Step 2 - Unmasking For the selected LS(ℒ), the set 𝔇′of candidate unmasked syndromes is 𝔇′ ={[1 0 0 0 0 0 0 1 1 1 1 1 1]T, [1 1 0 1 0 100101 0 1]T, [0 0 1 0 1 011010 1 0]T, [0 1 1 1 1 110000 0 0]T}

Step 3–Division by 𝒒(𝑥) The set 𝔇of low-memory candidate syndromes is obtained by dividing each member of 𝔇′ by 𝒒(𝑥) =1+x3. This yields four low-memory candidate syndromes, of which only one is guaranteed to be exactly divisible by𝒒(𝑥). 𝒔0=[0 00 0 0 00111]T, remainder1, 𝒔1=[0101111101]T, remainder 1, 𝒔2=[0010111010]T, 𝒔3= [0111000000]T. Thus, not all divisions yield zero remainder. Assuming no transmission errors have occurred, only candidates with zero remainder are consistent with exact division by 𝒒(𝑥)and may therefore be retained for syndrome-trellis decoding. In the general case, however, all candidates must be considered, since transmission errors may perturb the syndrome and produce nonzero remainders even for the correct masking vector. Step 4- Parallel Syndrome-Trellis Decoding The candidate syndrome trellises are decoded in parallel to determine the most likely error vector𝑃𝒆̂𝑇 . In this example, the CC has a free distance dfree = 5, allowing reliable correction of up to two errors within a sliding window of six bits. If three or more errors occur within a window, decoding may fail. The syndrome trellis corresponding to𝒔3=[0 1 1 10 0 0 0 0 0]Tis illustrated in Fig. 5. Since p = 2, the final two syndrome bits uniquely determine the terminal state of the syndrome trellis.

78

Computer Science & Information Technology (CS & IT)

Figure 5. Syndrome trellis corresponding to𝒔3= [0 1 1 10 000 0 0]T

Fig. 6showsthe trellis of Fig. 5after enforcing unique initial and terminal states. The highlighted path corresponds to the minimum-weight path, yielding 𝑃𝒆̂𝑇 = [0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0]T The selected path has Hamming weight 1. By contrast, the minimum-weight paths in all remaining candidate syndrome trellises have weights greater than 1.

Figure 6. Minimum-weight path through the syndrome trellis of Fig. 5

Step 5- Plaintext Recovery The plaintext is recovered by applying the inverse permutation: 𝒆̂𝑇 = 𝑃𝑇 𝑃𝒆̂𝑇 = [0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0]T The recovered vector matches original plaintext.

7. CRYPTANALYSIS RESISTANCE AND PERFORMANCE Threat Model: We consider a passive adversary (eavesdropper) who has full knowledge of the ̂ , the encryption algorithm, and all system parameters except the private key. The public key 𝐻 adversary observes the intercepted ciphertext (syndrome) 𝒔 and seeks either to recover the plaintext error vector 𝒆 or to recover the hidden structure of the public key.Direct recovery of 𝒆 ̂ is computationally infeasible because the corresponding syndrome defines a coset by inverting 𝐻 containing an astronomically large number of candidate error vectors. ̂ is computationally We further assume that, for the selected parameters, the public matrix 𝐻 indistinguishable from the parity-check matrix of a random binary linear code. As in the Classic McEliece cryptosystem, this assumption is not supported by a formal proof but by the absence of any known efficient structural attacks against appropriately chosen parameter sets. Under these assumptions, the adversary is effectively limited to three classes of attacks:

Computer Science & Information Technology (CS & IT)

79

Plaintext-recovery attacks, which attempt to recover the transmitted error vector by solving the syndrome decoding problem. The complexity of these attacks grows exponentially with the error weight, which is itself unknown in the proposed framework because only the error probability ε is public. Structure-recovery attacks, which attempt to recover the hidden structured matrix H, together with the masking and transformation operations, from the public matrix ̂ can be distinguished from Distinguishing attacks, whose objective is to determine whether 𝐻 the parity-check matrix of a random linear code. As in the Classic McEliece cryptosystem, this assumption is not supported by a formal proof but rather by the absence of any known efficient structural attack against appropriately chosen parameter sets. The second and third attack classes are hindered by three complementary obfuscation mechanisms: •

• •

Dense masking. The memory of the CCis substantially increased by multiplication with a ̃ , whose columns are statistically high-degree polynomial, followed by masking with 𝐻 balanced random vectors with Hamming weight close to (𝑁 − 𝐾)/2. This process effectively conceals the underlying algebraic structure. Random row operations. A nonsingular matrix 𝑆randomizes the basis of the masked paritycheck matrix through invertible linear combinations of its rows. Random column permutation. A permutation matrix𝑃 uniformly permutes the coordinate positions, eliminating any remaining positional or diagonal patterns.

Additional analytical evidence that the resulting public matrix exhibits the statistical properties expected of a random full-rank (N,K) binary code is presented in [8]. Although the syndrome 𝒔 contains no explicitly injected errors, the decryption problem associated with the proposed masked parity-check matrices still appears to reduce to the classical syndrome decoding problem, which is NP-hard. Daniel J. Bernstein [17] analyzed quantum speedups for information-set decoding (ISD) attacks. His analysis addresses the decoding problem itself, independently of whether the public code is represented by a generator matrix or a parity-check matrix. Consequently, provided that ISD remains the best-known generic attack against the proposed framework, Bernstein's complexity estimates apply directly using the effective code parameters defined by the public parity-check matrix. ̂ anda In the proposed framework, given a finite-dimensional masked parity-check matrix 𝐻 syndrome s, and assuming that exactly 𝜀𝑁 errors occurred, the attacker must recover an error vector 𝒆 satisfying ̂ 𝒆𝑇 = s, wt(𝒆) = 𝜀𝑁 𝐻 (30) The cryptanalytic complexity is estimated using the best-known information-set decoding (ISD) algorithms, including those of Prange, Lee–Brickell, and BJMM [14–16], which measure security primarily in terms of bit operations and typically do not account for memory requirements or large-scale parallelization. As with other code-based cryptosystems, the proposed construction relies on sufficiently large parameter sets; smaller parameters may permit exhaustive search or

80

Computer Science & Information Technology (CS & IT)

structural attacks and are therefore not intended to provide cryptographic security. Accordingly, we consider only parameter ranges for which generic ISD attacks are believed to dominate. The analyses in [14–16] generally assume that the Hamming weight wt(𝒆) is known a priori. In the proposed framework, however, the exact number of errors is not fixed but is determined probabilistically by the publicly known error probability ε. This additional uncertainty further complicates generic decoding attacks. Moreover, since the error vector 𝒆 is generated as a statistically random binary vector, it contains no intentional algebraic or combinatorial structure that could be exploited to reduce decoding complexity. In the context of quantum computing, ISD complexity estimates are typically derived from classical attack models. Although quantum algorithms such as Grover's search algorithm [17] provide a quadratic speedup, no exponential quantum speedup for ISD is currently known. Consequently, code-based cryptography generally assumes that ISD, with at most quadratic quantum acceleration, remains the most efficient generic attack. To compare the proposed framework with other code-based cryptosystems, we adopt the complexity measure of [17]. Specifically, for a classical attack on an (N,K,t) code, the ISD complexity, denoted by CISD, is proportional to the number of iterations required by the ISD algorithm. In the present work, the classical ISD complexity is approximated by 𝑁 ( ) 𝐾 CISD ~ 𝑁−𝑡 0.29( ) 𝐾

(31)

For quantum computing, the corresponding complexity, denoted by CQISD, becomes 𝑁 ( ) 𝐾 𝑁−𝑡 0.29( ) 𝐾

CQISD ~√

(32)

Each quantum iteration requires a function evaluation requiring O(N3) qubit operations. We now apply Equation (31) to estimate the ISD complexity of a Goppa-code-based cryptosystem, using the widely adopted parameter set (N, K,t) = (8192,6528,128) as a reference, and compare it with the proposed MPC framework at a comparable key size(~50 Mbits). Publickey size is measured as the total number of stored bits required to represent the dense binary parity-check matrix without compression. Although the parameter ε is publicly known, the actual number of errors in the plaintext vector 𝒆 is not revealed. For a conservative comparison, however, we assume that the effective number of errors in the MPC scheme is fixed at εN. Substituting the parameters of the (8192, 6528, 128) Goppa code into Equation (31) yields CISD(Goppa) ≈

8192 ) 6528 84 8192−128 ≈2.74×10 0.29( ) 6528 (

(33)

For an MPCconstruction with a comparable key size (~35 Mbits), we may choose 𝑁 =8200 and 𝑁 − 𝐾= 4300. Selecting the degree-14 CC polynomials 𝒑0 (𝑥)= 55751, 𝒑1 (𝑥)= 66323,

(34)

Computer Science & Information Technology (CS & IT)

81

expressed in octal form, yields a code with dfree= 20. Choosing 𝒒(𝑥)of degree 186givesp + q = 200. For these parameters, selecting ε = 0.07producesapproximately 574 errors in an8200-bit error vector.This error rate lieswell within the correction capability of the selected CC, which corrects up to 9 errors in a 30-bit window, making decoding failures highly unlikely. By contrast, incorrectly unmasked candidates are decoded, asdiscussed in Section 2, to vectors lying at a Hamming distance of approximately 0.11×8200 ≈ 902 from the received vector. This distance is substantially larger than the expected 574-error radius of the valid plaintext, placing such candidates well outside the decoder's effective decoding radius. This separation enables reliable discrimination between the correct plaintext and incorrect candidates. Consequently, the valid plaintext is identified with overwhelming probability, while incorrect candidates are systematically rejected. Under these assumptions, the estimated ISD complexity of the proposed MPC cryptosystem is CISD(MPC) ≈

8200 𝑁 ( ) ( ) 4300 𝐾 196 = 𝑁−𝜀𝑁 8200−574 ≈1.44×10 (35) 0.29( ) 0.29( ) 𝐾 4300

This corresponds to an estimated increase in ISD attack complexity by a factor of approximately 𝐶ISD (MPC) ≈0.52×10112≈2371 𝐶ISD (Goppa)

relative to the Niederreiter and Classic McEliece parameter set considered in Equation (33). For quantum ISD (QISD),the improvement is approximately 2185, consistent with the square-root speedup provided by Grover-typequantum search. The probability of decoding failure, and hence the need for retransmission, can also be estimated directly. For example, the decoder fails if more than 9 errors occur within a 30-bit window. At an error probability of ε = 0.07, the probability of this event is approximately 1.6×10-6 Over 274 windows, corresponding to a ciphertext length of approximately 8,200 bits, the probability of successful decoding is therefore (1 - 1.6×10-6)274≈ 0.9995 This demonstrates that the proposed MPC cryptosystem maintains a very high probability of successful decryption even for ciphertexts spanning thousands of bits under fully random error injection. We note that low-rate public codes can correct a larger fraction of errors than high-rate codes. However, their increased redundancy may adversely affect both efficiency and security in codebased cryptosystems, as indicated by (31). When K≪N, the large number of parity constraints, N−K, may be exploited to accelerate decoding attacks [18]. Consequently, the code rate is an important design parameter in selecting the underlying CC. In practice, a code rate close to 1/2, i.e., N−K≈K, provides a good balance between security and implementation efficiency.

82

Computer Science & Information Technology (CS & IT)

Finally, we examine the computational complexity of decryption. Schöffel et al. [19] presented a hardware/software co-design implementation of the Hamming Quasi-Cyclic (HQC) cryptosystem for IoT edge devices, demonstrating that code-based cryptography can provide a practical alternative to lattice-based schemes in resource-constrained environments. Similarly, [20] introduced an FPGA-based hardware accelerator for HQC post-quantum cryptography, implementing key generation, encapsulation, and decapsulation with substantial performance gains through tight integration with a RISC-V core. In the proposed MPC cryptosystem, the dominant contribution to the decryption complexity arises from syndrome-trellis decoding. Other operations, such as polynomial division and syndrome unmasking, are performed on the entire ciphertext but incur negligible computational cost compared with the per-bit processing carried out by the syndrome-trellis decoders. To quantify the decoding complexity, we evaluate the number of Add–Compare–Select (ACS) operations required per decrypted ciphertext bit. These operations are highly amenable to efficient hardware and software implementation, enabling scalable high-throughput realizations. Assume that the MPC cryptosystem employs a CC with memory p together with a rank-l masking matrix. The decryption process then requires 2l parallel syndrome-trellis decoders, each operating with 2p ACS units per bit. Consequently, the total ACS complexity per ciphertext bit is2l+p. This complexity is independent of the plaintext length and therefore scales linearly with the ciphertext size, ensuring predictable performance for arbitrarily long messages. For example, using the CC defined by (34) with l=6 and memory p=14, the total number of ACS operations per decrypted ciphertext bit is 2l+p = 220 which remains well within the capabilities of modern commercial processors and dedicated hardware accelerators, including those integrated into contemporary mobile devices.

8. CONCLUSION This work introduced a novel post-quantum cryptographic framework based on high-memory masked parity-check matrices of convolutional codes, addressing several inherent limitations of traditional block-code-based cryptosystems. Security is enhanced through random error injection into the plaintext, combined with dense random masking and invertible linear transformations that produce dense, random-like parity-check matrices, thereby mitigating vulnerabilities associated with low-density or structurally distinguishable codes. A principal novelty of this work is the introduction of directed-graph decoders as the practical decryption mechanism for masked code-based crypto systems. Decoding is performed by an array of syndrome trellises, dynamically constructed by the legitimate recipient from predefined building blocks. While authorized users resolve the resulting decryption ambiguity in polynomial time, an adversary appears to be limited to exponential-time decoding attacks. The analysis presented in this work indicates that, for the parameter sets considered, the proposed framework can achieve substantially higher estimated security margins than Niederreiter or Classic McEliece, with estimated ISD attack-complexity improvements exceeding factors of 2100against quantum adversaries and 2200against classical adversaries, while maintaining practical decoding complexity for legitimate users.

Computer Science & Information Technology (CS & IT)

83

Beyond its security properties, the proposed construction supports arbitrary plaintext lengths, linear overall decoding complexity with message length, and efficient high-throughput implementation in both software and hardware. Collectively, these characteristics make the proposed MPC framework a promising candidate for robust, scalable, and practically deployable post-quantum public-key cryptography.

REFERENCES [1]

McEliece, R.J., (1978) “A Public-Key Cryptosystem Based on Algebraic Coding Theory”, DSN Progress Report. [2] Bernstein, D.J.; Lange, T.; Peters, C., (2008) “Attacking and defending the McEliece cryptosystem”, Post-Quantum Cryptography, pp. 31–46. [3] Misoczki, R.;Tillich, J.-P.;Sendrier, N.; Barreto, P.S.L.M., (2013) “New McEliece Variants from Moderate Density Parity-Check Codes”, Proceedings of the IEEE International Symposium on Information Theory (ISIT), pp. 2069–2073. [4] National Institute of Standards and Technology (NIST), “Post-Quantum Cryptography Standardization, (2023),https://csrc.nist.gov [5] Weger, V.;Barelli, E.;Beullens, W.;Couvreur, A.; Debris-Alazard, T.; Galvez, L.; Gauthier-Umaña, V.;Misoczki, R.;Puchinger, S.;Sárközy, G.;Sendrier, N., (2022) “A Survey on Code-Based Cryptography”, IACR Cryptology ePrint Archive, Report 2022/005. Updated July 2024, https://eprint.iacr.org/2022/005 [6] Cayrel, P.L.;Gaborit, P.;Misoczki, R.;Puchinger, S.;Weger, V. (eds.), (2024) Code-Based Cryptography, Proceedings of CBCrypto 2024, Vol. 14699, Springer, Cham. [7] Ariel, M., (2025) “High-Memory Masked Convolutional Codes for Post-Quantum Cryptography”, CS & IT Conference Proceedings, vol. 15, no. 17, pp. 1–22, 2025. [8] Ariel, M., (2025) “Decryption Through Polynomial Ambiguity: Noise-Enhanced High-Memory Convolutional Codes for Post-Quantum Cryptography”, International Journal on Cryptography and Information Security (IJCIS), Vol. 15, Nos.1-4, Dec. 2025, pp. 1–23. [9] Baldi, M.;Chiaraluce, F.;Garello, R.;Mininni, F., (2007) “Quasi-cyclic Low-Density Parity-Check Codes in the McEliece Cryptosystem”, Proceedings of the IEEE International Conference on Communications (ICC), pp. 951–956. [10] Niederreiter, H., (1986) “Knapsack-Type Cryptosystems and Algebraic Coding Theory”, Problems of Control and Information Theory, 15, pp. 159–166. [11] Canteaut, A.;Sendrier, N., (1998) “Cryptanalysis of the Original McEliece Cryptosystem”, ASIACRYPT '98, LNCS 1514, pp. 187-199. [12] Ariel,M.;SnydersJ., (1998) “Error-Trellises for Convolutional Codes – Part I: Construction”, IEEE Transactions on Communications, Vol. 46, No. 12, pp. 1592–1601. [13] Ariel, M.;Meidan, R., (1999) “Soft-Decision Syndrome-Based Decoder for Convolutional Codes”, U.S. Patent 6,009,552 [14] Becker, A.;Joux, A.; May, A.; Meurer, A., (2012) “Decoding Random Binary Linear Codes in 2^{n/20}”, Advances in Cryptology – EUROCRYPT 2012, Lecture Notes in Computer Science Vol. 7237, pp. 520–536. [15] Prange, E., (1962) “The Use of Information Sets in Decoding Cyclic Codes”, IRE Transactions on Information Theory, Vol. 8, No. 5, pp. 5–9. [16] Lee, P.J.; Brickell, E.F., (1988) “An Observation on the Security of McEliece’s Public-Key Cryptosystem”, Advances in Cryptology – EUROCRYPT 88, LNCS Vol. 330, pp. 275–280. [17] Bernstein, D.J., (2010) “Grover vs. McEliece”, in N. Sendrier(Ed.), Post-Quantum Cryptography, PQCrypto 2010, Vol. 6061, pp. 73–80. Springer, Heidelberg. [18] Carrier, N.;Espitau, T.;Gaborit, P.;Géraud, A.;Kachigar, G., (2024) “Reduction from Sparse LPN to LPN, Dual Attack 3.0”, Advances in Cryptology – EUROCRYPT 2024, Vol. 14655, pp. 735–765. Springer, Cham. [19] Schöffel, P.; Feldmann, A.;Wehn, N., “Code-Based Cryptography in IoT: A HW/SW Co-Design of HQC”, Proceedings of the Design, Automation and Test in Europe Conference(2023), pp. 368–373. [20] Di Matteo, A.;Marrone, M.; Valenzano, A., (2025) “TYRCA: A RISC-V Tightly Coupled Accelerator for Code-Based Cryptography”, Proceedings of the 62nd Design Automation Conference (DAC 2025), pp. 1–6.

84

Computer Science & Information Technology (CS & IT)

AUTHOR Meir Ariel received the B.Sc. and M.Sc. degrees (with honors) in Electrical Engineering and the Ph.D. degree in Algebraic Group Theory from Tel Aviv University, Israel. He has more than 30 years of research and development experience in signal processing, wireless communications, information theory, cryptography, and space technologies, holding leadership positions in both industry and the public sector. From 1999 to 2013, he served as Chief Executive Officer of several technology companies specializing in computer vision, Voice over IP (VoIP), and financial technologies (FinTech). Since 2013, he has been the Director General of the Herzliya Science Center. In 2018, he founded the Space Engineering Center at Tel Aviv University, where he currently serves as its Head. Under his leadership, the Center has developed and launched 24 nanosatellites for scientific research and experimental space communications. He holds 15 patents in information theory and signal processing and has served on national advisory committees in science and education. His honors include the Marco Polo Society Award (2018) and recognition by Israel's Ministry of Science and Technology as one of the country's 60 pioneering inventors (2016) .

©2026 By AIRCC Publishing Corporation. This article is published under the Creative Commons Attribution (CC BY) license.

Related documents

• Syndrome Trellis Decryption in Post-Quantum Cryptography#1491268
• Quantum Algorithm for Elliptic Curve Discrete Logarithms with Space-Efficient Point Addition#973273
• Elevator Codes: Concatenation for resource-efficient quantum memory under biased noise#1050804
• Magic Secret Sharing: Threshold Control of Quantum Computational Power via GHZ Entanglement#1050878
• Quantum codes are quantized codes: Stabilizer codes from quantization over finite fields#1215703