# Sparse Certificate Security Model
This document defines what `PHSPv1`, `PHSMv1`, and `PHCPv1` establish and what
they do not establish.
## Statement
For a prime field `F_p`, the committed workflow represents a public sparse
multilinear polynomial
```text
f(x_0, ..., x_(n-1)) = sum_t c_t * product_(j in S_t) x_j
```
and records a deterministic sum-check transcript for its sum over `{0,1}^n`.
`PHSMv1` contains the canonical polynomial. `PHCPv1` contains its
domain-separated BLAKE2b-256 commitment, claimed sum, round messages, final
evaluation, and transcript digest.
## Current Verification Profile
The v1 verifier reads the complete public polynomial and deterministically
recomputes:
1. the polynomial commitment,
2. the Boolean-hypercube sum,
3. every expected round polynomial,
4. every Fiat-Shamir challenge,
5. the final evaluation and transcript digest.
Acceptance therefore means that the supplied files match the deterministic v1
derivation. It is a conformance and reproducibility check, not a succinct
delegation result.
For this polynomial representation, the claimed sum also has the closed form
```text
sum_t c_t * 2^(n - |S_t|) mod p
```
so a verifier that already reads every sparse term can calculate the statement
without the million-round certificate. The certificate is useful as a stable,
cross-language stress artifact, but it does not reduce verifier asymptotic work.
## Security Properties
- **Canonical binding:** changing canonical `PHSMv1` bytes changes the
BLAKE2b-256 commitment except in the event of a hash collision.
- **Deterministic transcript integrity:** changing certificate metadata,
rounds, final evaluation, or transcript state is rejected by full replay.
- **Prime-field enforcement:** Rust and Python now reject composite moduli
using deterministic primality checks over the complete `u64` range.
- **Memory safety objective:** length fields are checked against available
input before encoded collections are allocated. Decoders cap inputs at 16
million variables, one million terms, one million variables per monomial, 1
MiB seeds, and a 64 million-incidence work budget.
- **Cross-language conformance:** separate Rust and Python implementations parse and
replay the stable formats.
## Non-Goals
The v1 formats do not provide:
- succinct verification,
- a polynomial commitment opening proof,
- zero knowledge or witness hiding,
- proof of arbitrary computation,
- protection from a malicious local verifier implementation,
- post-quantum security certification,
- an established novelty or world-first claim.
## Probabilistic Sum-Check Boundary
A conventional multilinear sum-check verifier checks round consistency and one
final polynomial evaluation instead of recomputing each expected round. Its
classical interactive soundness error is bounded by approximately `n / |F|`
for one repetition.
For the published parameters:
```text
n = 1,000,000
security >= approximately 9.97 bits
```
That is not an acceptable cryptographic soundness target. BLAKE2b-derived
Fiat-Shamir challenges do not enlarge the field or remove this algebraic bound.
The estimate can be reproduced with:
```bash
python3 scripts/soundness_budget.py
```
Using the 64-bit prime `18446744073709551557` raises one-repetition security to
approximately 44.07 bits at one million rounds. Three independently
domain-separated repetitions would exceed a 128-bit classical union-bound
target, before accounting for the Fiat-Shamir transform's random-oracle model.
## Threats and Mitigations
| Workload substitution | Domain-separated hash commitment | Not a polynomial commitment |
| Certificate bit corruption | Exact replay and transcript digest | Depends on verifier correctness |
| Composite modulus | Deterministic primality rejection | Construction still panics on invalid Rust input |
| Length-based allocation abuse | Input-size checks before encoded allocations | Applications should still impose file-size limits |
| Common-mode implementation error | Rust/Python conformance and property tests | Both implementations remain project-authored |
| Malicious prover in standard sum-check | Not the v1 verification profile | Requires a v2 protocol and soundness budget |
## v2 Security Target
A research-grade successor must:
1. use a field/repetition plan with at least 128 bits of stated algebraic
soundness,
2. separate prover logic from verifier logic,
3. check standard sum-check identities rather than exact prover replay,
4. bind final evaluation through a reviewed polynomial commitment or a clearly
stated public-data oracle model,
5. domain-separate every repetition and protocol version,
6. publish malformed-input, differential, and external-reproduction results.
The project conformance corpus is in `conformance/v1`. Its manifest fixes
digests and expected outputs. Rust and Python require every single-byte XOR
mutation of the small canonical vectors to reject.