Privacy preserving multi-modal biometric au thentication (PPMBA) is a critical technology for verifying identity with multiple biometrics. Among PPMBA solutions, fuzzy vaults stand out for their simplicity and effectiveness. However, existing fuzzy vaults suffer from two major limitations: (1) cross-matching vulnerability, it allows an adversary to use a vault stolen from one service to unlock the same user's vault on another sensitive service; (2) excessive storage overhead, with auxiliary data 100–300 times larger than the original biometric data. In this work, to address these challenges, we propose OKVS Vault, a novel fuzzy vault protocol by introducing a multi threshold secret sharing (MTSS) scheme and integrating it with an oblivious key-value store (OKVS). Our protocol achieves universally composable (UC) security while significantly im proving efficiency and accuracy. Benchmark results demonstrate that OKVS Vault reduces auxiliary data size by 99.61% compared to state-of-the-art (SOTA) fuzzy vaults, bringing it close to the original data size. Moreover, the protocol operates 60–93% faster than SOTA alternatives. When applied to fused fingerprint and face features, OKVS Vault achieves exceptional accuracy: a 0.00% false acceptance rate (FAR), 4.00% false rejection rate (FRR), and 3.00% equal error rate (EER), outperforming existing fuzzy vaults.