PUZZLE #5342: LWE Cipher (diff 7)
Recover the secret vector s from the LWE instance A·s + e = b (mod 97). 18 equations, 9 unknowns, noise bound ±5.
DATA
| A |
[73, 30, 1, 10, 43, 69, 53, 25, 85], [56, 84, 41, 76, 78, 55, 44, 79, 21], [74, 30, 78, 74, 72, 74, 68, 89, 80], [7, 36, 84, 51, 80, 86, 20, 56, 0], [60, 45, 21, 20, 87, 46, 66, 57, 39], [56, 45, 64, 60, 94, 49, 34, 2, 77], [49, 17, 84, 50, 28, 21, 75, 37, 87], [87, 83, 81, 9, 65, 3, 79, 37, 66], [40, 93, 68, 54, 48, 36, 7, 73, 0], [66, 13, 92, 32, 6, 62, 70, 35, 24], [94, 11, 58, 34, 48, 88, 30, 1, 55], [16, 0, 25, 20, 27, 57, 63, 17, 15], [48, 52, 58, 1, 29, 60, 34, 29, 18], [77, 58, 49, 47, 4, 91, 78, 47, 20], [87, 89, 58, 52, 49, 72, 6, 26, 44], [89, 71, 50, 22, 43, 17, 49, 15, 24], [50, 53, 4, 75, 73, 38, 39, 8, 46], [47, 26, 17, 83, 91, 59, 41, 88, 92]
|
| B |
8, 72, 41, 6, 88, 8, 57, 4, 89, 8, 39, 73, 43, 13, 65, 51, 67, 78
|
| Q |
97
|
| N |
9
|
| M |
18
|
| Error Scale |
5
|
| Hint |
Recover the secret vector s of length 9 from A·s + e = b (mod 97). System is 18 equations, 9 unknowns. Error bound ±5. 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 7
— website sponsored —
[ ad space ]