Fair E-Cash: Be Compact, Spend Faster

摘要

We present the first fair e-cash system with a compact wallet that enables users to spend efficiently k coins while only sending to the merchant O(λlog k) bits, where λ is a security parameter. The best previously known schemes require to transmit data of size at least linear in the number of spent coins. This result is achieved thanks to a new way to use the Batch RSA technique and a tree-based representation of the wallet. Moreover, we give a variant of our scheme with a less compact wallet but where the computational complexity of the spend operation does not depend on the number of spent coins, instead of being linear at best in existing systems.