Is $a b + e \mod P$ hard to invert?

Question

Given $a, p$, $c$ where $c = a b + e \mod p$, can $e$ be recovered?

Additional details:

• $p$ is prime
• $a, p$ are re-used across many instances of the problem
• $b, e$ (and by extension $c$) are always unique for each instance of the problem
• $a, p$ are about 783 bits, with $a$ being smaller then $p$ by a no more then a few bits
• $b, e$ are uniformly random 256-bit integers

What I have tried:

• If the problem was not done modulo $p$, but was over integers, then it would be a simple matter of performing $c \mod b$ to obtain $e$.
• The modular inverse of $a$ is about the same size as $a$, otherwise we could do $a_i c \equiv b + a_i e \mod p$ followed by $\mod p_i$ to recover $b$.

• I noticed that:

  

  $a b \equiv p - b(p - a) \mod p$ which lead me to this little algorithm:

  $x = p - a\\ b = c / x\\ e = c \mod x\\ y = x q + e \mod p\\ y \equiv c\\ y = c - e - 1\\ b = (y * inverse(a, p)) \mod N\\ output\ b, e$

  but for whatever reason, this only seems to function when $p=65537$ and $a=256$.

  • Applying the above algorithm to a random instance of $a$ for the actual $p$ does not output $b, e$ correctly.
  • If $b, e$ were the same size as $a$, I'm pretty sure it would be information theoretically secure.
  • Since $b, e$ are smaller, it makes me think there is leakage somehow.
  • Since $a b \mod p$ is about 783 bits in size and $e$ is only about 256 bits in size, then much of the upper bits of $a b + e \mod p$ are equal to the upper bits of $p q \mod p$.

  I don't know how to take exploit this information.

The answer might be obviously simple, but I just haven't been able to figure it out for a few weeks.

Here is a gist with python code for what I am attempting to break.

Answer 1

Background: $ab + e \bmod P$ is the public key operation for a trapdoor function I am researching. The same expression, usually with more terms/in a higher dimension, is quite prevalent in many lattice based cryptosystems.

My work is available on github, and consequently I happened to receive some analysis from another user there. The following is a transcription of the users comments.

The "EPQ" key exchange program given here is vulnerable to a Lagarias-Odlyzko style lattice attack. The usual upper triangular lattice basis matrix is formed by taking an identity matrix and replacing the rightmost column with a vector made from the public key, system parameters, and ciphertext. This 3 dimensional lattice contains a short vector that exposes the plaintext, allowing us to recover it with an SVP oracle.

I've experimentally verified the attack using fpLLL as the SVP oracle, and had successful key recovery in every trial. For concreteness and convenience, the lattice basis I've used is (where P is the system modulus, K is the public key, and C is the ciphertext):

$\begin{pmatrix} 1 & 0 & P \\ 0 & 1 & K \\ 0 & 0 & C \end{pmatrix}$

I actually used vanilla fpLLL on the command line, and manually typed in the numbers generated by the program. To demonstrate, I've generated this keypair just now:

Public: 914984079037409997753646956896411367020716296641338957641608068567317657086975832590795630339277510788727851945111403187181412830140879040014025475367233381190196941804342169193880920240279264797993403702890997094738006766532630568999

Private: 2502644320274784300686027905786577204651695824856428916800576785188468831099194056968432976701679611038222704877942453351051289674522482331865454722815092306

And encrypted a random key to get this ciphertext: 31156599101993645275226400017248608173867507193910625562695392661378570296553738808446028840212848623662312900007512235634449530713883849145685393866636831069585880990434485646285032107701202733953935100342846543008476824530843873800801
(The random key was: 101020355786439301914818388108389342468906297672328361246394394849844032365586)

Then I entered this into the command line by hand (the flag -a svp tells fpLLL to act as an SVP oracle):

...:~\$ ~/codes/fplll/fplll/fplll -a svp

$\begin{pmatrix} 1 & 0 & P_i \\ 0 & 1 & K_i \\ 0 & 0 & C_i \end{pmatrix}$

[values taken out of the matrix for readibility and horizontal space saving] with $P_i=$90539821999601667010016498433538092350601848065509335050382778168697877622963864208930434463149476126948597274673237394102007067278620641565896411613073030816577188842779580374266789048335983054644275218968175557708746520394332802669663
and $K_i=$914984079037409997753646956896411367020716296641338957641608068567317657086975832590795630339277510788727851945111403187181412830140879040014025475367233381190196941804342169193880920240279264797993403702890997094738006766532630568999
and $C_i=$31156599101993645275226400017248608173867507193910625562695392661378570296553738808446028840212848623662312900007512235634449530713883849145685393866636831069585880990434485646285032107701202733953935100342846543008476824530843873800801

fpLLL short vector output:

[203453603089198469384658317783196545918051882397653184390372945748471804449, -20132211511540947010614907531449286044959891949349819581130241666199997596098, 101020355786439301914818388108389342468906297672328361246394394849844032365586 ]

Which is of the form: [-modular_reduction_value, -s_value, plaintext] which correctly recovers the plaintext 101020355786439301914818388108389342468906297672328361246394394849844032365586 as well as the random s value used during encryption.

As for parameters that foil this attack, I found that the lattice starts to contain many unrelated short vectors if either s or e are increased in size by around 16 bits, but this causes the lower 16 bits of the shared key to be corrupted, and these 16 bits can be searched by brute force...

Conclusion

So as you can see, it seems like the real question is "with what parameter sizes is $ab + e \bmod P$ hard to invert?", and we basically happen to have a question about that here.

However, it looks like in order to really quantify that, we have to know what problem the cryptosystem reduces to (if any); Then, we can find out what the most efficient algorithms for solving that problem are and how they scale, and use that information to select secure parameter sizes.