ACM CCS

\documentclass[sigconf,screen]{acmart}

\usepackage{graphicx}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{booktabs}
\usepackage{algorithm,algpseudocode}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}

\AtBeginDocument{%
  \providecommand\BibTeX{{%
    \normalfont B\kern-0.5em{\scshape i\kern-0.25em b}\kern-0.8em\TeX}}}

\acmConference[CCS '26]{ACM SIGSAC Conference on Computer and Communications Security}{October 12--16, 2026}{City, Country}
\acmISBN{978-1-4503-XXXX-X/26/10}
\acmDOI{10.1145/XXXXXXX.XXXXXXX}
\setcopyright{acmlicensed}
\copyrightyear{2026}
\acmYear{2026}

\begin{document}

\title{Aurora: Practical Private Set Intersection\\
       at Billion-Element Scale}

\author{First Last}
\affiliation{\institution{University of Example}\country{Country}}
\email{[email protected]}

\author{Jane Doe}
\affiliation{\institution{Example Research Labs}\country{Country}}
\email{[email protected]}

\author{John Smith}
\affiliation{\institution{University of Example}\country{Country}}
\email{[email protected]}

\renewcommand{\shortauthors}{Last et al.}

\begin{abstract}
Private set intersection (PSI) allows two parties to learn their common
elements without revealing the rest. Existing protocols scale poorly
beyond 100M elements, limiting applicability to many industrial-scale
workloads. Aurora is a new PSI protocol using oblivious pseudorandom
functions (OPRFs) and bucket-level parallelism that achieves 3.8$\times$
speedup on 1B-element benchmarks with 23\% less communication, while
preserving semi-honest security. We formally prove security in the
standard model and report production-scale experiments showing that
1B-element PSI is now practical on commodity hardware.
\end{abstract}

\begin{CCSXML}
<ccs2012>
<concept><concept_id>10002978.10002991</concept_id>
<concept_desc>Security and privacy~Cryptography</concept_desc>
<concept_significance>500</concept_significance></concept>
</ccs2012>
\end{CCSXML}
\ccsdesc[500]{Security and privacy~Cryptography}

\keywords{private set intersection, OPRF, secure multiparty computation}
\maketitle

\section{Introduction}
PSI is a building block for contact discovery, ad measurement, clinical
research collaborations, and anti-fraud cooperation. Practical scaling
to billion-element sets has remained elusive: prior protocols either
incur quadratic bandwidth or rely on trusted hardware.

\paragraph{Contributions.}
\begin{itemize}
\item A new OPRF-based PSI protocol using bucket-level parallelism.
\item Formal security proof in the semi-honest model.
\item Implementation and evaluation demonstrating 1B-element PSI in
  under 6 minutes over a 10 Gbps link.
\item Open-source release with an extensive benchmark suite.
\end{itemize}

\section{Background}
OPRF-based PSI, circuit-based PSI, unbalanced PSI. We focus on the
balanced two-party setting with standard security assumptions
(DDH, Random Oracle).

\section{Protocol}
Aurora partitions inputs into buckets using a universal hash and runs
OPRF evaluations per-bucket in parallel. A fallback path handles
collisions without revealing set sizes.

\begin{algorithm}[t]
\caption{Aurora PSI (sketch)}
\begin{algorithmic}[1]
\State $P_1$ and $P_2$ agree on buckets $B_1, \ldots, B_k$
\For{each bucket $B_i$}
  \State $P_1$ sends $\{\text{OPRF}_k(x) : x \in B_i \cap S_1\}$
  \State $P_2$ computes $\text{OPRF}_k(y)$ for $y \in B_i \cap S_2$
  \State $P_2$ outputs matches
\EndFor
\end{algorithmic}
\end{algorithm}

\subsection{Security}
\begin{theorem}
Aurora is secure in the semi-honest two-party model under DDH and ROM.
\end{theorem}
We prove security via the standard simulation paradigm; see Appendix A.

\section{Implementation}
Aurora is 9{,}400 lines of Rust using the libOTe library for oblivious
transfer. The OPRF implementation uses curve25519 via ristretto.

\section{Evaluation}
\begin{table}[t]
\centering
\begin{tabular}{lcc}
\toprule
Protocol & Time (s) & BW (GB) \\
\midrule
PSIpure         & 4{,}820 & 172 \\
PSIfast         & 1{,}240 &  98 \\
\textbf{Aurora} & \textbf{324} & \textbf{75} \\
\bottomrule
\end{tabular}
\caption{1B-element benchmarks over a 10 Gbps link.}
\label{tab:main}
\end{table}

\section{Related Work}
DDH-based PSI, RSA-based PSI, homomorphic PSI, threshold PSI.

\section{Conclusion}
Aurora demonstrates that billion-element PSI is practical on commodity
hardware with modern protocol design.

\section*{Ethics Considerations}
PSI is a privacy-enhancing primitive; our work directly advances the
state of practical privacy-preserving computation. We do not foresee
direct misuse potential.

\bibliographystyle{ACM-Reference-Format}
\bibliography{refs}

\end{document}