Discrete Logarithm

Overview

The discrete log module implements the baby-step giant-step algorithm for solving discrete logarithm problems in the Ristretto group. This is essential for decrypting twisted ElGamal ciphertexts, where messages are encoded as scalar exponents.

Problem Statement

Given a generator point G and a target point T, find the scalar x such that:

x * G = T

This module solves this problem efficiently for 32-bit unsigned integers using precomputation and parallelization.

Key Concepts

Baby-Step Giant-Step Algorithm

The algorithm splits the search into two phases:

Precomputation (Giant Steps): Build a hash table of points {2^17 * i * G : i} for i = 0..2^16
Online Search (Baby Steps): For each j = 0..2^16, check if T - j*G is in the hash table

If found at (i, j), then x = 2^17 * i + j.

Performance Characteristics

Precomputation: One-time computation, stored as static data
Search Range: 32-bit unsigned integers (0 to 2^32 - 1)
Time Complexity: O(2^16) online operations
Memory: ~2 MB precomputed hash table

Core Types

DiscreteLog

Represents a discrete log problem instance.

pub struct DiscreteLog {
    pub target: RistrettoPoint,
    num_threads: Option<NonZeroUsize>,
    range_bound: NonZeroUsize,
    step_point: RistrettoPoint,
    compression_batch_size: NonZeroUsize,
}

Methods

Creating Instances

// Create instance for generator G (recommended)
pub fn new_for_g(target: RistrettoPoint) -> Self

Configuring the Solver

// Set number of threads (must be power of 2, max 65536)
pub fn num_threads(&mut self, num_threads: NonZeroUsize) -> Result<(), DiscreteLogError>

// Set compression batch size (max 65535)
pub fn set_compression_batch_size(
    &mut self,
    compression_batch_size: NonZeroUsize,
) -> Result<(), DiscreteLogError>

Solving

// Solve for 32-bit unsigned integer
pub fn decode_u32(self) -> Option<u64>

DiscreteLogError

Errors that can occur during configuration.

pub enum DiscreteLogError {
    DiscreteLogThreads,      // Invalid thread count
    DiscreteLogBatchSize,    // Invalid batch size
}

DecodePrecomputation

Precomputed hash table for the giant steps.

pub struct DecodePrecomputation(HashMap<[u8; 32], u16>)

// Global precomputed table for generator G
pub static DECODE_PRECOMPUTATION_FOR_G: LazyLock<DecodePrecomputation>

Usage Examples

Basic Discrete Log Solution

use solana_zk_sdk::encryption::discrete_log::DiscreteLog;
use curve25519_dalek::{
    constants::RISTRETTO_BASEPOINT_POINT as G,
    scalar::Scalar,
};

// The secret value we want to recover
let amount: u64 = 12345;

// Create the target point (amount * G)
let target = Scalar::from(amount) * G;

// Solve the discrete log
let instance = DiscreteLog::new_for_g(target);
let decoded = instance.decode_u32().unwrap();

assert_eq!(amount, decoded);

Multi-threaded Solving

use solana_zk_sdk::encryption::discrete_log::DiscreteLog;
use curve25519_dalek::{constants::RISTRETTO_BASEPOINT_POINT as G, scalar::Scalar};
use std::num::NonZeroUsize;

let amount: u64 = 55;
let target = Scalar::from(amount) * G;

// Create instance and configure for 4 threads
let mut instance = DiscreteLog::new_for_g(target);
instance.num_threads(4.try_into().unwrap()).unwrap();

// Solve using multiple threads
let decoded = instance.decode_u32().unwrap();
assert_eq!(amount, decoded);

Integration with ElGamal Decryption

use solana_zk_sdk::encryption::{
    elgamal::{ElGamalKeypair, ElGamal},
    discrete_log::DiscreteLog,
};

let keypair = ElGamalKeypair::new_rand();
let amount: u32 = 57;

// Encrypt
let ciphertext = keypair.pubkey().encrypt(amount);

// Decrypt returns a DiscreteLog instance
let discrete_log = keypair.secret().decrypt(&ciphertext);

// Solve the discrete log to recover the amount
let decoded_amount = discrete_log.decode_u32().unwrap();
assert_eq!(57, decoded_amount);

Edge Cases

use curve25519_dalek::{constants::RISTRETTO_BASEPOINT_POINT as G, scalar::Scalar};

// Amount 0
let instance = DiscreteLog::new_for_g(Scalar::from(0_u64) * G);
assert_eq!(instance.decode_u32().unwrap(), 0);

// Amount 1
let instance = DiscreteLog::new_for_g(Scalar::from(1_u64) * G);
assert_eq!(instance.decode_u32().unwrap(), 1);

// Max u32 value
let max_amount: u64 = (1_u64 << 32) - 1;
let instance = DiscreteLog::new_for_g(Scalar::from(max_amount) * G);
assert_eq!(instance.decode_u32().unwrap(), max_amount);

Configuring Batch Size

use std::num::NonZeroUsize;

let target = Scalar::from(1000_u64) * G;
let mut instance = DiscreteLog::new_for_g(target);

// Adjust compression batch size for performance tuning
instance.set_compression_batch_size(64.try_into().unwrap()).unwrap();

let decoded = instance.decode_u32().unwrap();
assert_eq!(1000, decoded);

Thread Configuration

let target = Scalar::from(100_u64) * G;
let mut instance = DiscreteLog::new_for_g(target);

// Valid thread counts (powers of 2)
instance.num_threads(1.try_into().unwrap()).unwrap();
instance.num_threads(2.try_into().unwrap()).unwrap();
instance.num_threads(4.try_into().unwrap()).unwrap();
instance.num_threads(8.try_into().unwrap()).unwrap();

// Invalid thread count (not power of 2)
let result = instance.num_threads(3.try_into().unwrap());
assert!(result.is_err());

Algorithm Details

Two-Level Search

The algorithm uses a 16/16 bit split:

High bits: Precomputed in hash table (2^16 entries)
Low bits: Computed online (2^16 iterations)

For a 32-bit value x = x_hi * 2^17 + x_lo:

Hash table contains: {(2^17 * x_hi * G) : x_hi} for x_hi ∈ [0, 2^16)
Online search checks: T - x_lo * G for x_lo ∈ [0, 2^16)
When match found: x = 2^17 * x_hi + x_lo

Parallelization

When using n threads:

Each thread searches a different starting point
Thread i starts at T - i*G
Each thread steps by -n*G instead of -G
Search space divided evenly among threads
First thread to find solution returns result

Batch Compression

Ristretto points are compressed in batches for efficiency:

RistrettoPoint::double_and_compress_batch(&batch_points)

Default batch size is 32, configurable via set_compression_batch_size().

Performance Tuning

Thread Count

More threads can improve performance for large values:

let mut instance = DiscreteLog::new_for_g(target);

// Single-threaded (default)
instance.decode_u32();  // Slowest for large values

// Multi-threaded
instance.num_threads(4.try_into().unwrap()).unwrap();
instance.decode_u32();  // Faster

instance.num_threads(8.try_into().unwrap()).unwrap();
instance.decode_u32();  // Even faster

Trade-offs:

More threads = faster for large values
More threads = higher CPU usage
More threads = diminishing returns beyond 8-16

Batch Size

Larger batch sizes can improve throughput:

let mut instance = DiscreteLog::new_for_g(target);

// Small batches (less memory, more overhead)
instance.set_compression_batch_size(16.try_into().unwrap()).unwrap();

// Default
instance.set_compression_batch_size(32.try_into().unwrap()).unwrap();

// Large batches (more memory, less overhead)
instance.set_compression_batch_size(256.try_into().unwrap()).unwrap();

Typical Performance

Informal measurements on modern hardware:

Small values (< 2^16): < 1 second
Medium values (2^16 - 2^24): 1-10 seconds
Large values (2^24 - 2^32): 10-60 seconds
Multi-threaded: 2-4x speedup with 4-8 threads

Security Considerations

Not Constant-Time

The implementation is not constant-time:

Uses hash tables (variable access time)
Short-circuits on solution (variable iteration count)
Batching introduces timing variations
Multi-threading adds non-determinism

This may allow timing side-channel attacks in adversarial settings.

Information Leakage

Execution time reveals information about the solution:

Small values decrypt faster
Large values take longer
Thread count affects timing

In protocols requiring privacy, consider:

Adding random delays
Using fixed-time operations
Limiting value range

Range Limitations

Only supports 32-bit unsigned integers:

Values > 2^32 - 1 will fail to decrypt
Negative values not supported
Returns None for out-of-range values

Precomputation

The hash table is precomputed and embedded in the binary:

pub static DECODE_PRECOMPUTATION_FOR_G: LazyLock<DecodePrecomputation> =
    LazyLock::new(|| {
        static DECODE_PRECOMPUTATION_FOR_G_BINCODE: &[u8] =
            include_bytes!("decode_u32_precomputation_for_G.bincode");
        bincode::deserialize(DECODE_PRECOMPUTATION_FOR_G_BINCODE)
            .unwrap_or_default()
    });

Precomputation Contents

2^16 = 65,536 hash table entries
Each entry: 32-byte point → 2-byte index
Total size: ~2 MB
Computed for generator G only

Regenerating Precomputation

The precomputation is generated by test code:

#[test]
fn test_serialize_decode_u32_precomputation_for_G() {
    let decode_u32_precomputation_for_G = decode_u32_precomputation();
    // Serializes to src/encryption/decode_u32_precomputation_for_G.bincode
}

This test will panic if the precomputation needs to be regenerated.

Advanced Usage

Custom Configuration

use std::num::NonZeroUsize;

let target = Scalar::from(5000000_u64) * G;
let mut instance = DiscreteLog::new_for_g(target);

// Configure for high-performance decryption
instance.num_threads(8.try_into().unwrap()).unwrap();
instance.set_compression_batch_size(128.try_into().unwrap()).unwrap();

// Solve
let start = std::time::Instant::now();
let decoded = instance.decode_u32().unwrap();
let duration = start.elapsed();

println!("Decoded {} in {:?}", decoded, duration);

Handling Decryption Failures

let keypair = ElGamalKeypair::new_rand();
let ciphertext = keypair.pubkey().encrypt(100_u64);

// Decrypt with wrong key produces unsolvable discrete log
let wrong_keypair = ElGamalKeypair::new_rand();
let discrete_log = wrong_keypair.secret().decrypt(&ciphertext);

// decode_u32 returns None for unsolvable instances
assert!(discrete_log.decode_u32().is_none());

Comparison with Other Methods

Method	Time Complexity	Space	Range
Baby-step Giant-step	O(√n)	O(√n)	Full
Pollard’s Rho	O(√n)	O(1)	Full
Brute Force	O(n)	O(1)	Limited
Lookup Table	O(1)	O(n)	Limited

This implementation uses baby-step giant-step with:

Precomputed table (giant steps)
Online search (baby steps)
Parallel search (multiple threads)
Batch compression (optimization)

Optimal for repeated decryption of 32-bit values.

API Reference

Modules

Overview

Problem Statement

Key Concepts

Baby-Step Giant-Step Algorithm

Performance Characteristics

Core Types

DiscreteLog

Methods

DiscreteLogError

DecodePrecomputation

Usage Examples

Basic Discrete Log Solution

Multi-threaded Solving

Integration with ElGamal Decryption

Edge Cases

Configuring Batch Size

Thread Configuration

Algorithm Details

Two-Level Search

Parallelization

Batch Compression

Performance Tuning

Thread Count

Batch Size

Typical Performance

Security Considerations

Not Constant-Time

Information Leakage

Range Limitations

Precomputation

Precomputation Contents

Regenerating Precomputation

Advanced Usage

Custom Configuration

Handling Decryption Failures

Comparison with Other Methods

Build docs developers (and LLMs) love

API Reference

Modules

​Overview

​Problem Statement

​Key Concepts

​Baby-Step Giant-Step Algorithm

​Performance Characteristics

​Core Types

​DiscreteLog

​Methods

​DiscreteLogError

​DecodePrecomputation

​Usage Examples

​Basic Discrete Log Solution

​Multi-threaded Solving

​Integration with ElGamal Decryption

​Edge Cases

​Configuring Batch Size

​Thread Configuration

​Algorithm Details

​Two-Level Search

​Parallelization

​Batch Compression

​Performance Tuning

​Thread Count

​Batch Size

​Typical Performance

​Security Considerations

​Not Constant-Time

​Information Leakage

​Range Limitations

​Precomputation

​Precomputation Contents

​Regenerating Precomputation

​Advanced Usage

​Custom Configuration

​Handling Decryption Failures

​Comparison with Other Methods

Build docs developers (and LLMs) love

Overview

Problem Statement

Key Concepts

Baby-Step Giant-Step Algorithm

Performance Characteristics

Core Types

DiscreteLog

Methods

DiscreteLogError

DecodePrecomputation

Usage Examples

Basic Discrete Log Solution

Multi-threaded Solving

Integration with ElGamal Decryption

Edge Cases

Configuring Batch Size

Thread Configuration

Algorithm Details

Two-Level Search

Parallelization

Batch Compression

Performance Tuning

Thread Count

Batch Size

Typical Performance

Security Considerations

Not Constant-Time

Information Leakage

Range Limitations

Precomputation

Precomputation Contents

Regenerating Precomputation

Advanced Usage

Custom Configuration

Handling Decryption Failures

Comparison with Other Methods