How to Win the Clone Wars:Efficient Periodic n-Times Anonymous AuthenticationJan CamenischZurich Research LabIBM [email protected] HohenbergerZurich Research LabIBM [email protected] KohlweissDept. of Electrical EngineeringKatholieke Universiteit [email protected] LysyanskayaComputer Science Dept.Brown [email protected] MeyerovichComputer Science Dept.Brown [email protected] create a credential system that lets a user anonymouslyauthenticate at most n times in a single time period. Auser withdraws a dispenser of n e-tokens. She shows an e-token to a verifier to authenticate herself; each e-token canbe used only once, however, the dispenser automatically re-freshes every time period. The only prior solution to thisproblem, due to Damg˚ard et al. [29], uses protocols thatare a factor of k slower for the user and verifier, whe re kis the security parameter. Damg˚ard et al. also only sup-port one authentication p e r time period, while we supportn. Because our construction is based on e-cash, we can useexisting techniques to identify a cheating user, trace all ofher e-tokens, and revoke her dispensers. We also offer anew anonymity service: glitch protection for basically hon-est users who (occasionally) reuse e-tokens. The verifier canalways recognize a reused e-token; however, we preserve theanonymity of users who do not reuse e-tokens too often.Categories and Subject Descriptors: K.6.5 [Securityand Protection]:Authentication.General Terms: Security, Algorithms.Keywords: n-anonymous authentication, clone detection,credentials.1. INTRODUCTIONAs computer devices get smaller and less intrusive, it be-comes possible to place them everywhere and use them tocollect information about their environment. For example,with today’s technology, sensors mounted on vehicles mayreport to a central traffic service which parts of the roadsPermission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.CCS’06, October 30–November 3, 2006, Alexandria, Virginia, USA.Copyright 2006 ACM 1-59593-518-5/06/0010 ...$5.00.are treacherous, thus assisting people in planning their com-mutes. Some have proposed mounting sensors in refrigera-tors to report the consumption statistics of a household,thus aiding in public health studies, or even mounting themin people’s bodies in an attempt to aid medical science. Inall these areas, better information may ultimately lead to abetter quality of life.Yet this vision appears to be incompatible with privacy.A sensor installed in a particular car will divulge that car’slocation, while one installed in a fridge will report the eatingand drinking habits of its owner.A naive solution would be to supply only the relevantinformation and nothing else.1A report about the roadconditions should not s ay which sensor made the measure-ment. However, then nothing would stop a malicious partyfrom supplying lots of false and m is leadi ng data. We needto authenticate the information reported by a sensor with-out divulging the sensor’s identity. We also need a way todeal with rogue sensors, i.e., formerly honest sensors withvalid cryptographic keys that are captured by a maliciousadversary and used to send lots of misleading data.The same problem arises in other scenarios. Consider aninteractive computer game. Each player must have a licenseto participate, and prove this fact to an on-line authorityevery time she wishes to play. For privacy reasons, the playerdo e s not wish to reveal anything other than the fact thatshe has a license. How can we prevent a million users fromplaying the game for the price of just one license?A suite of cryptographic primitives such as group signa-tures [27, 21, 1, 6] and anonymous credentials [25, 30, 39,14, 16, 17] has been developed to let us prove that a pieceof data comes from an authorized source without revealingthe identity of that particular source. However, none of theresults cited above provide a way to ensure anonymity andunlinkability of honest participants while at the same timeguaranteeing that a rogue cannot undetectably provide mis-leading data in bulk. Indeed, it seems that the ability toprovide false data is a consequence of anonymity.1Divulging the relevant information alone may already con-stitute a breach of privacy. This has to do with statisticalprop e rties of the data itself. See Sweeney [46] and Chawlaet al. [28] on the challenges of determining which data is andis not safe to reveal.Recently Damg˚ard, Dupont and Pedersen [29] presented ascheme that overcomes this seem ing paradox. The goal is toallow an honest participant to anonymously and unlinkablysubmit data at a small rate (for example, reporting on roadconditions once every fifteen minutes, or joining one gamesession every half an hour), and at the same time to havea way to identify participants that submit data more fre-quently. This limits the amount of false information a roguesensor can provide or the numb er of times that a given soft-ware license can be used per time period.While the work of Damg˚ard et al. is the first step in theright direction, their approach yields a prohibitively expen-sive solution. To authenticate itself, a sensor acts as a proverin a zero-knowledge (ZK) proof of knowledge of a relevantcertificate. In their construction, the zero-knowledge prop-erty crucially depends on the fact that the prover must makesome random choices; should the prover ever re-use the ran-dom choices he made, the prover’s secrets can be efficientlycomputed from the two transcripts. The sens or’s randomchoices are a pseudorandom function of the current timeperiod (which must be proven in an additional ZK proofproto col). If a rogue sensor tries to submit more data in thesame time period, he will have to use the same randomnessin the proof, thus exposing his identity. It is very challeng-ing to instantiate this solution with efficient building blocks.Damg˚ard et al. use the most efficient building blocks avail-able, and also introduce some of their own; their schemerequires that the user perform 57+68k exponentiations toauthenticate,
View Full Document
Unlocking...