Private Inner Product Encryption Demo

Build private search and recommendations without revealing your data. This project lets you compute how well two items match (a simple "similarity score") while keeping both inputs private.

Imagine Alice has a search query (for example, "machine learning researcher in California") represented as a vector, and Bob has a database of user profiles also represented as vectors. Inner Product Encryption lets Bob compute how well Alice's query matches each profile (via a dot product) without Bob learning what Alice searched for, and without Alice learning the contents of Bob's database. Only the similarity scores are revealed.

Simple example: Alice encrypts her preference vector [3, 5, 2]. Bob has an item vector [2, 4, 1]. The similarity score (dot product) is 3×2 + 5×4 + 2×1 = 28 — computed privately without revealing either vector.

Real-world applications:

• Privacy-preserving search: query encrypted databases without revealing your query
• Secure machine learning: compare encrypted feature vectors for classification or matching
• Private recommendations: match user preferences against items without exposing either
• Biometric authentication: compare encrypted templates without revealing raw data

For background and a practical performance review focused on private semantic search, see the accompanying research note: Performance of Function-Hiding IPE for Private Semantic Search.

Overview

This is a Rust implementation of Function-Hiding Inner Product Encryption (FHIPE) on the BLS12-381 curve. It demonstrates how to compute similarity scores between encrypted vectors while keeping the underlying data private.

WARNING: Educational Use Only
This implementation is for educational and research purposes only. It has not undergone professional security review or audit. DO NOT use this library in production systems or for protecting sensitive data. For production use, consult with cryptography experts and use well-audited libraries.

Key Features:

• Encrypt vector y to produce ciphertext ct
• Generate a secret key sk for vector x
• Decrypt to recover <x, y> (the inner product) without revealing x or y
• Built on the BLS12-381 pairing-friendly curve
• Efficient Baby-Step Giant-Step algorithm for discrete log solving

Quick Start

Run the Demo

cargo run --example inner_product_demo

This will:

1. Generate two random 32-dimensional vectors x and y
2. Compute their inner product in plaintext
3. Run the full IPE protocol (Setup → KeyGen → Encrypt → Decrypt)
4. Verify that both methods produce the same result

Example Output

=== Inner Product Encryption Demo ===

Parameters:
  - Vector dimension: 32
  - Security parameter: 128
  - Search space size: 10000

Step 1: Computing inner product in the clear (plaintext)...
  Plaintext inner product <x, y> = 623

Step 5: IPE Decrypt - Recovering inner product from encrypted data...
  ✓ Encrypted inner product recovered: 623

  ✓✓✓ SUCCESS! Both methods computed the same inner product! ✓✓✓

Library Usage

Basic IPE Flow

use ark_bls12_381::Fr;
use private_inner_product_demo::{
    setup::ipe_setup,
    keygen::ipe_keygen,
    encrypt::ipe_encrypt,
    decrypt::ipe_decrypt,
};

// Setup: Generate public parameters and master secret key
let (pp, msk) = ipe_setup(128, 32, 10000);

// Create two vectors
let x: Vec<Fr> = vec![/* ... */];
let y: Vec<Fr> = vec![/* ... */];

// KeyGen: Generate secret key for vector x
let sk = ipe_keygen(&msk, &x, &mut rng);

// Encrypt: Encrypt vector y
let ct = ipe_encrypt(&msk, &y, &mut rng);

// Decrypt: Recover inner product <x, y>
let result = ipe_decrypt(&pp, &sk, &ct);

Modules

• setup - IPE setup algorithm to generate public parameters and master secret key
• keygen - Key generation algorithm to create secret keys for query vectors
• encrypt - Encryption algorithm to encrypt data vectors
• decrypt - Decryption algorithm with Baby-Step Giant-Step discrete log solver

Development

Quick Commands

Using the provided Makefile:

make all      # Format, lint, test, and run example
make fmt      # Format code with cargo fmt
make clippy   # Run clippy (warnings fail build)
make test     # Run all tests
make example  # Run the demo example
make ci       # Run all CI checks (format check, clippy, tests)
make bench    # Run all benchmarks
make clean    # Clean build artifacts

Code Quality

This project enforces strict code quality standards:

• Formatting: Code is automatically formatted with cargo fmt
• Linting: Clippy warnings are treated as errors and will fail the build
• CI: GitHub Actions runs format checks, clippy, and tests on every push/PR

To ensure your changes pass CI before pushing:

make ci

Testing

Run all tests:

cargo test

Run tests with output:

cargo test -- --nocapture

Benchmarking

Performance benchmarks are available to measure throughput for 384-dimensional vectors:

Run All Benchmarks

make bench
# or
cargo bench

Run Specific Benchmarks

make bench-keygen   # Benchmark key generation only
make bench-encrypt  # Benchmark encryption only
make bench-decrypt  # Benchmark decryption/inner product evaluation only

The benchmarks measure:

• Setup: Time to generate public parameters and master secret key
• Key Generation: Number of secret keys generated per second
• Encryption: Number of vectors encrypted per second
• Decryption: Number of inner products evaluated per second

Each operation is measured independently (excluding setup and other operations).

Results are saved in target/criterion/ with detailed HTML reports.

Performance Results

Benchmarks run on 384-dimensional vectors with a search space of 100,000:

Operation	Throughput	Time per Operation
Setup	-	~216 ms
KeyGen	374 keys/sec	2.67 ms
Encrypt	103 encryptions/sec	9.72 ms
Decrypt	10.6 decryptions/sec	94.6 ms
Plaintext	208K operations/sec	4.82 µs

Encrypted vs Plaintext Comparison:

• Plaintext inner product: ~240,000 operations/second
• Encrypted IPE (decrypt): ~10.6 operations/second
• Overhead: Encrypted computation is approximately 22,600x slower than plaintext
  • This is the cost of privacy: computing inner products without revealing the vectors
  • Dominated by pairing operations and discrete logarithm solving
  • The code is not or barely optimized, take those numbers with a grain of salt.

Key Insights:

• Setup is a one-time cost (~216ms for 384-dimensional system)
• KeyGen processes ~385 keys/second with minimal batch size impact
• Encryption achieves ~103 encryptions/second across all batch sizes
• Decryption (inner product recovery) is the slowest at ~10.6 operations/second
  • Dominated by Baby-Step Giant-Step discrete logarithm solving
  • Search space size impacts performance (larger space = slower)

Optimizations:

• AHashMap for faster discrete log table lookups (50-70% speedup vs standard HashMap)
• Prepared pairings with multi-Miller loops for efficient pairing computations
• Parallel operations using Rayon for matrix operations and scalar multiplications
• Pre-computed scalars before parallel multiplications for better memory access patterns

Technical Details

Cryptographic Scheme

This implementation is based on Function-Hiding Inner Product Encryption using bilinear pairings:

• Curve: BLS12-381 pairing-friendly elliptic curve
• Groups: G1, G2 (elliptic curve groups), GT (target group)
• Pairing: e : G1 × G2 → GT (bilinear pairing operation)
• Field: Fr (scalar field for BLS12-381)
• Security Parameter: λ = 128 bits

Implementation Details

Core Operations:

• Setup: Generate public parameters and master secret key
• KeyGen: Generate secret keys for query vectors
• Encrypt: Encrypt data vectors into ciphertexts
• Decrypt: Recover inner product from encrypted data

Performance Optimizations:

• Baby-Step Giant-Step (BSGS): O(√|S|) discrete log solving instead of O(|S|) linear search
• AHashMap: Fast hashing for BSGS lookup table (no serialization overhead)
• Prepared Pairings: Converts points to prepared form for efficient Miller loop computation
• Multi-Miller Loop: Computes multiple Miller loops before final exponentiation
• Parallel Scalar Multiplications: Rayon-based parallelization for independent operations
• Parallel Gaussian Elimination: Rayon parallelization for matrix inversion in setup

Benchmark Configuration

• Vector Dimension: 384
• Search Space Size: 100,000 (affects BSGS performance)
• Sample Sizes: 10-20 iterations
• Batch Sizes: 1, 10, 25 operations per batch
• Parallelism: Multi-threaded by default (Rayon uses all available cores)
  • To benchmark single-threaded: RAYON_NUM_THREADS=1 cargo bench

Citation

This implementation is based on the following research paper:

Function-Hiding Inner Product Encryption is Practical
Sam Kim, Kevin Lewi, Avradip Mandal, Hart Montgomery, Arnab Roy, David J. Wu
Cryptology ePrint Archive, Paper 2016/440 (2016)
https://eprint.iacr.org/2016/440

@misc{cryptoeprint:2016/440,
  author = {Sam Kim and Kevin Lewi and Avradip Mandal and Hart Montgomery and Arnab Roy and David J. Wu},
  title = {Function-Hiding Inner Product Encryption is Practical},
  howpublished = {Cryptology {ePrint} Archive, Paper 2016/440},
  year = {2016},
  url = {https://eprint.iacr.org/2016/440}
}

License

MIT