The KKRT protocol is a seminal private set intersection (PSI) construction that achieves fast, low-communication secure computation by combining OT extension with Cuckoo hashing. It operates in the semi-honest security model, where parties follow the protocol correctly but may attempt to learn additional information from the transcript, providing an optimal balance of practical efficiency and strong privacy guarantees for collaborative analytics.
Glossary
KKRT Protocol
A highly efficient semi-honest private set intersection (PSI) protocol by Kolesnikov, Kumaresan, Rosulek, and Trieu that uses OT extension and Cuckoo hashing to achieve fast, low-communication private set intersection.
EFFICIENT SEMI-HONEST PSI
What is KKRT Protocol?
The KKRT protocol is a highly efficient private set intersection (PSI) protocol designed for the semi-honest security model, introduced by Kolesnikov, Kumaresan, Rosulek, and Trieu in 2016.
Its core innovation lies in using the IKNP OT extension protocol to efficiently realize a large number of oblivious transfers, which are then structured via Cuckoo hashing to compare sets with minimal computational and communication overhead. This design made KKRT the fastest PSI protocol of its era, establishing a foundational performance baseline against which subsequent protocols like those based on vector OLE (VOLE) are measured.
PROTOCOL ARCHITECTURE
Key Features of KKRT
The KKRT protocol achieves high-speed private set intersection by combining OT extension, Cuckoo hashing, and efficient symmetric-key operations to minimize both computation and communication overhead.
01
OT Extension Foundation
KKRT builds on the IKNP OT extension protocol to efficiently generate a large number of oblivious transfers from a small number of base OTs. This reduces the heavy public-key cryptography to a one-time setup cost, while the bulk of the protocol uses only fast symmetric-key operations like AES. The result is a dramatic speedup compared to traditional Diffie-Hellman-based PSI protocols, especially for large sets.
02
Cuckoo Hashing for Efficiency
KKRT employs Cuckoo hashing to map elements into a compact table with minimal collisions. Each element is placed into one of two possible bins using two hash functions, ensuring that lookups require checking only a constant number of positions. This transforms the PSI problem from a quadratic comparison into a linear batch of OT evaluations, slashing both computational and communication complexity.
03
Semi-Honest Security Model
The protocol assumes semi-honest (honest-but-curious) adversaries—parties that follow the protocol correctly but may attempt to learn additional information from the transcript. This security model enables significant performance optimizations compared to maliciously secure protocols. KKRT guarantees that neither party learns anything beyond the intersection result, with formal proofs in the random oracle model.
04
Communication Complexity
KKRT achieves near-optimal communication complexity proportional to the size of the larger set plus the intersection size. For sets of size n, the protocol requires approximately O(n) communication, making it highly suitable for bandwidth-constrained environments. This efficiency comes from batching OT operations and using permutation-based hashing to compress the representation of set elements.
05
Comparison with DH-Based PSI
Unlike classical Diffie-Hellman-based PSI protocols that require expensive modular exponentiation for every element, KKRT replaces these with cheap symmetric operations after the initial OT setup. For large sets (millions of elements), KKRT can be 10-100x faster than ECDH-based approaches. The trade-off is a slightly higher setup cost and reliance on the random oracle model for security proofs.
06
Real-World Applications
KKRT is widely deployed in contact discovery systems, private record linkage for healthcare, and collaborative analytics where two organizations need to find common customers without exposing their full databases. Its efficiency makes it practical for production systems handling datasets with hundreds of millions of entries, operating in seconds rather than hours.
KKRT PROTOCOL INSIGHTS
Frequently Asked Questions
Clear, technical answers to common questions about the KKRT semi-honest private set intersection protocol, its mechanisms, and its performance characteristics.
The KKRT protocol is a highly efficient semi-honest private set intersection (PSI) protocol introduced by Kolesnikov, Kumaresan, Rosulek, and Trieu in 2016. It enables two parties to compute the intersection of their private sets without revealing any elements outside that intersection. The protocol works by combining oblivious transfer (OT) extension with Cuckoo hashing to minimize both computation and communication. Specifically, the receiver uses Cuckoo hashing to map their set into a hash table with empty bins, while the sender uses simple hashing. The parties then perform a large number of 1-out-of-2 OTs efficiently generated via the IKNP OT extension protocol. For each element, the receiver inputs a choice bit based on their hash table position, and the sender inputs two masked values. The receiver decrypts the value corresponding to their element, and if it matches a value computed from the sender's set, the element is in the intersection. This batched OT approach avoids expensive public-key operations per element, making KKRT one of the fastest PSI protocols for semi-honest settings.
Enabling Efficiency, Speed & Accuracy
Intelligent Analysis, Decision & Execution
We build AI systems for teams that need search across company data, workflow automation across tools, or AI features inside products and internal software.
Talk to Us
Search across company data
Give teams answers from docs, tickets, runbooks, and product data with sources and permissions.
Useful when people spend too long searching or get different answers from different systems.
Enterprise searchRAGPermissions
Read more
Automate internal workflows
Use AI to route work, draft outputs, trigger actions, and keep approvals and logs in place.
Useful when repetitive work moves across multiple tools and teams.
AI agentsWorkflow automationGovernance
Read more
Add AI to products and internal tools
Build assistants, guided actions, or decision support into the software your team or customers already use.
Useful when AI needs to be part of the product, not a separate tool.
AI integrationDecision supportModel routing
Read moreSEMI-HONEST PROTOCOL COMPARISON
KKRT vs. Other PSI Protocols
Comparative analysis of the KKRT protocol against other prominent semi-honest private set intersection constructions across key performance and architectural dimensions.
| Feature | KKRT | DH-Based (ECDH) | Circuit-PSI | VOLE-Based |
|---|---|---|---|---|
Cryptographic Foundation | OT Extension + Cuckoo Hashing | Elliptic Curve Diffie-Hellman | Garbled Circuits | Vector OLE |
Communication Complexity | O(n) symmetric, very low constant | O(n) public-key, high per-item | O(n log n) to O(n^2) | O(n) symmetric, lowest constant |
Computational Cost | Low (fast symmetric-key ops) | High (expensive ECC ops) | Very High (circuit garbling) | Very Low (linear operations) |
Asymmetric Set Sizes | ||||
Post-Quantum Security | ||||
Round Complexity | 2 rounds | 2 rounds | 2-3 rounds | 2 rounds |
Bandwidth at 2^20 items | ~10 MB | ~50-100 MB | ~1-10 GB | ~5 MB |
Best Use Case | Balanced sets, low latency | Small sets, simple implementation | Complex intersection logic | Ultra-low bandwidth, large sets |
About the author
Prasad Kumkar
CEO & MD, Inference Systems
Prasad Kumkar is the CEO & MD of Inference Systems and writes about AI systems architecture, LLM infrastructure, model serving, evaluation, and production deployment. Over 5+ years, he has worked across computer vision models, L5 autonomous vehicle systems, and LLM research, with a focus on taking complex AI ideas into real-world engineering systems.
His work and writing cover AI systems, large language models, AI agents, multimodal systems, autonomous systems, inference optimization, RAG, evaluation, and production AI engineering.
LinkedIn
Limited slotsGet a Free AI Consultation
Partnered with leading AI, data, and software stack.
How We Work
Custom AI workflows for your Business
One-fit-all AI don't work for modern businesses. At Inferensys, we aim to understand your business & custom requirements; which we use to define most efficient agentic workflows, the data, and the tools for your business.
01
Review the use case
We understand the task, the users, and where AI can actually help.
Read more02
Pick the right approach
We define what needs search, automation, or product integration.
Read more03
Build the first useful version
We implement the part that proves the value first.
Read more04
Improve from there
We add the checks and visibility needed to keep it useful.
Read moreThe first call is a practical review of your use case and the right next step.
Talk to Us