Foteini Baldimtsi
ABSTRACT
We define and propose an efficient and provably secure construction of blind signatures with attributes. Prior notions of blind signatures did not yield themselves to the construction of anonymous credential systems, not even if we drop the unlinkability requirement of anonymous credentials. Our new notion in contrast is a convenient building block for anonymous credential systems. The construction we propose is efficient: it requires just a few exponentiations in a prime-order group in which the decisional Diffie-Hellman problem is hard. Thus, for the first time, we give a provably secure construction of anonymous credentials that can work in the elliptic group setting without bilinear pairings and is based on the DDH assumption. In contrast, prior provably secure constructions were based on the RSA group or on groups with pairings, which made them prohibitively inefficient for mobile devices, RFIDs and smartcards. The only prior efficient construction that could work in such elliptic curve groups, due to Brands, does not have a proof of security.
- M. Abe. A secure three-move blind signature scheme for polynomially many signatures. In EUROCRYPT'01, pages 136--151, 2001. Google Scholar
Digital Library
- M. Abe and T. Okamoto. Provably secure partially blind signatures. In CRYPTO'00, pages 271--286. Springer-Verlag, 2000. Google ScholarDigital Library
- F. Baldimtsi and A. Lysyanskaya. Anonymous credentials light. Cryptology ePrint Archive, Report 2012/298, 2012.Google Scholar
- F. Baldimtsi and A. Lysyanskaya. On the security of one-witness blind signature schemes. Cryptology ePrint Archive, Report 2012/197, 2012.Google Scholar
- M. Belenkiy, M. Chase, M. Kohlweiss, and A. Lysyanskaya. Compact e-cash and simulatable vrfs revisited. In Pairing '09, pages 114--131, 2009. Google ScholarDigital Library
- P. Bichsel, J. Camenisch, T. Groß, and V. Shoup. Anonymous credentials on a standard java card. CCS '09, pages 600--610. ACM, 2009. Google ScholarDigital Library
- A. Boldyreva. Threshold signatures, multisignatures and blind signatures based on the gap-diffie-hellman-group signature scheme. PKC '03, pages 31--46, London, UK, UK, 2003. Springer-Verlag. Google ScholarDigital Library
- S. Brands. Untraceable off-line cash in wallets with observers. In CRYPTO'93, pages 302--318, 1993. Google ScholarDigital Library
- S. A. Brands. Rethinking public key infrastructures and digital certificates: Building in privacy. MIT Press, Cambridge-London, August 2000. Google ScholarDigital Library
- J. Camenisch and T. Groß. Efficient attributes for anonymous credentials. In Proceedings of the 15th ACM conference on Computer and communications security, CCS '08, 2008. Google ScholarDigital Library
- J. Camenisch, S. Hohenberger, and A. Lysyanskaya. Compact e-cash. In EUROCRYPT '05, volume 3494 of LNCS, pages 302--321. Springer-Verlag, 2005. Google ScholarDigital Library
- J. Camenisch, M. Koprowski, and B. Warinschi. Efficient blind signatures without random oracles. SCN'04, pages 134--148, 2005. Google ScholarDigital Library
- J. Camenisch and A. Lysyanskaya. An efficient system for non-transferable anonymous credentials with optional anonymity revocation. EUROCRYPT '01, pages 93--118, London, UK, 2001. Springer-Verlag. Google ScholarDigital Library
- J. Camenisch and A. Lysyanskaya. Signature schemes and anonymous credentials from bilinear maps. In CRYPTO'04, LNCS 3152, pages 56 -- 72, 2004.Google ScholarCross Ref
- J. Camenisch and M. Michels. Proving in zero-knowledge that a number is the product of two safe primes. EUROCRYPT'99. Springer-Verlag, 1999. Google ScholarDigital Library
- J. Camenisch, F.-H. Simone, and K. Rannenberg. Privacy and identity management for life. In ISBN 978--3--642--20316--9. Springer, 2012. Google ScholarDigital Library
- D. Chaum. Blind signatures for untraceable payment. In Crypto'82, pages 199--203, 1982.Google Scholar
- R. Cramer, I. Damgård, and B. Schoenmakers. Proofs of partial knowledge and simplified design of witness hiding protocols. In CRYPTO '94, pages 174--187. Springer-Verlag, 1994. Google ScholarDigital Library
- I. Damgård. Commitment schemes and zero-knowledge protocols. In Lectures on Data Security, Modern Cryptology in Theory and Practice, Summer School, Aarhus, Denmark, July 1998. Springer-Verlag, 1999. Google ScholarDigital Library
- I. Damgård. On σ- protocols. In Course Notes, http://www.daimi.au.dk/ ivan/Sigma.ps, 2002.Google Scholar
- A. Fiat and A. Shamir. How to prove yourself: Practical solutions to identification and signature problems. In CRYPTO '86, pages 186--194. Springer-Verlag, 1986. Google ScholarDigital Library
- S. Garg, V. Rao, A. Sahai, D. Schröder, and D. Unruh. Round optimal blind signatures. In CRYPTO'11, pages 630--648, 2011. Google ScholarDigital Library
- O. Goldreich. Foundations of Cryptography, vol. 1: Basic Tools. Cambridge University Press, 2001. Google ScholarDigital Library
- S. Goldwasser, S. Micali, and C. Rackoff. The knowledge complexity of interactive proof systems. SIAM J. Comput., 18:186--208, February 1989. Google ScholarDigital Library
- J. Guajardo, B. Mennink, and B. Schoenmakers. Anonymous credential schemes with encrypted attributes. In Cryptology and Network Security, pages 314--333. Springer, 2010.Google ScholarCross Ref
- L. C. Guillou and J.-J. Quisquater. A practical zero-knowledge protocol fitted to security microprocessor minimizing both transmission and memory. In EUROCRYPT '88, pages 123--128, 1988. Google ScholarDigital Library
- N. Gura, A. Patel, A. Wander, H. Eberle, and S. C. Shantz. Comparing elliptic curve cryptography and rsa on 8-bit cpus. In CHES'04, pages 119--132, 2004.Google ScholarCross Ref
- G. Hinterw\"alder, C. T. Zenger, F. Baldimtsi, A. Lysyanskaya, C. Paar, and W. P. Burleson. Efficient e-cash in practice: NFC-based payments for public transportation systems. In Privacy Enhancing Technologies - PETS'13, pages 40--59, 2013.Google Scholar
- A. Juels, M. Luby, and R. Ostrovsky. Security of blind digital signatures (extended abstract). In CRYPTO'97, pages 150--164. Springer-Verlag, 1997. Google ScholarDigital Library
- M. Langheinrich. Privacy by design - principles of privacy - aware ubiquitous systems. In Ubicomp 2001: Ubiquitous Computing, volume 2201, pages 273--291. Springer Berlin, Heidelberg, 2001. Google Scholar
- A. J. Menezes, P. C. V. Oorschot, and S. A. Vanstone. Handbook of applied cryptography, 1997. Google ScholarDigital Library
- NIST. The case for elliptic curve cryptography, 2009. http://www.nsa.gov/business/programs/elliptic_curve.shtml.Google Scholar
- M. Ohkubo and M. Abe. Security of three-move blind signature schemes reconsidered. In SCIS'03, Symposium on Cryptography and Information Security, 2003.Google Scholar
- T. Okamoto. Efficient blind and partially blind signatures without random oracles. In TCC'06, volume 3876 of Lecture Notes in Computer Science, pages 80--99. Springer, 2006. Google ScholarDigital Library
- C. Paquin. U-prove cryptographic specification v1.1. In Microsoft Technical Report, http://connect.microsoft.com/site1188, February 2011.Google Scholar
- E. Parliament and C. of the European Union. Regulation (ec) 45/2001. In Official Journal of the European Union, 2001.Google Scholar
- E. Parliament and C. of the European Union. Directive 2009/136/ec. In Official Journal of the European Union, 2009.Google Scholar
- T. P. Pedersen. Non-interactive and information-theoretic secure verifiable secret sharing. CRYPTO '91. Springer-Verlag. Google ScholarDigital Library
- D. Pointcheval and J. Stern. Security arguments for digital signatures and blind signatures. In Journal Of Cryptology, volume 13, pages 361--396, 2000.Google ScholarDigital Library
- D. Pointcheval and J. Stern. Provably secure blind signature schemes. In Asiacrypt '96, LNCS 1163, pages 252--265. Springer-Verlag, Feb 2011. Google ScholarDigital Library
- H. A. Schmidt. National strategy for trusted identities in cyberspace. In Cyberwar Resources Guide, Item 163, http://www.projectcyw-d.org/resources/items/show/163, 2010.Google Scholar
- C. P. Schnorr. Efficient identification and signatures for smart cards. CRYPTO '89, pages 239--252, 1989. Google ScholarDigital Library
- I. S. Team. Specification of the identity mixer cryptographic library, version 2.3.0. In IBM Research Report, 2010.Google Scholar
- G. J. R. B. Zhang, H. and K. Fu. Moo: A batteryless computational rfid and sensing platform. In Tech. Rep. UM-CS-2011-020, UMass Amherst Department of Computer Science, 2011.Google Scholar
Index Terms
- Anonymous credentials light
Recommendations
Algebraic MACs and Keyed-Verification Anonymous Credentials
CCS '14: Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications SecurityWe consider the problem of constructing anonymous credentials for use in a setting where the issuer of credentials is also the verifier, or more generally where the issuer and verifier have a shared key. In this setting we can use message authentication ...
Privacy-Enhancing Proxy Signatures from Non-interactive Anonymous Credentials
DBSec 2014: Proceedings of the 28th Annual IFIP WG 11.3 Working Conference on Data and Applications Security and Privacy XXVIII - Volume 8566Proxy signatures enable an originator to delegate the signing rights for a restricted set of messages to a proxy. The proxy is then able to produce valid signatures only for messages from this delegated set on behalf of the originator. Recently, two ...
Commuting signatures and verifiable encryption
EUROCRYPT'11: Proceedings of the 30th Annual international conference on Theory and applications of cryptographic techniques: advances in cryptologyVerifiable encryption allows one to encrypt a signature while preserving its public verifiability. We introduce a new primitive called commuting signatures and verifiable encryption that extends this in multiple ways, such as enabling encryption of both ...
Comments