short integer solution (SIS) problem
E639078
average-case hard problem
computational problem
lattice problem
post-quantum cryptography assumption
The short integer solution (SIS) problem is a fundamental lattice-based computational problem that underpins many modern cryptographic constructions, especially in post-quantum cryptography.
Observed surface forms (1)
| Surface form | Occurrences |
|---|---|
| short integer solution problem | 0 |
Statements (49)
| Predicate | Object |
|---|---|
| instanceOf |
average-case hard problem
ⓘ
computational problem ⓘ lattice problem ⓘ post-quantum cryptography assumption ⓘ |
| abbreviation | SIS ⓘ |
| alsoKnownAs | short integer solutions problem ⓘ |
| basedOn | integer lattices ⓘ |
| considered |
hard for classical computers
ⓘ
hard for quantum computers ⓘ |
| constraint | matrix-vector product equals zero modulo q ⓘ |
| definedOver | integer matrix modulo q ⓘ |
| field |
computational complexity theory
ⓘ
cryptography ⓘ |
| hardnessType | worst-case to average-case reduction ⓘ |
| hasVariant |
approximate SIS problem
ⓘ
inhomogeneous SIS problem ⓘ module-SIS problem ⓘ ring-SIS problem ⓘ |
| introducedInContextOf | lattice-based cryptography ⓘ |
| involves | finding short nonzero integer vector ⓘ |
| motivation | design of post-quantum secure primitives ⓘ |
| parameter |
dimension n
ⓘ
modulus q ⓘ norm bound for short vector ⓘ number of columns m ⓘ |
| relatedTo |
NTRU cryptosystem
NERFINISHED
ⓘ
bounded distance decoding problem ⓘ closest vector problem ⓘ learning with errors problem ⓘ shortest vector problem ⓘ |
| securityBasisFor |
Fiat–Shamir with aborts signatures
ⓘ
Lyubashevsky-style lattice signatures ⓘ SIS-based hash functions ⓘ SIS-based identification schemes ⓘ |
| typicalNorm |
Euclidean norm
ⓘ
infinity norm ⓘ |
| underpins |
lattice-based cryptography
ⓘ
post-quantum cryptography schemes ⓘ |
| usedIn |
attribute-based signatures
ⓘ
collision-resistant hash functions ⓘ commitment schemes ⓘ digital signature schemes ⓘ group signatures ⓘ hash-and-sign signatures ⓘ homomorphic authenticators ⓘ identification schemes ⓘ lattice-based identification protocols ⓘ ring signatures ⓘ zero-knowledge proofs ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.