1 / 13
JPMorgan AI Research · AlgoCRYPT CoE · 2026

TAPAS: Two-server Asymmetric Private Aggregation Scheme

Efficient Two-Server Private Aggregation Beyond Prio(+)
Harish Karthikeyan  ·  Antigoni Polychroniadou
Asymmetric Post-Quantum Identifiable Abort
Motivation
The Symmetric Bottleneck
Prior Work — Prio · Elsa · Prio+
Clients
→
O(nL)
Server 1
↔
O(nL)
Server 2
Both servers receive O(nL) data — doubles deployment cost
Abort is anonymous — cannot identify the guilty party
→
TAPAS — Intentional Asymmetry
Clients
→
O(nL)
Server 1
↔
O(nλ)
Server 2
S2 receives only O(nλ) seeds — runs on a laptop
Identifiable Abort — misbehaving party is named, not just detected
93×
speedup vs Prio
17.5×
speedup vs Elsa
30×
less work for Server 2
O(nλ)
Server 2 communication
Core Construction
LWE-Based Asymmetric Masking
Clientsi ∈ {1…n}
Server 2Facilitator
Server 1Aggregator
\(\mathbf{y}_i = \mathbf{A}\mathbf{s}_i + \mathbf{e}_i + \Delta\mathbf{x}_i \in \mathbb{Z}_q^L\)
\(\mathbf{s}_i \in \mathbb{Z}_q^\lambda\)
\(\textstyle\sum \mathbf{s}_i \in \mathbb{Z}_q^\lambda\)
Client

1. Mask input \(\mathbf{x}_i\) as \(\mathbf{y}_i = \mathbf{A}\mathbf{s}_i + \mathbf{e}_i + \Delta\mathbf{x}_i \in \mathbb{Z}_q^L\)
2. Send large \(\mathbf{y}_i\) (O(L)) → Server 1
3. Send small seed \(\mathbf{s}_i\) (O(λ)) → Server 2

Decryption at Server 1

1. Collect \(\sum \mathbf{y}_i\) — all O(L) work stays here
2. Receive only \(\sum \mathbf{s}_i\) from Server 2 — O(λ)
3. Output \(\approx \operatorname{Decode}\!\bigl(\textstyle\sum\mathbf{y}_i - \mathbf{A}\sum\mathbf{s}_i\bigr)\)

Additive homomorphism: \(\sum_i \mathbf{y}_i = \mathbf{A}\sum_i\mathbf{s}_i + \sum_i\mathbf{e}_i + \Delta\sum_i\mathbf{x}_i\). Server 1 recovers \(\sum\mathbf{x}_i\) using only the aggregate seed — never individual inputs.

Contribution Summary
TAPAS vs. Prior Work
Property Prio Prio+ Elsa Heli TAPAS
S2 comm. independent of L ✗✗ ✗✗ ✓
No trusted setup ✗✗ ✗✗ ✓
Post-quantum (LWE / SIS only) ✗✗ ✗✗ ✓
Malicious server security ✗✗ ✓ MP ✓ MP ✓ IA
Identifiable Abort ✗✗ ✗✗ ✓
Input validation / malicious clients ✓✓ ✓✓ ✓
Arbitrary integer inputs ✓✓ ✓✗ ✓

MP = Malicious Privacy  ·  IA = Identifiable Abort (stronger)

Input Validation
Two ZKP Instantiations

To guarantee clients' inputs satisfy norm constraints (L2 / L∞), TAPAS offers two proof systems with complementary trade-offs.

TAPASBP — Bulletproof Variant

Group-Based Proofs

  • Pedersen commitments + Bulletproofs over prime-order group
  • Building on prior works of GHV21, ACORN, Armadillo
  • Four-square theorem proves L2 / L∞ norms exactly
  • Better than Heli's \( O(tL) \) expansion where \( \|\mathbf{x}\|_\infty\leq 2^t-1 \)
  • Limitation: group exponentiations expensive at large L
TAPASLWE — Lattice-Only Variant

All-Lattice Proofs

  • Proofs entirely over LWE modulus q — no extra group field
  • No group exponentiations whatsoever
  • Best asymptotic performance for large L
Technical Challenge
Three Lattice Caveats
Caveat 1

Rejection Sampling

Responses must be over the integers, not modulo q. We must sample carefully and abort if the response violates a norm bound — to prevent leaking the secret.

Caveat 2

Repetition Cost

Reducing rejection probability forces a smaller challenge space, which increases soundness error. More repetitions of the protocol are required to compensate.

Caveat 3

Soundness Slack

The witness can only be extracted with an error margin. For monolithic proofs over dimension L:

Slack \(\gamma \approx \sqrt{L}\)

This is the core bottleneck for large L.

Zero-Knowledge Proof
Lattice \(\Sigma\)-Protocol — Interactive Proof

Status:

Prover Client
Commit: \(t = Ar_s + r_e + \Delta r_x\)
Challenge: \(c\)
Response: \(z_s, z_e, z_x\)
Verifier Server
Witness Decomposition
L
monolithic
↓ split into k blocks
d
d = L/k

Split L-dim witness into k blocks of size d = L/k.

Slack shrinks from √L → √d. Each block restarts independently → expected time O(k·M).

Bimodal Rejection Sampling
σ ≫ ‖w‖ σ ∝ ‖w‖ 0

Target a bimodal distribution shaped like witness ± noise.

Requires much smaller \( \sigma \) while ensurng higher acceptance rate.

Key Innovation
Independent Restarts — Closing the Security Gap
The Technique

Each block performs rejection sampling independently. If block 5 fails, only block 5 restarts — all other blocks keep their accepted values.

Expected Time: \(\mathcal{O}(k \cdot M)\) with \(M \approx 2\)

Transforms exponential-in-k convergence into linear, restoring practical efficiency for high-dimensional witnesses.

The Security Gap

Independent blocks open an attack: a malicious client could use different secrets sj per block to inject garbage. This breaks the global consistency guarantee.

Question: How do we enforce s1 = s2 = … = sk without reverting to O(L) communication for Server 2?

Answer: Cross-Server Digest Check

Server 2 re-derives responses using the client's single secret s, hashes them, and sends a 256-bit digest to Server 1 for verification. Communication overhead for S2 remains O(λ).

Global Consistency
Cross-Server Digest Verification

Status:

Client
Server 2Facilitator
Server 1Aggregator
Secret s + Seed
ZK Responses z1 … zk
Digest H = Hash(z′j)
✔ CONSISTENT
 Server 2 computes

1. Expand seed ρ → masking vectors {rj}
2. Re-derive z′j = rj + cj · s  per block j
3. Compute H = Hash({z′j, cj})

Bandwidth to S1: 256 bits — O(1) in L
 Server 1 verifies

1. Verify ZK proof π on responses zj
2. Compute H′ = Hash({zj, cj}) locally
3. If H = H′: same s used across all k blocks ✓

Security: collision resistance of H
Malicious Security
PROM + Equivocable Commitments
The Simulation Trap

A malicious Server 1 drops ciphertexts dynamically. The simulator must commit to honest ciphertexts before knowing which clients S1 will drop — but it cannot query the ideal functionality without knowing the final online set.

The PROM Solution

Add a secondary programmable mask derived from a seed ρi:

\(y_i = As_i + e_i + \Delta x_i + \mathcal{H}'(\rho_i)\)

The simulator programs H′(ρi) after the online set is fixed, injecting a correction term into the sum.

The ZKP Dilemma

Proving correctness of yi now requires proving inside the ZKP that H′(ρi) was computed correctly — expensive and incompatible with the Programmable Random Oracle Model used for simulation.

Equivocation Technique

Commit directly to the raw mask w without proving its derivation. Use an equivocable commitment (Pedersen DL trapdoor or wide Ajtai SIS matrix) to re-open to wtarget after the online set is finalised.

\(\text{Prove } y_i \text{ w.r.t. } w \quad + \quad \text{Equivocal commitment to } w\)
Stronger Security Guarantee
Identifiable Abort
 1. Binding Handshake

Before exchanging any data, servers intersect their valid-client sets V1 ∩ V2 = V and each signs and broadcasts V. Neither server can later deny seeing a client's message.

 2. Proof of Malice

If a digest fails, the server must produce the original signed message as evidence. Because signatures are non-repudiable:

  • Server cannot fake a client error
  • Server cannot frame an honest client
 3. Privacy Guarantee

False alarms reveal the server as the cheater — without exposing any client secret.

Clients
Signed \((m_i, \sigma_i)\)
S2
S1
Valid Set V
Signed Proof σ

Non-repudiation prevents anonymous stalling attacks

Empirical Results · n = 100 clients, AWS c5.9xlarge + ABIDES network model
Computation vs. Vector Length L
Client Computation

L = 216  /  217  /  218  (seconds)

Prio

13.3
35.3
73.4

Elsa

3.1
6.9
13.8

TAPAS

0.20
0.40
0.79
93× vs Prio  ·  17.5× vs Elsa
Server 1 Computation

L = 216  /  217  /  218  (seconds)

Prio

2.6
7.7
15.0

Elsa

3.7
7.9
15.4

TAPAS

2.6
5.2
10.2
1.5× faster than Elsa & Prio at L=218
Server 2 — Compute + Comm.

L = 216  /  217  /  218  (seconds)

Prio (compute ≈ comm.)

3.1
8.4
17.0

Elsa (comm. dominates at large L)

12.4
25.5
50.6

TAPAS (comm. = 0.1 s flat, any L)

0.26
0.38
0.62
352× less inter-server traffic vs Elsa at L=218

S2→S1 carries only n SHA-256 digests + one λ-field-element mask — bandwidth independent of L. Elsa/Prio send O(nL) data: at n=1000, L=217 that is terabytes per round; TAPAS sends kilobytes. The gap widens linearly as L grows.

Empirical Results · n ∈ {100 … 1000}, L = 2¹⁶ / 2¹⁷
Scaling with Client Count n

TAPAS client cost is O(1) in n — clients prove independently, so cohort size doesn't affect per-client work. End-to-end times confirm the architecture advantage at n=1000:

Total Protocol Time — n=1000, L=217  (compute + simulated comm., seconds)
Elsa
611.7
Prio
320.8
TAPAS
88.8  (6.9× faster than Elsa)
Client Time · L=216
Elsa n=1000
31.4
TAPAS n=1000
0.20

Elsa grows 155× from n=100→1000.
TAPAS stays flat at 0.20 s regardless of cohort size.

S2 Compute · n=1000
Prio, L=216
89.0
Elsa, L=217
79.1
TAPAS, L=217
2.82

55× vs Prio · 23× vs Elsa.

Why Inter-Server Comm. Matters

Prio / Elsa — S2 receives

O(nL) ciphertexts per round

n=1000, L=217: terabytes of traffic

TAPAS — S2 receives

n seeds (λ bits each)

n=1000, L=217: a few kilobytes

S2→S1 reply: n digests + 1 mask = 0.1 s flat, independent of L. This is 352× less comm. than Elsa at L=218.

JPMorgan AI Research · AlgoCRYPT CoE

Thank You

TAPAS: Efficient Two-Server Asymmetric Private Aggregation

harish.karthikeyan@jpmchase.com
antigoni.polychroniadou@jpmorgan.com
✓

S2 costs O(nλ) in comm. and compute — independent of L.

✓

First two-server protocol with pure post-quantum security (LWE + SIS only)

✓

Block-wise ZK proofs: slack √d instead of √L; independent restarts keep runtime O(k·M)

✓

Identifiable Abort: any misbehaving party (client or server) is cryptographically identified

✓

93× faster than Prio, 17.5× than Elsa (client, L=218). End-to-end 6.9× faster at n=1000.

✓

352× less inter-server traffic than Elsa at L=218 — kilobytes instead of terabytes per round

8th Edition · CRYPTO 2026
Privacy-Preserving
Machine Learning
Affiliated Event  ·  Submissions Open
Submit
EasyChair
Workshop
Website