Information-Set Decoding Attacks

Information-set decoding (ISD) is the fastest known generic attack on a random linear code, and its cost is what sets parameters for code-based cryptography. Each attack repeatedly guesses an information set, hoping the error is distributed favorably with respect to it, and the variants differ in how much work they do per iteration in exchange for a better success probability: Prange's algorithm does the least, Lee-Brickell and Leon allow a few errors in the information set, Stern and its DOOM variant collide partial sums across a split, and MMT and BJMM apply representation techniques to the same collision idea.

These functions are also useful outside cryptography. Solving the syndrome decoding problem is exactly what a decoder for an arbitrary linear code must do, and running an attack against a code whose distance is unknown yields an upper bound on that distance; see Minimum distance.

required_ISD_iterations estimates the number of iterations needed for a target success probability, which is the usual way to convert an attack into a security estimate.

CodingTheory.BJMM_attack — Method

BJMM_attack(
    C::AbstractLinearCode,
    target_w::Int64;
    w_recv,
    p,
    ϵ1,
    l1,
    l2,
    num_find,
    max_iters,
    unroll
) -> Any

source

CodingTheory.Canteaut_Chabaud_attack — Method

Canteaut_Chabaud_attack(
    C::AbstractLinearCode,
    target_w::Int64;
    w_recv,
    p,
    l,
    num_find,
    max_iters
) -> Set{Vector{Int64}}

Executes the Canteaut-Chabaud variant of Information Set Decoding (ISD). This algorithm modifies Stern's approach by replacing the O(n^3) full Gaussian elimination at each iteration with an O(n^2) single-column swap and pivot update. It reconstructs the full matrix entirely only after a set number of fast iterations.

Notes

The algorithm supports two modes:

Minimum Distance Search (Default): If w_recv is the all-zero vector, searches the nullspace for a codeword of weight target_w.
Syndrome Decoding: If w_recv is provided, searches for an error vector of weight target_w to correct the received word.

Arguments

C::AbstractLinearCode: The linear block code.
target_w::Int: The target Hamming weight of the codeword or error vector.

Keyword arguments

w_recv::Vector{Int} = zeros(Int, C.n): The received word.
p::Int = 2: The number of errors assumed to be in each half of the Information Set.
l::Int = (Int(order(C.F)) == 2 ? 12 : 3): The size of the collision window.
num_find::Int = 1: The number of valid vectors to find before terminating.
max_iters::Int = 10000: Maximum random permutations/pivot updates to attempt.

Returns

Set{Vector{Int}}: A set containing the discovered vectors. Returns an empty set if max_iters is reached without finding matches.

source

CodingTheory.DOOM_Stern_attack — Method

DOOM_Stern_attack(
    C::AbstractLinearCode,
    target_w::Int64;
    w_recv,
    p,
    l,
    num_find,
    max_iters,
    unroll
) -> Union{Set{Vector{Int64}}, Set{Tuple{Int64, Vector{Int64}}}}

Executes Sendrier's DOOM (Decoding One Out of Many) algorithm for full Information Set Decoding attacks. Simultaneously targets all valid error permutations of weight w-1 by checking all columns of the parity-check matrix in parallel.

source

CodingTheory.Gilbert_Varshamov_bound — Method

Gilbert_Varshamov_bound(
    n::Int64,
    k::Int64,
    q::Int64
) -> Int64

Return the Gilbert–Varshamov distance bound for a linear $[n, k]$ code over $\mathrm{GF}(q)$.

source

CodingTheory.Lee_Brickell_attack — Method

Lee_Brickell_attack(
    C::AbstractLinearCode,
    target_w::Int64;
    w_recv,
    p,
    num_find,
    max_iters
) -> Set{Vector{Int64}}

Executes the Lee-Brickell Information Set Decoding (ISD) algorithm. Automatically strips the structural objects and routes to optimized binary or nonbinary engines based on the code's base field.

Notes

The algorithm supports two modes:

Minimum Distance Search (Default): If w_recv is the all-zero vector, searches the nullspace for a codeword of weight target_w by enforcing exactly p non-zero elements in the Information Set.
Syndrome Decoding: If w_recv is provided, searches for an error vector of weight target_w to correct the received word.

Arguments

C::AbstractLinearCode: The linear block code.
target_w::Int: The target Hamming weight of the codeword or error vector.

Keyword arguments

w_recv::Vector{Int} = zeros(Int, C.n): The received word.
p::Int = 2: The number of errors assumed to be in the Information Set.
num_find::Int = 1: The number of valid vectors to find before terminating.
max_iters::Int = 10000: Maximum random permutations to attempt.

Returns

Set{Vector{Int}}: A set containing the discovered vectors. Returns an empty set if max_iters is reached without finding matches.

source

CodingTheory.Leon_attack — Method

Leon_attack(
    C::AbstractLinearCode,
    target_w::Int64;
    w_recv,
    p,
    l,
    num_find,
    max_iters
) -> Set{Vector{Int64}}

Executes Leon's Information Set Decoding (ISD) algorithm. Leon's algorithm improves upon Lee-Brickell by enforcing a strict filter: it demands that exactly 0 errors occur within a designated window of length l. This aggressively prunes the search tree before evaluating the full parity tail.

Notes

The algorithm supports two modes:

Minimum Distance Search (Default): If w_recv is the all-zero vector, searches the nullspace for a codeword of weight target_w.
Syndrome Decoding: If w_recv is provided, searches for an error vector of weight target_w to correct the received word.

Arguments

C::AbstractLinearCode: The linear block code.
target_w::Int: The target Hamming weight of the codeword or error vector.

Keyword arguments

w_recv::Vector{Int} = zeros(Int, C.n): The received word.
p::Int = 2: The number of errors assumed to be in the Information Set.
l::Int = (Int(order(C.F)) == 2 ? 12 : 3): The size of the strict zero-error window.
num_find::Int = 1: The number of valid vectors to find before terminating.
max_iters::Int = 10000: Maximum random permutations to attempt.

Returns

Set{Vector{Int}}: A set containing the discovered vectors. Returns an empty set if max_iters is reached without finding matches.

source

CodingTheory.MMT_attack — Method

MMT_attack(
    C::AbstractLinearCode,
    target_w::Int64;
    w_recv,
    p,
    l1,
    l2,
    num_find,
    max_iters,
    unroll
) -> Any

Executes the May-Meurer-Thomae (MMT) Second Generation 4-way merge tree algorithm for full Information Set Decoding attacks.

source

CodingTheory.Prange_attack — Method

Prange_attack(
    C::AbstractLinearCode,
    target_w::Int64;
    w_recv,
    num_find,
    max_iters
) -> Set{Vector{Int64}}

Executes Prange's foundational Information Set Decoding (ISD) algorithm.

Notes

The algorithm supports two modes:

Minimum Distance Search (Default): If w_recv is the all-zero vector, the algorithm evaluates the rows of the systematized matrix (p=1) to find codewords of weight target_w.
Syndrome Decoding: If w_recv is provided, the algorithm assumes no errors exist in the information set (p=0) and checks if the parity syndrome has weight target_w.

Arguments

C::AbstractLinearCode: The linear block code.
target_w::Int: The target Hamming weight of the codeword or error vector.

Keyword arguments

w_recv::Vector{Int} = zeros(Int, C.n): The received word.
num_find::Int = 1: The number of valid vectors to find before terminating.
max_iters::Int = 10000: Maximum random permutations to attempt.

Returns

Set{Vector{Int}}: A set containing the discovered vectors. Returns an empty set if max_iters is reached without finding matches.

source

CodingTheory.Stern_attack — Method

Stern_attack(
    C::AbstractLinearCode,
    target_w::Int64;
    w_recv,
    p,
    l,
    num_find,
    max_iters,
    unroll
) -> Any

Executes Stern's Information Set Decoding (ISD) algorithm for linear block codes. This function incorporate the most valuable parts of Dumer’s refinement.

Notes

The algorithm supports two modes:

Minimum Distance Search (Default): If w_recv is the all-zero vector, searches the nullspace for a codeword of weight target_w.
Syndrome Decoding (Error Correction): If w_recv is provided, searches for an error vector of weight target_w to correct the received word.

Arguments

C::AbstractLinearCode: The linear block code over GF(q).
target_w::Int: The target Hamming weight of the codeword or error vector.

Keyword arguments

w_recv::Vector{Int} = zeros(Int, C.n): The received word. Defaults to the all-zero vector.
p::Int = 2: The search weight per half of the Information Set. Keep this small, as the search space grows exponentially with the field size q.
l::Int = 12 or 3: The size of the collision window. For binary codes, l = 12 perfectly balances the hash map size against the false-positive collision rate. The general case defaults to a much smaller value than the binary version (l = 3) because the number of possible window states is q^l. A large l will stall the hash map generation.
num_find::Int = 1: The number of valid vectors to find before terminating.
max_iters::Int = 10000: The maximum number of random permutations to attempt.

Returns

Set{Vector{Int}}: A set containing the discovered vectors of weight target_w. Returns an empty set if no vectors are found within max_iters.

source

CodingTheory.required_ISD_iterations — Method

required_ISD_iterations(
    alg::Symbol,
    n::Int64,
    k::Int64,
    w::Int64,
    target_success_rate::Float64;
    p,
    l,
    l1,
    l2,
    ϵ1
) -> Int64

Return the number of matrix permutations required to recover a specified weight-w error vector at target_success_rate, using log-domain hypergeometric probabilities.

source

CodingTheory.syndrome_decode — Method

syndrome_decode(
    C::AbstractLinearCode,
    w_recv::Vector{Int64},
    target_w::Int64;
    alg,
    confidence,
    p,
    l,
    l1,
    l2,
    ϵ1,
    num_find,
    unroll,
    verbose
) -> Any

The master Information Set Decoding attack dispatcher. Automatically calculates the required iteration budget, and seamlessly routes the attack to the hardware-accelerated engines based on the code's base field.

If unroll=true (default), the dispatcher routes algorithms equipped with leaf-node loop unrolling (Stern, DOOM, MMT, BJMM) to their highly specialized "overdrive" engines to maximize CPU cache utilization and memory bandwidth.

Notes

The supported algorithms are:

1st Gen: :Prange, :LeeBrickell, :Leon, :Stern, :CanteautChabaud
DOOM: :DOOM (Sendrier's multi-target optimization)
2nd Gen: :MMT (4-way merge tree)
3rd Gen: :BJMM (4-way merge tree with ϵ-overlap)

source