Abstract
Auditability is an important property in financial systems and architectures. Here we define the primitive of “blind auditable membership proof” (BAMP) which combines public auditability with privacy (i.e. user anonymity). In particular, one can use it as an auditable alternative to a “blind signature” component in unconditionally anonymous payment systems and in other systems requiring anonymity. We show that BAMP can be implemented quite efficiently (namely, without resorting to general zero-knowledge proofs of NP statements, which, in general, merely indicates plausibility).
We then build an anonymous off-line payment system based on the implementation of BAMP. The system has the property that its security against counterfeiting relies on the integrity of a public (auditable) database and not on the secrecy of privately held keys. The system strongly defends against blackmailing and bank robbery attacks, in the same way the system in [21] does. However, the current system is a significant step towards practicality since, unlike the previous system, first, it does not use general protocols for zero knowledge proofs for NP, and second, the cost of the payment protocol is independent of the number of total coins withdrawn.
Work on this paper was done while author was at ICSI, Berkeley.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
N. Baric and B. Pfitzmann. Collision-free accumulators and fail-stop signature schemes without trees. Lecture Notes in Computer Science, 1233, 1997.
M. Bellare and P. Rogaway. Random oracles are practical: A pardigm for designing efficient protocols. In Victoria Ashby, ed., 1st ACM Conference on Computer and Communications Security, Fairfax, Virginia, November 1993. ACM Press, also appeared as IBM RC 19619 (87000) 6/22/94.
J. Benaloh and M. de Mare. One-way accumulators: A decentralized alternative to digital signatures (extended abstract). In Tor Helleseth, ed., Advances in Cryptology-EUROCRYPT 93, volume 765 of Lecture Notes in Computer Science, pages 274–285. Springer-Verlag, 1994, 23-27 May 1993.
D. Boneh and M. Franklin. Efficient generation of shared RSA keys. In Burt Kaliski, ed., Advances in Cryptology: CRYPTO’ 97, volume 1233 of Lecture Notes in Computer Science, pages 425–439. Springer, 1997.
S. Brands. An efficient off-line electronic cash system based on the representation problem. In 246. Centrum voor Wiskunde en Informatica (CWI), ISSN 0169-118X, December 31 1993. AA (Department of Algorithmics and Architecture), CS-R9323, ftp://ftp.cwi.nl/pub/CWIreports/AA/CS-R9323.ps.Z.
J. Camenisch and M. Michels. A group signature scheme with improved efficiency. Lecture Notes in Computer Science, 1514, 1998.
J. Camenisch and M. Michels. Proving in zero-knowledge that a number is the product of two safe primes. Lecture Notes in Computer Science, 1592, 1999.
J. L. Carter and M. N. Wegman. Universal classes of hash functions (extended abstract). In Conference Record of the Ninth Annual ACM Symposium on Theory of Computing, pages 106–112, Boulder, Colorado, 2-4 May 1977.
D. Chaum. Blind signatures for untraceable payments. In David Chaum, Ronald L. Rivest, and Alan T. Sherman, eds., Advances in Cryptology: Proceedings of Crypto 82, pages 199–203. Plenum Press, New York and London, 1983, 23-25 August 1982.
J. D. Cohen and M. J. Fischer. A robust and verifiable cryptographically secure election scheme (extended abstract). In 26th Annual Symposium on Foundations of Computer Science, pages 372–382, Portland, Oregon, 21-23 October 1985. IEEE.
R. Cramer and V. Shoup. Signature schemes based on the strong RSA assumption. In Proceedings of the 6th ACM Conference on Computer and Communications Security. ACM Press, 1999.
A. Fiat and A. Shamir. How to prove yourself: Practical solutions to identification and signature problems. In Andrew Michael Odlyzko, ed., Advances in cryptology: CRYPTO’ 86: proceedings, volume 263 of Lecture Notes in Computer Science, pages 181–187, Berlin, 1987. Springer-Verlag.
Y. Frankel, P. MacKenzie, and M. Yung. Robust efficient distributed RSA-Key generation. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC-98), pages 663–672, New York, May 23-26 1998. ACM Press.
Y. Frankel, Y. Tsiounis, and M. Yung. “Indirect discourse proofs”: Achieving efficient fair off-line E-cash. In Kwangjo Kim and Tsutomu Matsumoto, eds., Advances in Cryptology-ASIAGRYPT’ 96, volume 1163 of Lecture Notes in Computer Science, pages 286–300, Kyongju, Korea, 3-7 November 1996. Springer-Verlag.
M. K. Franklin and M. Yung. Secure and efficient off-line digital money (extended abstract). In Svante Carlsson Andrzej Lingas, Rolf G. Karlsson, ed., Automata, Languages and Programming, 20th International Colloquium, volume 700 of Lecture Notes in Computer Science, pages 265–276, Lund, Sweden, 5-9 July 1993. Springer-Verlag.
E. Fujisaki and T. Okamoto. Statistical zero knowledge protocols to prove modular polynomial relations. In Burton S. Kaliski Jr., ed., Advances in Cryptology-CRYPTO’ 97, volume 1294 of Lecture Notes in Computer Science, pages 16–30. Springer-Verlag, 17-21 August 1997.
R. Gennaro, S. Halevi, and T. Rabin. Secure hash-and-sign signatures without the random oracle. Lecture Notes in Computer Science, 1592, 1999.
M. Jakobsson and M. Yung. Revokable and versatile electronic mony. In Clifford Neuman, ed., 3rd ACM Conference on Computer and Communications Security, pages 76–87, New Delhi, India, March 1996. ACM Press.
D. Pointcheval and J. Stern. Security proofs for signature schemes. In Ueli Maurer, ed., Advances in Cryptology-EUROCRYPT 96, volume 1070 of Lecture Notes in Computer Science, pages 387–398. Springer-Verlag, 12-16 May 1996.
T. Sander. Efficient accumulators without trapdoor. In V. Varadharajan and Y. Mu, eds., Proceedings of 2nd Lnternational Conference on Lnformation and Communication Security (LCLCS’ 99), volume 1726 of Lecture Notes in Computer Science. Springer-Verlag, 1999.
T. Sander and A. Ta-Shma. Auditable, anonymous electronic cash. In M. Wiener, ed., Advances in Cryptology-CRYPTO’ 99, volume 1666 of Lecture Notes in Computer Science. Springer-Verlag, 1999.
A. De Santis, Y. Desmedt, Y. Frankel, and M. Yung. How to share a function securely (extended summary). In Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pages 522–533, Montreal, Quebec, Canada, 23-25 May 1994.
A. Shamir. On the generation of cryptographically strong pseudo-random sequences. In Shimon Even and Oded Kariv, eds., Automata, Languages and Programming, 8th Colloquium, volume 115 of Lecture Notes in Computer Science, pages 544–550, Acre (Akko), Israel, 13-17 July 1981. Springer-Verlag.
S. von Solms and D. Naccache. On blind signatures and perfect crimes. Computers and Security, ll(6):581–583, October 1992.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sander, T., Ta-Shma, A., Yung, M. (2001). Blind, Auditable Membership Proofs. In: Frankel, Y. (eds) Financial Cryptography. FC 2000. Lecture Notes in Computer Science, vol 1962. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45472-1_5
Download citation
DOI: https://doi.org/10.1007/3-540-45472-1_5
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42700-1
Online ISBN: 978-3-540-45472-4
eBook Packages: Springer Book Archive