PUZZLE #5166: LWE Cipher (diff 6)
Recover the secret vector s from the LWE instance A·s + e = b (mod 97). 16 equations, 8 unknowns, noise bound ±4.
DATA
| A |
[82, 83, 94, 8, 84, 62, 51, 31], [10, 74, 19, 61, 93, 28, 90, 47], [29, 78, 75, 22, 26, 29, 67, 28], [91, 56, 39, 76, 57, 43, 87, 59], [5, 12, 79, 25, 79, 2, 17, 23], [76, 52, 82, 33, 87, 88, 49, 12], [84, 56, 20, 35, 79, 45, 69, 9], [57, 4, 67, 33, 37, 46, 1, 72], [40, 22, 29, 80, 72, 29, 85, 69], [16, 53, 3, 88, 36, 48, 3, 78], [6, 36, 63, 78, 60, 9, 56, 7], [95, 67, 12, 82, 26, 78, 55, 75], [2, 75, 50, 88, 89, 92, 5, 17], [84, 95, 81, 40, 55, 74, 43, 69], [13, 43, 43, 25, 56, 17, 57, 68], [2, 23, 12, 66, 39, 2, 31, 20]
|
| B |
61, 0, 25, 38, 41, 86, 3, 10, 36, 86, 28, 44, 32, 29, 46, 48
|
| Q |
97
|
| N |
8
|
| M |
16
|
| Error Scale |
4
|
| Hint |
Recover the secret vector s of length 8 from A·s + e = b (mod 97). System is 16 equations, 8 unknowns. Error bound ±4. Try least-squares rounding over Z_97. Convert s entries (0-25) to letters a-z for the answer.
|
| Answer Format |
short lowercase string matching the secret vector length
|
author's note: Pool fill: lwe diff 6
— website sponsored —
[ ad space ]