Efficient Multi-signature Schemes and Threshold Password Authentication

Multi-signature schemes enable a group of users to sign a message by issuing a single short string which is equivalent to the set of their individual signatures on that message, thus reducing both bandwidth and verification time from linear in the number of the individual signers to constant. Such schemes are applicable to authenticated route information discovery, aggregation of acknowledgements in response to a broadcast, aggregation of authenticated data in sensor networks, etc. We make the following contributions regarding such schemes: 1. We propose multi-signature schemes based on the Diffie-Hellman assumption with O(1) verification time, optimal exact security (enabling short key sizes), and security under concurrent composition, i.e. each user can safely run several concurrent instances of the multi-signature protocol. 2. We propose multi-signatures based on the Discrete-Log assumption with round complexity reduced to two rounds at no extra cost. The exact security of our schemes matches that of standard DL-based signatures, and our schemes are concurrently secure. Our schemes rely on a novel commitment scheme of independent interest. 3. We propose identity-based multi-signature and aggregate signature schemes (allowing aggregation of signatures on different messages) based on the RSA problem. This is the first ID-based aggregate signature scheme which is stateless and non-sequential. This scheme is also 2-round, it is concurrently secure, and its exact security is comparable to that of standard (non-aggregated) ID-based signatures.;Password-Authenticated Key Agreement (PAKA), on the other hand, is an interactive protocol in which two or more participants establish a cryptographic key (i.e. high entropy string) based on the knowledge of only a human memorable password (i.e. a low entropy string), in such a way that an unauthorized party cannot influence the distribution of the established cryptographic keys, without guessing the password correctly. PAKA protocols and threshold PAKA protocols are extremely useful in establishing secure channels amongst two and multiple parties. Our contribution to this field is formalizing a solution which we call it Password-Protected Secret-Sharing (PPSS), that allows a user to secret-share her data among n trustees in such a way that (1) the user can retrieve the shared secret upon entering a correct password into a reconstruction protocol, which succeeds as long as at least t + 1 uncorrupted trustees are accessible, and (2) the shared data remains secret even if the adversary which corrupts t trustees, with the level of protection expected of password-authentication. We propose an efficient PPSS protocol in the PKI model, secure under the DDH assumption and show a generic compilation of a PPSS protocol to Threshold Password Authenticated Key Agreement (T-PAKA) protocol in the PKI model with significantly lower message, communication, and server computation complexities than existing T-PAKA's.