Recover a secret from randomly corrupted shares --- while preserving perfect privacy. A foundation for practical fuzzy password authentication and conditional encryption.
Perfect privacyAny ≤ t − 1 shares are jointly uniform.
Random robustnessRecover despite up to n − t random corruptions.
Two applicationsFuzzy PAKE and conditional encryption.
01 / The primitive
Privacy without a robustness gap.
Shamir secret sharing offers perfect privacy, but corrupted shares can prevent reconstruction. RRSS preserves that privacy and adds robustness against random share corruption.
An adversary chooses up to n − t positions; the shares at those positions are replaced by independent uniform random shares. RRSS identifies enough valid shares to recover the secret with high probability.
The model matters: random replacement is weaker than arbitrary malicious corruption. It is exactly the structure that arises from character mismatches in our applications.
Figure 1 Random Robust Secret Sharing. The reconstruction threshold is t; the corruption budget is n − t.
Read the research summary
We introduce Random Robust Secret Sharing with Perfect Privacy (RRSS). The construction preserves (t − 1)-perfect privacy while recovering a secret with high probability when an arbitrary subset of up to n − t shares is independently replaced at random. We use RRSS to construct a practically efficient fuzzy password-authenticated key exchange protocol for Hamming distance and an efficient conditional encryption scheme for arbitrary Hamming-distance thresholds. Implementations evaluate the practicality of both applications.
02 / Applications
When mismatches become random shares.
The same identification step turns noisy inputs into useful cryptographic building blocks.
A
Fuzzy password-authenticated key exchange
Establish a shared session key using passwords that are close in Hamming distance.
Matching characters yield valid shares; mismatches yield random shares. The receiving party does not initially know which shares are valid. RRSS identifies them, enabling reconstruction when the passwords are sufficiently close. The protocol provides full UC security.
Figure 2 RRSS-based fuzzy PAKE: valid shares from matches, random shares from mismatches.
Application example: pairing from sensor fingerprints
Similar physical measurements can produce nearby binary fingerprints, which serve as fuzzy passwords. We integrate RRSS into the FastZIP fPAKE implementation and evaluate it using the original fingerprint datasets.
Figure 3 Adapted two-car illustration. Original FastZIP evaluates intra-car device pairing; this illustration is not a claim of a deployed inter-car system.
B
Conditional encryption for Hamming distance
Release a payload only when an encrypted message is close to a control message.
Alice encrypts m1. Bob combines that ciphertext with a control message m2 and payload m3. Alice recovers the payload when Ham(m1, m2) ≤ ℓ; otherwise decryption returns ⊥, except with negligible error. RRSS replaces a combinatorial search for valid shares with efficient identification.
Ameri & Blocki · CCS 2024Ω(nℓ)
Search over candidate subsets
→
RRSS-based scheme · CCS 2026O(nω)
Identify valid shares using linear algebra
The binomial coefficient denotes “n choose ℓ”; ω is the matrix multiplication exponent. This compares conditional decryption costs; see the paper for ciphertext-size tradeoffs and benchmarks.
Figure 4 Conditional encryption with RRSS-based share identification and recovery.
Mohammad Hassan Ameri and Jeremiah Blocki. Random Robust Secret Sharing with Perfect Privacy and its Applications. ACM CCS, 2026.
BibTeX
@inproceedings{ameri2026rrss,
author = {Mohammad Hassan Ameri and Jeremiah Blocki},
title = {Random Robust Secret Sharing with Perfect Privacy
and its Applications},
booktitle = {Proceedings of the ACM SIGSAC Conference
on Computer and Communications Security},
year = {2026},
doi = {10.1145/3830454.3846816},
url = {https://eprint.iacr.org/2026/653}
}
