Password Protected Secret Sharing from Lattices

A password protected secret sharing (PPSS ) allows a user to store shares of a secret on a set of L servers, and use a single password to authenticate itself to any subset of k servers at a later time to access the shares and reconstruct the secret. Security of PPSS ensures that a coalition of up to k- 1 servers cannot reveal any information about the secret message or the password. A related primitive is threshold password authenticated key exchange protocol (TPAKE ) that allows a user to establish individual authenticated shared secret keys with members of a subset of k out of L servers, using a single password. These primitives are well motivated, with applications such as secure storage of secret keys, and secure group communication using passwords for authentication. In this paper, we give the first construction of these primitives that provide post-quantum security. We prove security of our constructions in concurrent setting, and in the standard model, reducing security to the decisional LWE problem