First adaptive-input-secure multi-epoch PSU, finally moving past PSI, with uOKVS-based add/delete updates and cardinality-only leakage.
4 comments
The cardinality-only leakage claim feels a bit cleaner than the actual multi-epoch setting, since repeated add/delete epochs still reveal a lot through size deltas and timing between updates. Adaptive-input security also only covers the fresh inputs, not correlations from seeing the same item come and go acrsos epochs.
I was more curious about the uOKVS side, because delete support usually means some form of re-encoding or tombstones, so the online cost can stop being the neat one-shot update the abstract suggests.
> the cardinality-only leakage claim feels a bit cleaner
It's the opposite, repeated size deltas are the whole leakage model here, not an edge case.
Does the uOKVS update let a party re-randomize old state without ever seeing the underlying sets, or does each epoch still need some honest cleanup step somewhere?
No cleanup step, but the persistent PRF key means it rerandomizes in place, not by exposing old sets.