Keyboard shortcuts

Press or to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

CI Docs License

Cryptographic Primitives for Privacy-Enhancing Technologies (PETs)

This repository hosts a collection of Rust libraries for building privacy-enhancing protocols. Think of these components as cryptographic PETs 🐕—reliable, well-behaved, and safe to keep around. It's organized as a Rust workspace with multiple crates:

  • dlog-group: abstraction layer over prime-order groups.
  • dlog-sigma-primitives: implementations of encryption schemes, commitments, and zero-knowledge proofs.

The goal of this project is to provide modular, composable, and group-agnostic building blocks for cryptographic applications such as secure voting and anonymous credentials.

⚠ Security Disclaimer

This project has not been independently audited. Correctness and resistance to side-channel attacks are not guaranteed. The software is not ready for production use. Use at your own risk.

License

Licensed under either of Apache License Version 2.0, or MIT license.

Acknowledgments

This work has been supported by the joint laboratory between the Bruno Kessler Foundation (FBK) and the Italian Government Printing Office and Mint (IPZS).

Introduction


dlog-group is a simple rust wrapper around different prime-order groups implementations where the decisional Diffie–Hellman (DDH), computational Diffie–Hellman (CDH) and discrete log (DL) problems are believed to be hard.

The purpose of this wrapper is to make it easy to switch between different group implementations. This can be useful for improving performance, adjusting security levels, or following new standards. By using a common interface, dlog-group lets you change the underlying group without rewriting your code, and makes it easy to compare how an implementation perform under different core operations.

Supported Groups

Currently, we support the following Elliptic-Curve Groups:

  1. ristretto, used by default;
  2. p256, enabled by features;
  3. k256, enabled by features;
  4. p384, enabled by features.

ristretto is build on top of the fast performing Curve25519 and follows Mike Hamburg’s Decaf construction. While many cryptographic systems require a group of prime order, most concrete elliptic-curve implementations fall short: they either offer a group of prime order with incomplete or variable-time addition formulas (e.g., many Weierstrass models), or they provide a fast and secure group whose order is not strictly prime but instead of the form , where is a small cofactor (e.g., Curve25519, which has a cofactor of 8).

Curve cofactors have been the cause of several vulnerabilities, however, when properly handled, they can allow for much better performance.

ristretto addresses these issues by providing a prime-order group abstraction over Curve25519.

p256 and p384 curves have long been officially recommended by the National Institute of Standards and Technology (NIST). Additionally, since 2023, Curve25519 is also included in the list of approved curves; see SP 800-186.

Design goals

The library assumes that the underlying group implementation:

  • Operates in constant time when appropriate,
  • Has a prime order (or uses a decaf-style abstraction to hide cofactors),
  • And correctly implements the group laws.

User Guide


Installation

dlog-group is published on crates.io. Add via Cargo:

cargo add dlog-group --features p256

Or add entries manually to your Cargo.toml (replace the version with the latest on crates.io):

[dependencies]
dlog-group = { version = "x.y.z", features = ["p256"] }

Available feature flags include: "ristretto", "p256", "k256" and "p384".

Usage

Once a group is selected (following standard elliptic-curve conventions, is considered an additive group), we can distinguish two main components:

  1. Points: Elements of . If , then as well. Operations on points (e.g. addition, scalar multiplication) are typically more expensive than on scalars.

  2. Scalars: Elements of , where is the order of the group . Scalars represent integer multipliers. For example, multiplying a point by (i.e., ) is defined as , and more generally represents the sum of added to itself -times.

These two structures support standard algebraic operations and are the basis for cryptographic schemes like Diffie–Hellman and digital signatures.

Example

First, we import a backend implementation (in this case, RistrettoGroup) as well as the traits GroupPoint and GroupScalar, which provide operations over points and scalars, respectively:

use dlog_group::{
    ristretto::{RistrettoGroup}, 
    group::{GroupPoint, GroupScalar}
};

We additionally import the rand crate to generate a random seed (rng) which we are going to use to generate a scalar r.

use rand;
let mut rng = rand::thread_rng();

Finally, let’s use the standard generator of the RistrettoGroup, perform some basic operations, and verify that the following holds:

let G = RistrettoGroup::generator();
let r = RistrettoGroup::scalar_random(&mut rng);

let r_G = G * &r;
let r1_G = G + &r_G;

assert_eq!(r1_G - &r_G, G);

Developer Guide


Group Trait

At the core of dlog-group is the Group trait, which defines the behavior expected from any prime-order group. This includes core group operations (such as addition, scalar multiplication, identity, equality), as well as serialization and size-related properties.

To extend dlog-group with support for a new group backend, you need to implement the following traits:

  • GroupScalar: Represents scalars from the field . You must specify their size and how to generate a random scalar using a cryptographically secure rng (i.e., one implementing CryptoRng).

  • GroupPoint: Represents elements of the group. This trait depends on GroupScalar and requires you to define the size of a point and implement scalar multiplication and point related operations.

  • Group: The main trait that binds GroupPoint and GroupScalar together into a single group definition.

Once these are implemented, your group can be used interchangeably with existing ones like RistrettoGroup, P256Group, or others, benefiting from the abstraction provided by the library.

It is recommended to include proper testing within any module that introduces new functionality. Additionally, if comparing performance is of interest, you can add benchmarks in the file benches/group_bench.rs, at the end of the file you can find examples of how the benchmarking macros (which take advantage of the Group trait) are used.

Performance


We report the timings of the main operations for each supported curve, where and . Note that performance is not the only metric to consider when choosing a curve, for example, P384 offers a higher security level (in bits) compared to the others. The data below was collected on an Intel® Core™ Ultra 7 165H and is represented in nanoseconds (ns).

OperationRistrettoK256P256P384
24,16829,40790,251379,02
139.93172.77265.80762.73
17.2638.73788.889414.125
60.12724.54545.44046.204

Introduction


dlog-sigma-primitives is a Rust crate offering discrete logarithm based cryptographic building blocks over elliptic curve groups. Group arithmetic and encodings are abstracted via the companion dlog-group crate, so the same protocols can be instantiated over any supported group.

Cryptographic model

Let be a cyclic group of prime order with generator , in this documentation we assume it written multiplicatively even if the implementation is written additively. Secrets and randomness are sampled from ; public elements live in . All statements and proofs in this crate are expressed as relations among discrete logarithms in . Security relies on the standard hardness of the discrete logarithm problem in and, where required, on DDH style indistinguishability. Non-interactive proofs are obtained from Sigma protocols using the Fiat-Shamir transform in the random oracle model, with challenge values derived from domain separated transcripts using the merlin crate.

Design goals

  • Composable. Proofs share uniform traits so that complex statements can be built easily.
  • Explicit transcripts. Every challenge is derived from a transcript with clear domain separation.
  • Group agnostic core. Protocol logic is independent of a particular curve; concrete groups are supplied by dlog-group (e.g., P 256 via the p256 feature).

User Guide


Installation

dlog-sigma-primitives is published on crates.io. It depends on a cryptographic group implementation, typically provided by a backend like dlog-group, which the crate already uses internally, so you don't need to add it as a dependency yourself unless you want to use it directly.

Add via Cargo:

cargo add dlog-sigma-primitives --features p256

Or add entries manually to your Cargo.toml (replace the version with the latest on crates.io):

[dependencies]
dlog-sigma-primitives = { version = "x.y.z", features = ["p256"] }

Notes:

  1. serde is a regular dependency of this crate. Types that are safe to serialize implement Serialize and Deserialize with no feature flag.
  2. Select exactly one concrete group via a crate feature on dlog-sigma-primitives (for example p256). These features forward to the underlying dlog-group backend.
  3. You only need a direct dlog-group dependency if you plan to call its APIs or need fine grained control over its own features beyond what this crate forwards.
  4. Randomness is provided via rand_core; transcripts and Fiat-Shamir challenges use merlin. These are regular dependencies and require no special configuration.

API documentation are available online:

  • Crate page on crates.io: https://crates.io/crates/dlog-sigma-primitives
  • API docs on docs.rs: https://docs.rs/dlog-sigma-primitives

Supported Algorithms

  1. ElGamal encryption (modified and exponential).

    • Modified ElGamal: a rerandomizable ElGamal variant tailored to verifiable shuffles and mixnets. It exposes ciphertext and randomness structures convenient for proof composition. [JCJ02]
    • Exponential ElGamal: plaintexts are represented in the exponent, enabling linear relations on messages to be proven with compact Sigma protocols.
  2. Pedersen commitments.

    • Additively homomorphic commitments of the form , with binding under DL in G and perfect hiding for uniformly random . [TPP91]
    • Designed to compose with the proof system below.
  3. Sigma protocols and non interactive zero knowledge proofs for DL relations.

    • Schnorr type proofs for knowledge of discrete logs and linear relations among logs. [CS97]
    • Relation specific statements used in the crate include:
      • Zero plaintext proofs for ElGamal ciphertexts, i.e., proofs that a ciphertext encrypts m = 0 without revealing the randomness.
      • Equality of discrete logs across independent bases.
      • Disjunctive (OR) proofs for alternative witnesses.
      • Designated verifier proofs that bind verification to a verifier secret. [JSB96]
    • All proofs are rendered non interactive via Fiat Shamir using merlin for transcript construction and challenge derivation. [FS86]

Modified ElGamal


Modified ElGamal [JCJ02] is a public key encryption scheme over a cyclic group of prime order that introduces a two-dimensional secret key and a three-component ciphertext. The change preserves the core guarantees of classical ElGamal (IND-CPA under DDH, rerandomizability, and homomorphism) while making the ciphertext structure more convenient for zero-knowledge proofs, shuffles, and threshold-style workflows.

Mathematical setting

Let be a cyclic group of prime order with independent generators .

  • Secret key: sampled uniformly at random.
  • Public key: .

Encryption of :

  1. Sample uniformly at random.
  2. Output ciphertext where

Decryption with secret key :

Correctness follows since:

Homomorphism

For any two ciphertexts and , Thus Modified ElGamal is multiplicatively homomorphic.

When messages are represented in the exponent, i.e., for a third fixed generator , then which induces additive homomorphism on exponents. Recovering from requires solving a discrete logarithm and is feasible only for small message domains.

Rerandomization

Given , any party can produce a distribution-identical ciphertext on the same plaintext by sampling in and outputting Rerandomization preserves correctness and hides .

Applications

  • Verifiable shuffles and mix-nets: ciphertexts can be permuted and rerandomized while preserving plaintexts.
  • Threshold workflows: the split structure of the secret key and the explicit randomness terms simplify share verifications.
  • Privacy-preserving systems: voting, sealed-bid auctions, credential systems, and any setting that benefits from efficient NIZKs over ElGamal relations.

Example

The crate is generic over a group backend. For documentation builds, select exactly one backend feature for the library (for example, p256 or ristretto). The alias Curve refers to the selected backend in this build.

// In Cargo.toml of this doc build:
// dlog-sigma-primitives = { version = "x.y.z", features = ["p256"] }

use rand_core::OsRng;
use dlog_sigma_primitives::prelude::*;

// The library exposes a concrete backend alias selected by features:
// type Curve = dlog_group::<backend>::Group;
// All APIs remain generic; Curve is provided for convenience.

fn main() {
let mut rng = OsRng;
// (sk, pk) sampled in the selected Curve
let params = ElGamalParams::<Curve>::new(&mut rng);
let (sk, pk) = KeyPair::<Curve>::new_from_params(&params, &mut rng).into_tuple();

// Sample a random message
let m = Curve::generator() * Curve::scalar_random(&mut rng);

// Encrypt and decrypt
let (ct, _r) = pk.encrypt(m, &params, &mut rng).into_tuple();

let m_dec = sk.decrypt(&ct);

assert_eq!(m, m_dec);
}

Pedersen Commitments


Pedersen commitments [TPP91] let a committer bind to a value while keeping it hidden, and later open it for verification. The scheme has two core properties:

  • Perfect hiding: the commitment leaks no information about the message.
  • Computational binding: after committing, it is infeasible to open to a different message assuming the hardness of discrete logarithm in the chosen group.

Mathematical setting

Let be a cyclic group of prime order with two independent generators in . For binding, no party should know . Messages and randomness are scalars in .

To commit to with randomness , compute

The pair is an opening of . Verification checks

Multi-message variant. For generators and message vector with randomness , define

Correctness is immediate from group laws.

Properties

  • Perfect hiding. For fixed , the distribution of is uniform in (because is uniform and independent of ). Hence reveals nothing about .

  • Computational binding. If an adversary finds two distinct openings for the same commitment: then . If , this reveals , contradicting the assumption that is unknown. If , then follows immediately. Thus binding reduces to the discrete logarithm hardness in together with the unknown-log relationship between and .

  • Additive homomorphism. For commitments and , . The multi-message variant is likewise additively homomorphic.

These algebraic properties make Pedersen commitments ideal for zero-knowledge proofs about sums, equalities, and linear relations among hidden values.

Applications

  • Sealed values: commit now, reveal later (e.g., bids, choices, randomness beacons).
  • Consistency checks: prove equality of hidden values across systems or that sums match.
  • Privacy-preserving protocols: a standard building block for NIZKs, voting, mix-nets, and confidential transactions.

Example


use dlog_sigma_primitives::pedersen::commitment::{ExtendedPedersen, Parameters};
use dlog_sigma_primitives::prelude::*;
use core_rng::OsRng;

fn main() {
let mut rng = OsRng;
// Choose a maximum supported message vector length and derive generators.
let list_len = 50;
let params = Parameters::<Curve>::new(list_len, &mut rng);

// Sample 40 messages (scalars) to commit.
let messages: Vec<<Curve as GroupScalar>::Scalar> =
  (0..40u64).map(|_| Curve::scalar_random(&mut rng)).collect();

// Variable-time, parallelized commitment (use const_commit for constant-time needs).
let (com, r) = ExtendedPedersen::var_commit(&params, &messages, &mut rng).unwrap().open();

// Verify with the provided opening (messages and randomness).
assert!(com
    .verify(&params, &messages, &r)
    .is_ok());
}

Notes:

  • Parameters should be sampled so that the generators have unknown discrete-log relation.
  • ExtendedPedersen retains the randomness r, which is useful when composing zero-knowledge proofs. The bare Pedersen type contains only the commitment element Com.
  • If constant-time behavior is required, prefer constant-time scalar multiplications (const_commit).

Zero-Knowledge Proofs


A Zero-Knowledge Proof (ZKP) is a cryptographic protocol that allows a prover to convince a verifier that a statement is true without revealing any additional information beyond the validity of the statement itself.

The concept was introduced in the 1980s by Goldwasser, Micali, and Rackoff [GMR85], who formalized the idea of proving statements while preserving secrecy. Since then, ZKPs have become a central tool in modern cryptography.

Every zero-knowledge proof must satisfy three core properties:

  • Completeness: If the statement is true and both parties follow the protocol, the verifier will be convinced.

  • Soundness: If the statement is false, no cheating prover can convince the verifier except with negligible probability.

  • Zero-Knowledge: The proof reveals nothing beyond the truth of the statement. A simulator could produce an indistinguishable transcript without access to the secret.

This crate organizes all discrete-logarithm proofs around a single abstraction: Sigma protocols, and it is made non-interactive via Fiat–Shamir using merlin transcripts. This page explains the model, the protocol flow and what the SigmaProtocol trait guarantees. Concrete implemented proofs (Zero, Equality, OR, etc.) are merely instances of the same pattern.

The goal is simple: write each relation once in a uniform interface, get transcript handling for free, and compose proofs safely.

What is a Sigma protocol?

A Sigma protocol is a 3-move public-coin protocol for proving knowledge of a witness to a public statement in some relation . The moves are:

  1. Commit: the prover sends a commitment computed from fresh randomness and the statement .
  2. Challenge: the verifier samples and sends a random scalar .
  3. Response: the prover returns a response computed from .

Finally, the verifier accepts if a fixed algebraic check holds, typically of the form

For discrete logs, is a group element or tuple of elements, is a scalar in , and is a linear combination of the witness and the commitment randomness.

A classic example, and fundamental building block is the Sigma-protocol for proving knowledge of a discrete logarithm:

  • Setup: Let be a cyclic group of prime order with generator . The prover knows a secret and the public value . The statement is: “I know such that .”

  • Protocol:

    1. Commit: The prover samples and sends to the verifier.
    2. Challenge: The verifier sends a random .
    3. Response: The prover replies with .
  • Verification: The verifier checks

This protocol is complete, sound (under the hardness of discrete log), and zero-knowledge.

From interactive to non-interactive: Fiat–Shamir

Interactive proofs are often turned into non-interactive proofs using the Fiat–Shamir heuristic [FS86]. Instead of receiving a random challenge from the verifier, the prover computes the challenge as a digest of the transcript and public information:

where is a secure hash function modeled as a random oracle. This transformation makes proofs publishable and universally verifiable, and in practice almost all deployed systems rely on it.

The heuristic must be applied carefully. The entire context must be hashed to avoid malleability, and domain separation should be used so that distinct protocols cannot interfere with each other. Only modern cryptographic hash functions should be used. In private protocols with interaction (for example, credential issuance or authentication with an authority) a nonce may also be included to prevent replay attacks. In contrast, public proofs must avoid nonces to prevent linkability, and should instead rely on globally shared context.

Fiat–Shamir is both powerful and essential: it eliminates interaction, enables public verifiability, and upgrades honest-verifier zero-knowledge protocols to full zero-knowledge in the random oracle model, provided it is applied with the necessary care.

The SigmaProtocol trait

All proofs in this crate implement the same behavior so that Fiat–Shamir can be applied safely and uniformly. The contract below is the minimum needed to make non-interactive Sigma protocols correct by construction, composable, and auditable.

  • Public(x): Borrowed view of the entire public statement with a fixed encoding order. Deterministic absorption of ensures consistent transcript context and prevents malleability.

  • Witness(w): The prover's secret (e.g., exponent, opening, encryption randomness). In order to avoid disclosure it is always zeroized on drop.

  • State: Ephemeral randomness used to form commitments. It is consumed during complete() to prevent reuse and ensure fresh commitments in each proof instance.

  • Proof: Minimal serialized object containing what the verifier needs to replay commitments and verify the relation.

  • Protocol methods (canonical order):

    1. absorb_public(x, transcript): absorb in the transcript.
    2. init(x, rng) -> State: sample fresh ephemeral randomness.
    3. commit(x, state, w, transcript): append all commitments; no challenge yet.
    4. complete(state, w, transcript) -> Proof: derive c from the transcript, compute responses, serialize proof, consume state.
    5. update_transcript(proof, transcript): verifier-side replay of commitments from the proof.
    6. verify_relation(x, proof, transcript): recompute c and check the algebraic equation.
  • One-shot helpers, to enforce the canonical sequence and reduce misuse in callers:

    • prove(x, w, transcript, rng)
    • verify(x, proof, transcript)

Transcript

  • Each protocol sets a unique, immutable DOMAIN.
  • Prover and verifier must call start_proof(DOMAIN, public, absorb_public) before any other transcript operation.
  • absorb_public appends the entire public statement once in a fixed order.
  • Commitments are then appended by commit. The challenge is derived only after all commitments have been absorbed.
  • The verifier must exactly mirror commit through update_transcript before deriving the challenge.

Proof helper trait

Every proof struct implements Proof by setting type Protocol = .... This exposes ergonomic one-shot helpers hiding the Transcript object while enforcing canonical order. For advanced use, call the protocol methods directly and pass an explicit transcript.

// Prover side
let proof = Zero::<Curve>::prove(public, &witness, &mut rng);

// Verifier side
proof.verify(public)?;

Applications

Zero-knowledge proofs are widely used whenever one must prove correctness without revealing the underlying secret. Common examples include:

  • Well-formedness proofs, showing that encrypted or committed values lie in a valid set.
  • Consistency checks, ensuring two hidden values are equal or satisfy a relation.
  • Privacy-preserving protocols, core of the classical scope for ZKPs such as anonymous credentials and voting systems.

Supported Proofs

This library includes a collection of zero-knowledge proofs that can be used as modular building blocks in cryptographic systems. Each proof enforces a specific algebraic property (e.g., equality of discrete logs, correct shuffling, or consistency with a reference value) and can be combined with others to enforce more complex constraints.

The table below summarizes the supported proofs, the guarantees they provide, and a representative application in e-voting systems:

Proof TypeWhat it ShowsExample Application in E-Voting
ZeroAn ElGamal ciphertext encodes the value zeroBuilding block for ballot validity and consistency checks
Disjunctive (OR)An ElGamal ciphertext encodes one value from a predefined setProving each selection is either 0 or 1
Exponential (Exp)Knowledge of the plaintext exponent in an exponential ElGamal ciphertextEncoding and proving selections as exponents
EqualityTwo group elements share the same discrete logarithm w.r.t. different basesLinking related ciphertexts for consistency
PlaintextProver knows the plaintext inside an ElGamal ciphertext (without revealing it)Ensuring the voter knows the vote they cast
Not Identity (NotId)An ElGamal ciphertext does not encrypt the group identityPreventing malformed or trivial ballot fields
Verifiable DecryptionAn ElGamal ciphertext has been correctly decrypted under a public key schemePublicly auditable tallying
Designated VerifierProof validity can be checked only by a specific verifier with secret dataRestricting credential checks to the voter
ShuffleA list of ElGamal ciphertexts was permuted and re-randomized correctlyVerifiable mixing of ballots in anonymization

Example

We show how to generate and verify a Zero proof. Examples for the other proofs are included in the API documentation. Thanks to the trait implementation, most proofs follows the exact same pattern.

use dlog_sigma_primitives::prelude::*;
use dlog_sigma_primitives::proofs::zero::{ZeroProtocol, ZeroPublicBorrowed};
let mut rng = OsRng;
fn main() {
let params: ElGamalParams<Curve> = ElGamalParams::new(&mut rng);
let (_sk, pk) = KeyPair::new_from_params(&params, &mut rng).into_tuple();

// Zero plaintext (group identity)
let (ct, r) = pk.encrypt(Curve::identity(), &params, &mut rng).into_tuple();

let public = ZeroPublicBorrowed::new(&pk, &params, &ct);

// Prover
let mut tr_p = Transcript::new(b"example");
let proof = ZeroProtocol::prove(public, &r, &mut tr_p, &mut rng);

// Verifier
let mut tr_v = Transcript::new(b"example");
ZeroProtocol::verify(public, &proof, &mut tr_v).expect("verification");
}