Homomorphic Lookup

A Swift demonstration of KeywordPIR (Keyword Private Information Retrieval) using Apple's HomomorphicEncryption and PrivateInformationRetrieval frameworks. This project showcases how to perform encrypted keyword lookups on a database without revealing which keyword was searched.

What is KeywordPIR?

KeywordPIR is a cryptographic protocol that allows a client to retrieve a value by searching for a keyword (e.g., "Alice") from a database server without revealing which keyword was searched. The server learns nothing about the query, providing strong privacy guarantees for the client.

Unlike traditional database queries where the server sees exactly what you're searching for, KeywordPIR uses homomorphic encryption to keep your queries completely private.

What This Project Does

This demonstration:

1. Creates an encrypted keyword database with 999 entries (names → contact information)
2. Generates encrypted queries for specific keywords without revealing which keyword
3. Computes encrypted responses on the server side using homomorphic operations
4. Decrypts the results client-side to retrieve the contact information
5. Verifies correctness including testing non-existent keywords (returns nil)

Key Insight: The server processes your encrypted query and returns an encrypted response, but learns absolutely nothing about which keyword you searched for.

Key Features

• Uses KeywordPIR with MulPir (Multiplicative PIR) protocol
• Cuckoo hashing with 2 hash functions for keyword-to-index mapping
• Encryption based on BFV scheme with UInt32 precision
• 999 keyword entries demonstrating scalability
• Automatic generation of required Galois elements for polynomial transformations
• Demonstrates private database access without server learning the query
• Includes detailed timing information for all operations
• Properly handles non-existent keywords (returns nil)
• Uses Protocol Buffers for efficient serialization (when persistence is enabled)

Real-World Use Cases

• Contact lookup - Search for contacts without revealing who you're looking for
• Caller ID - Like Apple's privacy-preserving caller ID lookup
• Private directories - Search employee directories, phone books, etc.
• Credential checking - Check if a username/email exists without revealing which one
• Privacy-preserving search - Any scenario where query privacy is critical

Requirements

• macOS
• Xcode
• Apple's HomomorphicEncryption framework
• Apple's PrivateInformationRetrieval framework
• SwiftProtobuf framework

Usage

Run the project in Xcode or via command line:

swift run

The program will:

1. Generate 999 unique keywords (names)
2. Create encrypted keyword database mapping names to contact info
3. Perform two random keyword lookups with full timing
4. Test a non-existent keyword to verify nil handling

How It Works

KeywordPIR Protocol Steps

1. Keyword Database Setup:

   • Convert keyword-value pairs to KeywordValuePair objects
   • Use cuckoo hashing to map keywords to indices
   • Process database using KeywordPirServer

2. Query Generation (Client):

   • Client creates encrypted query for target keyword (e.g., "Alice")
   • Query is fully encrypted - server cannot determine the keyword
   • Uses KeywordPirClient with secret key

3. Response Computation (Server):

   • Server performs homomorphic computation on encrypted query
   • Server learns NOTHING about which keyword was queried
   • Returns encrypted response using evaluation key

4. Decryption (Client):

   • Client decrypts response using secret key
   • Retrieves the value (contact info) or nil if keyword not found

Key Functions

• setupKeywordPirDatabase(keywordValues:): Creates encrypted keyword database and generates keys
• generateQuery(keyword:...): Client generates encrypted query for a keyword
• computeResponse(query:...): Server computes encrypted response (without learning the keyword)
• decryptResponse(response:keyword:...): Client decrypts response to get the value

Encryption Parameters

• Polynomial degree: 4096 (demo parameters - use 8192+ for production)
• Scheme: BFV (Brakerski-Fan-Vercauteren) with UInt32
• Plaintext modulus: logt_5
• Coefficient modulus: [27, 28, 28]
• Cuckoo hashing: 2 hash functions, 0.9 load factor
• Dimensions: 2D for performance optimization

Example Output

Starting KeywordPIR Encrypted Lookup Demo
========================================

Creating keyword database...
Keyword database contains 999 entries

1. Setting up encrypted keyword database...
   Configuring KeywordPIR with cuckoo hashing...
   Processing KeywordPIR database...
   ✓ Database processed (1.04s)
   Generating secret key...
   ✓ Secret key generated (0.10s)
   Generating evaluation key...
   ✓ Evaluation key generated (3.07s)
   ✓ Total setup time (5.95s)
   ✓ Keyword database ready

2. Performing private lookup for 'Bob12'...
   [Client] Creating KeywordPIR client...
   [Client] Generating encrypted query for keyword 'Bob12'...
   [Client] Query generated (keyword hidden from server)
   ✓ Query generated (0.126s)
   [Server] Computing encrypted response...
   [Server] (Server does NOT know which keyword was queried)
   [Server] Response computed and sent to client
   ✓ Server computed response (7.089s)
   [Client] Decrypting response...
   [Client] Decryption complete
   ✓ Result decrypted (0.117s)
   ✓ Total lookup time (7.333s)

   Result for 'Bob12':
   Contact: +1-555-0589 | Email: bob12@example.com

3. Performing second lookup for 'Gina12'...
   [Client] Creating KeywordPIR client...
   [Client] Generating encrypted query for keyword 'Gina12'...
   [Client] Query generated (keyword hidden from server)
   ✓ Query generated (0.128s)
   [Server] Computing encrypted response...
   [Server] (Server does NOT know which keyword was queried)
   [Server] Response computed and sent to client
   ✓ Server computed response (7.596s)
   [Client] Decrypting response...
   [Client] Decryption complete
   ✓ Result decrypted (0.120s)
   ✓ Total lookup time (7.843s)

   Result for 'Gina12':
   Contact: +1-555-0618 | Email: gina12@example.com

4. Testing non-existent keyword 'Zorro'...
   [Client] Creating KeywordPIR client...
   [Client] Generating encrypted query for keyword 'Zorro'...
   [Client] Query generated (keyword hidden from server)
   [Server] Computing encrypted response...
   [Server] (Server does NOT know which keyword was queried)
   [Server] Response computed and sent to client
   [Client] Decrypting response...
   [Client] Decryption complete
   ✓ Correctly returned nil for non-existent keyword

========================================
Total execution time: 28.93s
========================================
KeywordPIR Demo Complete!

Privacy Guarantees

What IS Protected ✅

• Which keyword you query - Completely hidden from server
• Query pattern - No way to link multiple queries together
• The retrieved value - Only you can decrypt it
• Quantum resistance - Based on lattice cryptography (Ring-LWE)

What is NOT Protected ❌

• That you made a query - Server knows someone queried (but not what)
• Query timing - Server can see when queries happen
• Approximate database size - Visible from configuration
• Query frequency - How often you make queries

Security Properties

Server Privacy (Information Theoretic): The server learns absolutely nothing about which keyword you're querying. Even with infinite computing power, the server cannot determine your query.

Response Correctness: You always get the correct value for your keyword. Returns nil for non-existent keywords.

Encryption Strength: Uses BFV homomorphic encryption based on Ring-LWE, believed to be quantum-resistant.

Technical Details

• Protocol: KeywordPIR wrapping IndexPIR with MulPir
• Scheme: BFV (Brakerski-Fan-Vercauteren) homomorphic encryption
• Hash Table: Cuckoo hashing with 2 hash functions
• Database dimensions: 2D for optimized BFV performance
• Uneven dimensions: Enabled for faster ciphertext-ciphertext multiplication
• Key compression: Disabled for fastest server performance
• Serialization: Protocol Buffers for efficient key storage
• Database size: 999 keyword-value pairs

Security Note

⚠️ This is a demonstration project using parameters suitable for testing:

• Polynomial degree: 4096 (fast but lower security)
• For production use: Use degree 8192 or 16384 for stronger security
• Implement key rotation and secure key storage
• Add TLS/SSL for transport security
• Consider rate limiting to prevent timing attacks