hesela.devAlgebraic signature
An algebraic signature is a compact finite-field fingerprint that preserves specified linear relations between data and parity.
For compatible field arithmetic and linear encoding, a parity fingerprint can be calculated from the data fingerprints. This lets a verifier compare compact responses instead of transferring the corresponding payloads. The primitive is not a cryptographic signature. [1]
The basic protocol's consistency check does not establish authenticity when sites cooperate to fabricate responses. The paper treats collusion separately using secret-dependent coding and blinding; that protection is not supplied by the fingerprint alone. [1]
The linked fixed GF(16) example maps four symbols to two. Every signature has 256 input blocks; the difference [2,3,1,0] preserves the signature. Its exhaustive counts illustrate collisions, not observed device errors or a replication of the paper's implementation. [2]
The block length is part of the detection contract. In the same GF(16) construction, powers of the evaluation point 2 repeat after 15 positions. At length 16, equal nonzero changes at positions 0 and 15 preserve both signature symbols; all one- and two-symbol changes are detected for lengths up to 15. The supplement derives and enumerates this boundary. Retaining separate, ordered page signatures detects its example; XORing them together does not. These are properties of the stated model, not physical error probabilities. [2]
Relations
Limitations
- Collision risk depends on the input-change model, field, signature construction and covered positions, not just the fingerprint width. [2]
Citations
- Schwarz and Miller, Store, Forget, and Check, ICDCS 2006, sections 3.1 and 4.2-4.3
- Hesela: finite-field signature derivation, code and exhaustive tests
Sources & caveats
- Historical research primitive with an educational finite-field calculation; no current product security guarantee or hardware experiment.