06 — Security Levels
Two Parameter Sets
FN-DSA is simpler than ML-DSA — only two security levels instead of three:
| FN-DSA-512 | FN-DSA-1024 | |
|---|---|---|
| NIST Security Level | Level 1 (~AES-128) | Level 5 (~AES-256) |
| Ring dimension (n) | 512 | 1,024 |
| Modulus (q) | 12,289 | 12,289 |
| Public key | 897 B | 1,793 B |
| Private key | 1,281 B | 2,305 B |
| Signature | 666 B | 1,280 B |
| Sign time | ~0.5 ms | ~1.2 ms |
| Verify time | ~0.08 ms | ~0.15 ms |
How the Parameters Work
Ring Dimension (n)
The dimension of the polynomial ring R_q = Z_q[X]/(X^n + 1):
- n = 512: Polynomials have 512 coefficients
- n = 1,024: Polynomials have 1,024 coefficients
Higher n means:
- More security: Larger lattice = harder to find short vectors
- Larger keys: 2× more coefficients = 2× larger public key
- Larger signatures: 2× more coefficients = ~2× larger signature
- Slower operations: 2× more FFT points = ~2.2× slower (log factor)
Modulus (q = 12,289)
Both parameter sets use the same modulus because:
- q must support NTT up to n = 1,024 (actually up to 4,096)
- 12,289 = 2^12 × 3 + 1 = 4,096 × 3 + 1
- 4,096 = 212, so q ≡ 1 (mod 212), supporting NTT up to 4,096 points
- Fits in 16-bit integers (q < 2^16 = 65,536)
Gaussian Width (σ)
The standard deviation of the discrete Gaussian distribution:
- Both parameter sets use σ ≈ 1.17 × √q (normalised)
- This is tight — signatures are as small as possible while maintaining security
Security Analysis
Classical Attacks
| Attack | Cost against FN-DSA-512 | Cost against FN-DSA-1024 |
|---|---|---|
| Lattice reduction (BKZ) | ~2128 | ~2256 |
| Meet-in-the-middle | ~2256 | ~2512 |
| Primal attack | ~2128 | ~2256 |
| Dual attack | ~2130 | ~2258 |
Quantum Attacks
| Attack | Cost against FN-DSA-512 | Cost against FN-DSA-1024 |
|---|---|---|
| Grover on hash | ~2128 | ~2256 |
| Quantum BKZ | ~264 (estimated) | ~2128 (estimated) |
| Quantum sieve | ~290 (estimated) | ~2180 (estimated) |
Important caveat: Quantum lattice attacks are not well-understood. The estimates above are conservative; actual security may be higher.
How to Choose
Default: FN-DSA-512
Use this for:
- Standard security requirements (equivalent to AES-128)
- Bandwidth-constrained environments (666-byte signatures)
- Performance-critical applications (faster signing)
When is AES-128 enough?
- Short-term signatures (session tokens, ephemeral certificates)
- Environments where keys are rotated frequently
- Systems where the cost of Level 5 is prohibitive
Use FN-DSA-1024 When
- Long-term signatures (legal documents, archive notarisation)
- High-assurance environments (root certificates, trust anchors)
- Regulatory requirements mandate highest security level
- Future-proofing against advances in quantum algorithms
When is AES-256 necessary?
- National security systems
- Long-term legal evidence
- Financial systems with multi-decade lifetimes
- Scenarios where algorithm replacement is physically impossible
Comparison with Other Schemes at Same Levels
Level 1 (AES-128 equivalent)
| Algorithm | Public key | Signature | Sign | Verify |
|---|---|---|---|---|
| FN-DSA-512 | 897 B | 666 B | ~0.5 ms | ~0.08 ms |
| ML-DSA-44 | 1,312 B | 2,420 B | ~0.3 ms | ~0.08 ms |
| SLH-DSA-SHA2-128s | 32 B | 7,856 B | ~8 ms | ~0.8 ms |
| ECDSA P-256 | 32 B | 64 B | ~0.05 ms | ~0.1 ms |
FN-DSA-512 has the smallest signature among PQC schemes at Level 1.
Level 5 (AES-256 equivalent)
| Algorithm | Public key | Signature | Sign | Verify |
|---|---|---|---|---|
| FN-DSA-1024 | 1,793 B | 1,280 B | ~1.2 ms | ~0.15 ms |
| ML-DSA-87 | 2,592 B | 4,595 B | ~0.8 ms | ~0.18 ms |
| SLH-DSA-SHAKE-256s | 64 B | 29,792 B | ~40 ms | ~2 ms |
| ECDSA P-521 | 66 B | 132 B | ~0.2 ms | ~0.3 ms |
FN-DSA-1024 has the smallest signature among PQC schemes at Level 5.
Resources
- NIST FIPS 206, Section 4: Parameter Sets
- Security analysis: falcon-sign.info/security.html
- Albrecht et al., "Estimate all the {LWE, NTRU} schemes!" (2018), SCN