@Istvan_A_Seres: 🚀New paper: Private Delegation...

🚀New paper: Private Delegation of (Non-)Membership Proof Updates in Cryptographic Accumulators

Ever tried to use accumulators in practice? Then you’ve hit the wall: every update breaks everyone’s proofs.

We fix that.

🧵1/n

@0xSooki @BotiGlasz 🔥The core problem:

Cryptographic accumulators compress huge sets (e.g., set of unspent coins) into tiny digests.

But… when the set changes:
➡️ ALL membership proofs become outdated
➡️ Clients must recompute them

This kills usability for mobile/offline users.

2/n

This isn’t just annoying — it’s fundamental.

Recent lower bounds show:
👉 You can’t avoid frequent proof updates without blowing up the state size.

So the question becomes:
Can we privately outsource (non-)membership proof updates?

3/n

@0xSooki @BotiGlasz Naively outsourcing fails!❌

If you send your (non-)membership proof to a server:
👉 it can brute-force which element you own.
Privacy = gone.

Even worse in systems like Zcash, anonymous credentials, or key transparency.

4/n

@0xSooki @BotiGlasz 💡Our idea:

Let clients delegate (non-)membership proof updates to an untrusted server…

BUT:
🔒 without revealing which element they care about
⚡ with constant client work
✅ and publicly verifiable correctness

5/n

@0xSooki @BotiGlasz We introduce a new primitive:

👉 Private delegation of accumulator proof updates

Formalized with:
• correctness
• delegation soundness
• (strong + weak) privacy guarantees

6/n

@0xSooki @BotiGlasz 🧠 Key trick:

Before sending a (non-)membership proof to the server, the client:
👉 blinds it

The server updates the blinded (non-)membership proof
→ learns nothing about the underlying element

7/n

@0xSooki @BotiGlasz Then:

✔ Server returns updated blinded proof
✔ Anyone can verify the update was correct
✔ Client unblinds → gets valid fresh (non-)membership proof

All without revealing the element x 👀

8/n

@0xSooki @BotiGlasz ⚡Performance highlight:

Client update cost:
👉 O(1) (constant time!)
Previous work:
👉 O(k) or even O(sqrt(k))

This is a huge win for resource-constrained devices.

9/n

@0xSooki @BotiGlasz 🏗 We build concrete schemes for:

• RSA accumulators
• Bilinear accumulators

Both supporting efficient private delegation for (non-)membership proofs.

10/n

@0xSooki @BotiGlasz For RSA accumulators:

✨ Simple but powerful trick:
Randomize proof → exponentiate → prove consistency with NIZKs

Result:
✔ efficient
✔ practical
✔ ~7% overhead vs non-private baseline

11/n

@0xSooki @BotiGlasz We also support:

✔ membership proofs
✔ non-membership proofs
✔ batching of updates

All privately delegated.

12/n

@0xSooki @BotiGlasz 🧾 Public verifiability is key:

The server can produce a proof that:
👉 “I updated this correctly”
Anyone can check it.

This enables:
💰 markets for proof-serving nodes.

13/n

🧠 Why this matters:

Applications include:
• Stateless blockchains
• Anonymous credentials (revocation)
• Registration-based encryption
• Transparency logs

14/n

@0xSooki @BotiGlasz Example: stateless blockchains

Without our approach:
👉 you must stay online to keep proofs fresh

With us:
👉 go offline, come back, outsource updates privately

It turns out that running a server for delegating proofs in a stateless blockchain is pretty cheap.

15/n

@0xSooki @BotiGlasz 🧪Bonus:

We built an open-source implementation🔧

👉 First real system for private accumulator proof delegation

3...2...1...Delegate! github.com/GlaszBoti/priv…

16/n

@0xSooki @BotiGlasz Open problems, directions

Private delegation for other authenticated data structures: vector commitments, authenticated dictionaries, etc.

Private delegation for PQ-secure accumulators

Multi-server private delegation schemes for better liveness

17/n

@0xSooki @BotiGlasz Let us know if you have any comments, feedback, critique, etc.

Tolle, lege: eprint.iacr.org/2026/832.pdf

Q.E.D.
Fin!
18/18