# Coron
Coron paper: http://www.crypto-uni.lu/jscoron/publications/bivariate.pdf.
Let's have a form:
```
{
"p": 24554940634497023,
"iso_degree": 4350,
"quadratic_form": 12 * x1^2 + 31 * x1 * x2 + 9 * x1 * x3^2 + 9 * x3 * x4^3 + 19 * x4^4,
"sol": [1, 9, 8, 3],
"known_variables": [],
},
```
The polynomial for which we want to find roots is: `9*z*t^3 + 19*t^4 + 9*x*z^2 + 12*x^2 + 31*x*y - 4350`.
According to the paper we can choose the modulus N as:
```
√ω·2−ω ·(XY)^k ·W ≤n<2·(XY)^k ·W
```
where `δ` is a maximum degree in each variable separately, we choose `k >= 0`, `ω = (δ + k + 1)^2`, and `W =∥p(xX,yY)∥∞.`
For our form:
```
N lower bound:
1003578542461285532463883
N upper bound:
42819351145014849385125638
```
# First run (small `N`)
```
N:
1003578542461285532463919
```
Bitlengths of matrix elements (before reduction):
```
[ 27 120 118 126 133 133]
[ 0 94 0 0 0 0]
[ 0 0 94 0 0 0]
[ 0 0 0 100 0 0]
[ 0 0 0 0 107 0]
[ 0 0 0 0 0 107]
```
Bitlengths of matrix elements (after reduction):
```
[ 39 45 44 50 58 57]
[ 80 49 47 53 61 60]
[ 62 94 67 73 81 80]
[ 60 67 94 72 79 78]
[ 73 80 78 100 92 91]
[ 79 92 92 96 101 102]
```
First three polynomials after LLL:
```
---
-936543609*z*t^3 - 1977147619*t^4 - 936543609*x*z^2 - 1248724812*x^2 - 3225872431*x*y + 452662744350
---
-8142415767*z*t^3 - 17189544397*t^4 - 8142415767*x*z^2 - 10856554356*x^2 - 28046098753*x*y - 1003578542457350031509869
---
-6087514727627820*z*t^3 - 12851419980547620*t^4 - 6087514727627820*x*z^2 - 8116686303503760*x^2 + 1003578521493179248412539*x*y + 2942298785020113000
pol2 = 0
pol3 not 0
pol4 not 0
```
# Second run (big `N`)
```
N:
42819351145014849385125547
```
Bitlengths of matrix elements (before reduction):
```
[ 27 125 124 132 137 138]
[ 0 99 0 0 0 0]
[ 0 0 99 0 0 0]
[ 0 0 0 106 0 0]
[ 0 0 0 0 112 0]
[ 0 0 0 0 0 112]
```
Bitlengths of matrix elements (after reduction):
```
[ 39 45 44 50 58 57]
[ 86 54 53 59 67 65]
[ 67 99 72 78 86 85]
[ 66 72 99 77 85 84]
[ 79 85 84 106 98 97]
[ 84 97 97 101 107 108]
```
First three polynomials after LLL:
```
---
936543609*z*t^3 + 1977147619*t^4 + 936543609*x*z^2 + 1248724812*x^2 + 3225872431*x*y - 452662744350
---
-350674437114*z*t^3 - 740312700574*t^4 - 350674437114*x*z^2 - 467565916152*x^2 - 1207878616726*x*y - 42819351144845356740520447
---
-259733942981248140*z*t^3 - 548327212960412740*t^4 - 259733942981248140*x*z^2 - 346311923974997520*x^2 + 42819350250375712449715287*x*y + 125538072440936601000
pol2 = 0
pol3 not 0
pol4 not 0
```
# Question
In two runs two different `N` are used, but the obtained shortest vector is the same.
If we add a shift of the original polynomial, then we again get the same shortest vector, but this time by a shift.
I don't understand why different lattices have the same shortest vector. And I wonder whether we can modify the lattice to get a different shortest vector.
EDIT: I have a bug in quadvariate implementation, this might be the cause.
EDIT: It wasn't a bug.
# Trying to get different short enough polynomials
```
f = -52 + 4*x1^2 + 12*x1*x2 + 7*x3^2 + 5*x4^2
```
The root is `r = [1, 3, 1, 1]`.
Let's say the bound is `X = Y = Z = T = 101`.
We choose `n = 122461`.
We multiply `f` by the inverse of `-52` and we get a polynomial for which `r` is a solution modulo `n`:
```
f1 = 1 + 9420*x^2 + 28260*x*y + 16485*z^2 + 11775*t^2
```
If we can construct a lattice with only the polynomials that have `r` as a root modulo `n` and if we get a short enough vector, this vector will have `r` as root also over integers.
We multiply by the inverse of `-52` to get `1` at the position in the matrix where we don't have an element "beneath in the matrix" to reduce it (see the matrix below).
Bitlengths of matrix elements (before reduction):
```
------ sorted monomials --------
[1, t^2, z^2, x*y, x^2]
```
```
[ 1 27 28 29 27]
[ 0 31 0 0 0]
[ 0 0 31 0 0]
[ 0 0 0 31 0]
[ 0 0 0 0 31]
```
```
f1 = 1 + 11775*t^2 + 16485*z^2 + 28260*x*y + 9420*x^2
```
```
[ 1 11775*T^2 16485*Z^2 28260*X*y 9410*X^2]
[ 0 n*T^2 0 0 0 ]
[ 0 0 n*Z^2 0 0 ]
[ 0 0 0 n*X*Y 0 ]
[ 0 0 0 0 n*X^2 ]
```
If we multiply `f1` by some `a` such that some `f1` coefficient wraps around `n`, I expected at first we end up with a lattice with a different shortest vector. But that's not true because (we get a * shortest_vector):
- Let's have `a` such that `11775 * a = b + k * n` for some integer `k`.
- `f1 * a % n = a + b * t^2 + ...`
- We construct a lattice:
```
[ a b*T^2 ... ]
[ 0 n*T^2 0 0 0 ]
[ 0 0 n*Z^2 0 0 ]
[ 0 0 0 n*X*Y 0 ]
[ 0 0 0 0 n*X^2 ]
```
- By multiplying the first row of the first lattice we get `[a, 11775*T^2 * a = b*T^2 + k*n*T^2, ... ]`
- But the part `k*n*T^2` gets removed in LLL, so we see the first row of the second lattice is the element of the first lattice.
Another option is to add a shift of the polynomial, for example `x^2 * f`:
Bitlengths of matrix elements (before reduction):
```
[27 29 28 27 1 0 0 0 0]
[14 0 0 0 0 40 42 41 41]
[ 0 31 0 0 0 0 0 0 0]
[ 0 0 31 0 0 0 0 0 0]
[ 0 0 0 31 0 0 0 0 0]
[ 0 0 0 0 0 44 0 0 0]
[ 0 0 0 0 0 0 44 0 0]
[ 0 0 0 0 0 0 0 44 0]
[ 0 0 0 0 0 0 0 0 44]
```
But for the same reason as above we end up with the same shortest vector as with the original lattice and its multiplication by `x^2`.
Sign in with Wallet
Connect another wallet