| We present an approach to design signature schemes that are secure even with short passwords. We also present a distributed signature verification scheme that is very efficient. With the growth of on-line applications, users have been burdened with the challenge of having to memorize many passwords. We propose short passwords, and present a distributed verification scheme that allows groups of servers to validate these passwords in a distributed fashion, preventing off-line attacks. This scheme is likely to be useful in various commercial contexts, including Federated Identity applications, where vendors collaborate to permit common logins by customers. Efficiency is also critical when compute and battery power requirements must be low, or for supporting micropayment applications. Our authentication scheme requires only 0.5% of the online modular computations required in RSA, supports distributed verification and short passwords. Our scheme is provably secure and tolerant to Byzantine failures of the servers.; Key words. Distributed authentication, Federated Identity, Short passwords, Distributed signature verification. |
