libtalos_schnorr

A C library implementing Schnorr Non-Interactive Zero-Knowledge (NIZK) proofs over elliptic curves, with generalized multi-equation extensions suitable for protocols such as Signal's Keyed-Verification Anonymous Credentials (KVAC).

---

Overview

libtalos_schnorr provides cryptographic building blocks for proving knowledge of discrete logarithms without revealing their values. It is built on libsodium and ed448-goldilocks, and offers:

• RFC 8235-compliant Schnorr NIZK proofs over elliptic curves
• Two security levels: Ristretto255 (128-bit) and Decaf448 (224-bit)
• Generalized Schnorr proofs (multi-equation, multi-witness)
• Per-equation generators and masked witnesses (Signal KVAC support)
• A two-layer API: a composable interactive sigma protocol and a standalone non-interactive (Fiat-Shamir) interface
• Constant-time operations, mandatory secret wiping, no heap allocation

What is a Schnorr NIZK proof?

A Schnorr NIZK proof allows a prover to demonstrate knowledge of a secret a such that A = G × [a] (where G is a fixed generator and A is the public key) without revealing a. The proof is:

• Non-interactive: no back-and-forth communication
• Zero-knowledge: reveals nothing about a beyond the fact of knowledge
• Unforgeable: only a party that knows a can produce a valid proof

---

RFC 8235 Compliance

The library fully implements RFC 8235 Section 3 (elliptic-curve variant).

Feature	Ristretto255	Decaf448
Interactive sigma protocol (3-pass)	✅	✅
Fiat-Shamir transform (NIZK)	✅	✅
Length-prefixed hash construction	✅	✅
Public key validation	✅	✅
Secure RNG for ephemeral nonces	libsodium	libsodium
Hash function	SHA-512	SHAKE256

Curve choices:

• Ristretto255: 128-bit classical security. 32-byte points and scalars, prime-order group (cofactor = 1), built on Curve25519.
• Decaf448: 224-bit classical security. 56-byte points and scalars, prime-order group (cofactor = 1), built on Ed448-Goldilocks.

The library does not implement RFC 8235 Section 2 (finite-field multiplicative groups, DSA-style). That variant produces ~2 KB proofs, is slower than elliptic curves, and offers no security advantage; modern deployments universally use elliptic curves.

---

Extensions Beyond RFC 8235

RFC 8235 defines a proof of knowledge of a single discrete logarithm. Real-world protocols typically need more expressive proofs.

Generalized Schnorr proofs (multi-equation)

Prove knowledge of k witnesses satisfying m linear equations:

P[j] = Σ_i  a[j][i] · G_i × [w_i]      for j = 0, …, m-1

• Layer 2: gen_prove(V, r, coeffs, generators, P, w, k, m, …) / gen_verify(…)
• Layer 1: gen_prover_commit → gen_compute_challenge → gen_prover_respond → gen_verifier_check

Per-equation generators

Each equation may use its own generator for each witness:

P[j] = Σ_i  G_{j,i} × [w_i]

• Layer 2: gen_prove_ex(…) / gen_verify_ex(…)
• Layer 1: gen_prover_commit_ex → gen_compute_challenge_ex → gen_prover_respond → gen_verifier_check_ex

Masked witnesses

Some equations use only a subset of the witnesses; the rest are "masked" (inactive). Used in protocols such as Signal KVAC where the issuance proof relates several heterogeneous equations through a shared Fiat-Shamir challenge.

• Layer 2: gen_prove_masked(…) / gen_verify_masked(…)
• Layer 1: gen_prover_commit_masked → gen_compute_challenge_masked → gen_prover_respond_masked → gen_verifier_check_masked

Batch verification

Verify multiple independent generalized proofs in a single multi-scalar multiplication: gen_batch_verify(…). Requires pre-computed challenges (use gen_compute_challenge[_ex|_masked] to derive them).

Utilities

• Pedersen commitments (the k=2, m=1 special case of generalized Schnorr)
• Hash-to-scalar and hash-to-group
• Point and scalar arithmetic
• Constant-time comparisons (memcmp, point_eq, scalar_eq)

---

Two-Layer API

Layer 1: interactive sigma protocol (composable)

For protocols that need custom challenge derivation, such as hybrid classical / post-quantum proofs:

talos_schnorr_255_prover_state_t state;
uint8_t V[32];
talos_schnorr_255_prover_commit(&state, V);     // 1. commit
                                                // 2. obtain challenge c
uint8_t r[32];
talos_schnorr_255_prover_respond(r, &state, sk, c);  // 3. respond

talos_schnorr_255_verifier_check(pk, V, c, r);  // verify

Challenge generation options:

• Interactive: verifier draws c randomly via talos_schnorr_255_scalar_random(c).
• Fiat-Shamir: both parties compute the same c via talos_schnorr_255_compute_challenge(c, V, pk, user_id, …).
• Custom hybrid: combine multiple protocol transcripts before hashing.

Seeded commit variants (prover_commit_seed, gen_prover_commit_seed) accept a caller-supplied nonce instead of drawing one from the RNG. They are intended for deterministic test vectors and integration with protocols that derive nonces externally. Production code should use the random variants.

Layer 2: non-interactive (Fiat-Shamir)

For standalone proofs with automatic challenge derivation:

talos_schnorr_255_proof_t proof;
talos_schnorr_255_prove(&proof, sk, pk,
                        user_id, user_id_len,
                        other_info, other_info_len);

talos_schnorr_255_verify(&proof, pk,
                         user_id, user_id_len,
                         other_info, other_info_len);

Layer 2 wraps Layer 1 with the RFC 8235 Fiat-Shamir transform c = H(G ‖ V ‖ A ‖ UserID ‖ OtherInfo). Internally, prove() calls prover_commit → compute_challenge → prover_respond, and verify() calls compute_challenge → verifier_check.

---

Signal KVAC Demo

examples/signal_kvac_demo.c exercises the Signal KVAC issuance protocol end-to-end:

1. Server setup (§3.1): key generation (w, w′) → C_W; MAC issuance producing (t, U, V) over attribute M_1.

2. Issuance proof π_I (§3.2), a single masked proof relating three equations with five witnesses (w, w′, x0, x1, y1):

   eq.0: C_W = G_w × [w] + G_w' × [w']
   eq.1: G_V − I = G_x0 × [x0] + G_x1 × [x1] + G_y1 × [y1]
   eq.2: V = G_w × [w] + U × [x0] + U_t × [x1] + M_1 × [y1]
   

   All three equations share a single Fiat-Shamir challenge, cryptographically binding them together. This is the use case that motivates gen_prove_masked.

3. Credential presentation (§3.2 steps 1–4): randomization by the user, verification by the server.

Run after building:

./build/examples/signal_kvac_demo

---

Getting Started

Prerequisites

• libsodium ≥ 1.0.18 (Ristretto255 support)
• ed448-goldilocks (Decaf448 support; vendored in third_party/)
• C11 compiler (GCC or Clang)
• CMake ≥ 3.10

Build and test

cmake -S . -B build
cmake --build build -j$(nproc)
ctest --test-dir build --output-on-failure

Minimal example

#include <talos_schnorr.h>
#include <talos_schnorr_255.h>

int main(void) {
    talos_schnorr_init();

    uint8_t pk[32], sk[32];
    talos_schnorr_255_keygen(pk, sk);

    talos_schnorr_255_proof_t proof;
    const uint8_t user_id[] = "alice@example.com";
    talos_schnorr_255_prove(&proof, sk, pk,
                            user_id, sizeof(user_id) - 1,
                            NULL, 0);

    int valid = talos_schnorr_255_verify(&proof, pk,
                                         user_id, sizeof(user_id) - 1,
                                         NULL, 0);

    talos_schnorr_255_sk_clear(sk);
    talos_schnorr_255_proof_clear(&proof);
    return valid == 0 ? 0 : 1;
}

See docs/DESIGN.md for the full API reference, curve-specific parameters, and design rationale.

---

Security Notes

• Constant-time operations. All secret-dependent comparisons go through libsodium / libdecaf constant-time primitives.
• Single-use prover state. Each prover state object carries a consumed_ flag that is set after prover_respond. A second use returns an error. Nonce reuse leaks the secret key (a = (r − r′) / (c′ − c) mod l); the flag is the primary defense against this in callers that reuse state objects.
• Mandatory secret wiping. Ephemeral scalars and intermediate buffers are zeroed via sodium_memzero before functions return.
• No heap allocation. The library uses only stack-allocated state; there is no malloc / free.
• Canonical encoding checks. Points and scalars on the wire are validated for canonicality before any group operation.

---

Project Layout

libtalos_schnorr/
├── include/
│   ├── talos_schnorr.h           # Common header (init, version, errors)
│   ├── talos_schnorr_255.h       # Ristretto255 API
│   └── talos_schnorr_448.h       # Decaf448 API
├── src/
│   ├── talos_schnorr_common.c    # Common implementation
│   ├── talos_schnorr_255.c       # Ristretto255 implementation
│   └── talos_schnorr_448.c       # Decaf448 implementation
├── tests/
│   ├── test_schnorr_255.c
│   └── test_schnorr_448.c
├── examples/
│   └── signal_kvac_demo.c
├── tools/
│   └── gen_vectors.py            # Reference test-vector generator
├── docs/
│   ├── DESIGN.md                 # Design rationale
│   ├── libtalos_schnorr_seeded_api.md
│   ├── signal_kvac_example.md
│   └── specs/                    # RFC 8235, Signal KVAC paper
├── third_party/                  # Vendored libsodium, ed448-goldilocks
├── CHANGELOG.md
├── LICENSE
└── README.md

---

References

• RFC 8235: Schnorr Non-interactive Zero-Knowledge Proof (September 2017)
• Chase, Perrin, Zaverucha. The Signal Private Group System and Anonymous Credentials Supporting Efficient Verifiable Encryption (2020)
• Ristretto: prime-order group abstraction for Curve25519
• libsodium: cryptographic library (RNG, hashing, Ristretto255)
• ed448-goldilocks: Ed448-Goldilocks implementation

---

License

This project is licensed under the GNU Affero General Public License, version 3.0 (AGPL-3.0-only). See LICENSE for the full text.

Third-party libraries vendored under third_party/ remain under their respective licenses. See third_party/THIRD_PARTY_LICENSES.md for the reproduced notices.

---

Contributing and Issues

Bug reports and security issues should be filed on the project repository.