Lyubashevsky’s Fiat-Shamir-with-aborts signature over unstructured LWE. The public key is T = A·S for a plain matrix A over Z_q and a ternary secret S; a signature is a sparse challenge c together with z = y + S·c, and the verifier recomputes A·z − T·c, which equals the commitment A·y exactly. The abort is the point of the construction: a z outside a box smaller than the one y was drawn from is discarded and the signer retries, which makes the accepted z uniform on that box and independent of the secret. Dilithium is this scheme over a polynomial ring.
| Property | Value |
|---|---|
| Category | Asymmetric Ciphers |
| Sub-category | Lattice-Based Digital Signature |
| Security status | 🎓 Educational Only |
| Complexity | Expert |
| Inventor | Vadim Lyubashevsky |
| Year | 2009 |
| Origin | 🌐 International |
| Source | algorithms/asymmetric/lwe-signature.js |
| Parameter | Supported values |
|---|---|
| Key sizes | 32 bytes (256 bits) |
Status: 🎓 Educational Only
| Issue | Description | Mitigation |
|---|---|---|
| Parameters are not a published set | — | No standard fixes a parameter set for this construction, and the one here was chosen for correctness rather than from a lattice-attack analysis. Use ML-DSA (FIPS 204), which is this scheme over a ring with parameters that have been analysed |
| Omitting the abort leaks the secret | — | Returning a z that falls outside the acceptance box, rather than retrying, makes the signature distribution depend on S and leaks it over many signatures. The bound is enforced on both sides here and must not be relaxed |
| Published demonstration seed | — | The seed in the test vectors is printed in the source and confers no confidentiality. Supply a secret seed of SEED_LENGTH random octets for any use beyond demonstration |
3 vectors ship with this algorithm and run in the test suite. Byte values are hexadecimal.
Vector 1 — LWE-Signature round trip, 3-octet message
| Field | Value |
|---|---|
key |
000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f |
input |
616263 |
expected |
616263 |
Vector 2 — LWE-Signature round trip, message of zero octets only
| Field | Value |
|---|---|
key |
000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f |
input |
00000000000000000000000000000000 |
expected |
00000000000000000000000000000000 |
Vector 3 — LWE-Signature round trip under a second seed
| Field | Value |
|---|---|
key |
f0e0d0c0b0a090807060504030201000ffeeddccbbaa99887766554433221100 |
input |
4c57452d5369676e6174757265207465737420766563746f72 |
expected |
4c57452d5369676e6174757265207465737420766563746f72 |