Solving Hidden Number Problems Without Lattices

Quick Summary

We demonstrate practical alternatives to solving HNPs without constructing lattices.

This is part of our series on Practical Hidden Number Problems for Programmers:

*These links are paywalled. (It’s how I’ll afford grad school lol)

Part 1: Quantum Computing and Intro to Hidden Number Problems

Part 2: Increasing Lattice Volume for Improved HNP Attacks

Part 3: Hidden Number Problems with Multiple Noise Holes

Part 4: Hidden Number Problems with Chosen Multipliers

Part 5: Hidden Number Problems with Chosen Errors

Part 6 (we are here): Solving Hidden Number Problems Without Lattices

1.0 Introduction

The term hidden number problem refers to the challenge of recovering a secret hidden number given partial knowledge of its linear relations (Surin & Cohney, 2023).

Linear Hidden Number Problem

(Boneh & Venkatesan, 1996) introduce the linear hidden number problem and assert that lattice reduction recovers the unknown key ( x ) in polynomial time despite the noise term ( β i ) when provided known multipliers (t i ) alongside known observations (a i ).

Solving HNPs involves finding ‘good lifts’ from a finite field to an integer ring

However, non-lattice methods for solving HNPs exist, and all rely on a key insight from Part 5: HNP solvers simply find a suitable integer lift.

2.0 Solvers for Different Situations

Here’s a list of lattice alternatives and where they thrive:

ACGS algorithm (covered in Part 4) - use this to solve HNPs where you choose multipliers. However, you also need an oracle or some hand-wavy way to correctly predict LSBs of your multiples. Fourier analysis - use this when you can collect millions of samples. It works great even with lots of errors. Gaudry-Schost collision finding - useful for Hidden Number Problems where the field structure is not entirely on a circle (like in Infrastructure-based HNPs or Endomorphism based HNPs on elliptic curves). Roll your own lifter - whatever ‘lifting trick’ you can muster will work better than lattices or ACGS. All HNPs are unique lol. Bruteforce search - this works rather well when the field characteristic prime is small.

2.1 Writing HNP Solvers from First Principles

Most HNP solvers depend on finding a good integer lift and lattices are just one of many ways to get there. If you’re confident enough, you can totally improvise.

This section demonstrates a practical ‘roll-your-own-lifter’ approach to hidden number problems.

2.1.1 Toy Example: Hidden Number Problem with Equal, Negative Multipliers

Say we have a linear hidden number problem of the form below:

Premise for our toy HNP

where ( x, z i ) are the unknown key and noise terms, (b i ) is the known observation and (t i ,a i ) are known multipliers for the secret and the noise.

Assume the known multipliers (t i ,a i ) negate each other, guiding us to our toy example, the Hidden Number Problem with Equal, Negative Multipliers:

Multipliers are equal but negatives of each other

2.1.1 Understanding our Problem

Equal but negative multipliers for the unknown secret and noise is a bizarre HNP special case. We can rewrite our linear system as:

Rewriting linear system to account for bizzare info about multipliers

This essentially factors into the HNP form:

Factored HNP form

We know our solver’s objective is to find a good lift. So we can rewrite our HNP in its lifted form:

HNP lifted from a finite field to the ring of integers

Finally, the equation in terms of our target becomes:

Lifted HNP in terms of the target x

What does this reveal to us? Two things:

The value of x is a known constant plus unknown z modulo p: We know how a, b and z contribute to the value of x If z is small (like in a lattice-based approach), then we can approximate x as: x is pretty close to our known constant for small z

Now we know, each equation reveals that x is close to z:

Modular information revealed in a single equation

Therefore, each equation gives an interval constraint on x of the form:

Interval constraints revealed by each equation

Now we know what to do (and we don’t need lattices lol):

Lift each known constant to an integer: Lift constant to integers Find x that lies in many overlapping intervals: Search for x in overlapping intervals # Recover x from equations: # b_i = -a_i x + a_i z_i mod p # => c_i = -b_i * a_i^{-1} mod p ≈ x + z_i, |z_i| <= Z def modinv(a, p): return pow(a, -1, p) def compute_c_list(a_list, b_list, p): c_list = [] for a, b in zip(a_list, b_list): inv_a = modinv(a, p) c = (-b * inv_a) % p c_list.append(c) return c_list def recover_x(c_list, p, Z): """ Find densest interval of width 2Z on circle mod p """ c = sorted(c_list) c_ext = c + [x + p for x in c] best_count = 0 best_center = 0 j = 0 n = len(c) for i in range(n): while j < i + n and c_ext[j] - c_ext[i] <= 2 * Z: j += 1 count = j - i if count > best_count: best_count = count best_center = (c_ext[i] + c_ext[j - 1]) // 2 return best_center % p, best_count def circular_distance(a, b, p): return min((a - b) % p, (b - a) % p) def refine_x(x, c_list, p, Z): """ Refine estimate by averaging consistent points """ good = [] for ci in c_list: if circular_distance(ci, x, p) <= Z: good.append(ci) if not good: return x # unwrap around x lifted = [] for ci in good: if ci > x + p // 2: lifted.append(ci - p) elif ci < x - p // 2: lifted.append(ci + p) else: lifted.append(ci) return (sum(lifted) // len(lifted)) % p def solve(a_list, b_list, p, Z): c_list = compute_c_list(a_list, b_list, p) x_est, count = recover_x(c_list, p, Z) x_refined = refine_x(x_est, c_list, p, Z) return { "x_estimate": x_est, "x_refined": x_refined, "support": count, "total_equations": len(c_list), } if __name__ == "__main__": import random # Example parameters p = 13441 Z = 300 n = 60 # Secret x_true = random.randrange(p) a_list = [] b_list = [] for _ in range(n): a = random.randrange(1, p) z = random.randint(-Z, Z) b = (-a * x_true + a * z) % p a_list.append(a) b_list.append(b) result = solve(a_list, b_list, p, Z) print("True x:", x_true) print("Estimate:", result["x_estimate"]) print("Refined:", result["x_refined"]) print("Support:", result["support"], "/", result["total_equations"])

2.1.2 Toy Example: Bruteforcing Hidden Number Problem Modulo Small Primes

Say we have a HNP of the form:

HNP instance

where α is the unknown secret, t is the known secret multiplier, ψ k is an unknown constant noise term (it’s shared across all observations), d is the known noise term multiplier, a is the known observation, p is a known small prime.

We can build a p*p table and test for ( α ,ψ k ) pairs that satisfy the HNP. The correct pairs satisfy all equations. We bound the ψ k.

A bruteforcer in C would resemble:

{ int prime = 13441; int psiKBound = 13000; //#define INDEX(x, y, cols) ((x) * (cols) + (y)) int *validPairs = calloc(prime * prime, sizeof(int)); for(int k = 0; k < prime; k++) { for(int psi_k = 0; psi_k < psiKBound; psi_k++) { bool validPair = TestValidPair(k, psi_k, t_i,d_i,a_i,prime); if(validPair) { validPairs[INDEX(k, psi_k)] += 1; } } } free(validPairs); }

This bruteforcer is incredibly effective. One needs only 2 to 3 samples to pinpoint their search.

References