Anonymous Multi-Vendor Micropayment Scheme based on Bilinear
Contents
1. operation 3 Helper oracle Oy is constructed in a way that for an input m first calls the target oracle Or to calculate a H m then If b 0 then S terminates Otherwise signature o cjyP ra y r cP is returned back Observe that o is a valid signature for m under the public key Y rP 4 Adversary A asks the target oracle Or to calculate hash of m and with the help of H m provides a list of message certificate pairs m1 01 Mt Ct that contains the m o pair Ifo is not a valid signature for m then S terminates Otherwise S looks for m from the list of Orp Let denote this tuple by m a b c If b 1 then S terminates if b 0 then S calculates o rm ra We remark that a m cP and assuming that is valid o rm rcP y r m cP rm rceP y m cP S outputs m c yP for all signatures that are generated with the help of Oy and m o rm rcP Observe that S outputs a correct signature on m We prove that S generates the correct output with non negligible probability We consider the situation when S does not terminate There are events that should happen 1 For certificate queries S does not terminate i e b 1 9 For message m in the m a b c tuple b 0 3 A provides valid m o pair Let us denote the probability that S succeeds by Pr e It is easy to see that Pre Priey A 2 A 3 Prlei Prleg ei Prie2. plish necessary security requirements reducing both financial and computational costs We also give a detailed computational security evaluation of our scheme Most of the proposed micropayment schemes do not prove security properties There are few solutions 1 9 that give formal security evaluation based on applied pi calculus 14 with the help of automatic protocol verifier called Proverif 3 We prove that our scheme provides secure payment authorization under the chosen target Computational Diffie Hellman assumption in the random oracle model and customer s anonymity and coin unreusability against any passive adversary with unlimited computational power The rest of the paper is organized as follows Basic definitions notation and building blocks are given in section 2 In section 3 the proposed micropayment scheme is detailed Section 4 contains the security evaluation of the scheme starting with the definitions of the requirements that followed by the proofs At the end time and space complexity are given and the conclusion 2 Preliminaries 2 1 Definitions notation In order to give a security evaluation we review some basic definitions notation A negligible function is a function A such that for all polynomials poly A A lt 1 poly A holds for all sufficient large A We call an algorithm efficient if it is a probabilistic Turing machine running in expected polynomial time An adversary A is a PPT probabi
3. w vt P from w and verifies whether e o P e H wiv P bP and stores w The customer starts spending the coins with wi W5 etc After receiving wi the vendor verifies whether H w equals to the value stored If the verification holds then the vendor stores wi and sends the product Observe that for the verification processes the broker does not need to be available Vendor Broker relationship After receiving a few coins that can happen at the end of the day or after few days the vendor starts to redeem them He sends 0 wi w l to the bro ker The broker verifies the certificate by calculating H wiv P and bH wiv P and correctness of the last coin by H w wi If all verifications hold then transfers the proper amount to the vendor 4 Security evaluation 4 1 Security requirements We consider three security requirements for micropayment schemes anonymity secure payment authorization and unreusability We define anonymity and secure payment authorization properties via experiments involving an adversary A and the challenger Payment authorization guarantees a proof for the vendor that there is suffi cient fund on the user s account This proof or certificate is created by the broker Secure payment authorization is achieved if the certificate is undeniable Definition 6 Secure Payment Authorization The experiment is parameter ized by security parameter and l 1 The challenger generates the public
4. 3 ea Assuming there are ny 1 target oracle queries Pr e 1 me gt where e denotes the base of the natural logarithm Similarly Pr e2 aa The probability of event 3 is the advantage Adus AA Therefore Pre gt Adu SAA Since Advis a is non negligible Pr e is also non negligible We show that S is efficient S makes nr hash and ny signature queries for each signature query a hash query also happen Including calculating the output efficiency of S is nr 3ng 2 MULT and ny 2 ADD where MULT and ADD denote operations multiplication and addition in the GDH group Theorem 2 Anonymity coin unreusability The proposed micropayment scheme provides customer s anonymity and coin unreusability against any passive adver sary with unlimited computational power Proof First we deal with the customer s anonymity It is sufficient to prove that for any view p ID e of the adversary A and any message certificate pair wo a there exists a blind factor that maps the view and the message certificate pair Let p 1D for i 0 1 two views of A and w4 o two message signature pairs from customer 7 0 1 Since A colludes with the Broker and all the Vendors we assume that A observes two views that correspond to the same Vendor with keys v vP We state that with the knowledge of vP s p Hov is a correct blind factor for any pf ID w4 07 pairs Since so H wivP bH wiuP b
5. Anonymous Multi Vendor Micropayment Scheme based on Bilinear Maps Andrea Huszti Faculty of Informatics University of Debrecen 26 Kassai St H4028 Debrecen Hungary huszti andrea inf unideb hu Keywords micropayment multi vendor anonymous bilinear maps Abstract A hash based micropayment scheme is introduced that takes advantage of good properties of bilinear maps provides anonymity of the customers and makes it possible to shop at multiple vendors The pro posed scheme minimizes computational and financial costs We proved that it possesses secure payment authorization under the chosen target Computational Diffie Hellman assumption in the random oracle model and customer s anonymity and coin unreusability against any passive adversary with unlimited computational power 1 Introduction Micropayment schemes were invented as a consequence of Internet applications In particular there are content and service providers that charge very small amount e g less than a dollar The usual online purchasing method payment by credit cards requires minimal transaction fee and other extra costs hence it is not applicable for charging small amounts Special payment systems so called micropayment schemes are required One can read an overview of micropayment schemes in 17 Designing micropayment schemes requires special care First of all electronic payment systems deal with personal confidential financial data that should be prot
6. al Diffie Hellman as sumption in the random oracle model Proof We prove the security of our scheme by contradiction in the random oracle model We suppose our scheme is not secure there exists an adversary A that is able to break secure payment authorization of the scheme If A exists then we are able to build an efficient simulator algorithm S that with the help of A succeeds in breaking the chosen target CDH assumption that leads to a contradiction Let Gi lt P gt and G2 be groups of prime order q where G is a GDH group and given e G1 x GiG G2 After key generation simulator S receives public key Y yP where y Z is the secret key With the knowledge of P q Gi Ge e Y algorithm S simulates the challenger for A in the following 1 S provides A public parameters P q Gi G2 e and also gives Y rP asa public key where r lt Z 2 In order to respond valid certificates S has access to a target oracle Or and a helper oracle Oy Or works as follows S maintains a list of tuples Mi ai bi Ci that is empty at the beginning For a hash request of a message mi E Gy If m is on the list then S outputs a as a hash value Otherwise S generates a random bit b with Pr b 0 E probability chooses c Zj and calculates a 1 b m cP Finally S inserts Mi ai bi ci to the list Observe that a is uniform in G and independent of A s view hence S perfectly simulates the real has query
7. des about the Vendors where he would like to shop Let us denote the number of chosen Vendors by k For each Vendor he generates a hash chain The elements of the chain are the coins Random values w Z where i 1 amp are generated and the hash chain elements wi H w 41 where j n 1 0 are calculated We call values wih commitment values These commitment values are made vendor specific by a multiplication w v P where vt P is the Vendor s public key A Customer requires the Broker s authorization via a blind signature scheme he generates r Z sends p r H wjv P and his identity number ID to the Broker on an open channel He also calculates k T X H wiv P i 1 The Broker authenticates the Customer in a secure way The entity authen tication and authorization might happen even off line The Broker debits the proper amount on the Customer s account and sends bri H wivi P where i 1 k back The Customer after receiving the messages with the knowledge of rt calcu lates of bH w v P and k k A 5 bH wav P DD H wut P i 1 i 1 The Customer verifies whether e I bP e A P Observe that the Customer in order to verify all the signatures calculates only two bilinear maps Customer Vendor relationship In order to start the shopping process with Vendor i the Customer sends the certificate of bH wjv P and commitment value w on an open chan nel The vendor calculates H
8. ected against malicious attackers On the other hand financial and also computational costs should be minimized In order to minimize financial costs the e payment scheme should be off line that means the broker is off line during the shopping process i e broker is not required to verify whether users can cover their payments or not We can decrease customers expenses if they do not have to possess signature certificates either Computational costs especially for customers during the shopping process should be reduced Usually slow asymmetric cryptographic building blocks should be avoided One of the most well known hash based micropayment scheme is the Pay Word scheme 13 introduced in 1997 PayWord is not anonymous and designed to be one vendor thus if we apply it for multiple vendors it does not protect against double spending Our scheme is multi vendor and provides anonymity for the customers Com paring to other protocols in the literature in order to accomplish multi vendor property we do not use blacklists 15 16 that means brokers maintain a list of users who did not pay for the products or services In 2003 Payeras Capella Ferrer Gomila and Huguet Rotger designed an anonymous hash based scheme see 12 that is semi offline i e every time when a customer is willing to switch to another vendor he should contact with the broker to get the authorized cer tificate Therefore in 12 if a customer shops at k vendo
9. eil pairing Ad vances in Cryptology ASIACRYPT 2001 Vol 2248 of LNCS 2001 514532 Full version Journal of Cryptology 17 2004 297319 6 G Frey H Ruck A remark concerning m divisibility and the discrete logarithm in the divisor class group of curves Mathematics of Computation 62 1994 865 874 7 S Hohenberger Advances in Signatures Encryption and E Cash from Bilinear Groups PhD Dissertation 2006 8 M Hosseinkhani E Tarameshloo M Shajari AMVPayword Secure and Effi cient Anonymous Payword Based Micropayment Scheme International Conference on Computational Intelligence and Security CIS 2010 551 555 9 A Huszti Multi Vendor PayWord with Payment Approval Proceedings of the 2013 International Conference on Security and Management CSREA Press 2013 265 271 10 A Joux A One Round Protocol for Tripartic Diffie Hellman Proceedings of 4th International Symposium of Algorithmic Number Theory Vol 1838 of LNCS 2000 385 394 11 A Menezes T Okamoto S Vanstone Reducing Elliptic Curve Logarithms to Log arithms in a finite field IEEE Transaction of Information Theory Vol 39 1993 1639 1646 12 M Payeras Capella J L Ferrer Gomila L Huguet Rotger An efficient anony mous scheme for secure micropayments Web Engineering Lecture Notes in Com puter Science 2722 2003 80 83 Springer Verlag 13 R Rivest A Shamir PayWord and MicroMint Two simple micropayment schemes Security Protocol
10. listic polynomial time interactive Turing machine For a finite set X let x X denote the algorithm that samples an element uniformly random from X Our micropayment scheme is based on bilinear pairings Let us review the definition of the admissible bilinear map 2 Definition 1 Let Gy and G2 be two groups of order q for some large prime q A map e Gy x Gi gt Go is an admissible bilinear map if satisfies the following properties 1 Bilinear We say that a map e Gi x Gi gt G is bilinear if e aP bQ e P Q for all P Q G and alla b Z 2 Non degenerate The map does not send all pairs in Gi x Gy to the identity in Gp Since Gi Ga are groups of prime order if P is a generator of Gy then e P P is a generator of G2 3 Computable There is an efficient algorithm to compute e P Q for any P Q E G1 We should mention that bilinearity can be restated to for all P Q R Gi e P Q R e P R e Q R and e P Q R e P Q e P R We can find G and G2 where these properties hold The Weil and Tate pairings prove the existence of such constructions Typically G1 is an elliptic curve group and G2 is a finite field Let us review the relevant security problems Definition 2 Let P aP bP are given for some a b Z The problem of com puting abP is called Computational Diffie Hellman problem CDHP in G1 We assume that CDHP is intractable which means there is no polynomial time algorithm to solve CDHP with no
11. me provides secure payment authorization under the chosen target Computational Diffie Hellman assumption in the random ora cle model and customer s anonymity and coin unreusability against any passive adversary with unlimited computational power Acknowledgment The publication was supported by the TAMOP 4 2 2 C 11 1 KONV 2012 0001 project The project has been supported by the European Union co financed by the European Social Fund The author is also supported by the Hungarian National Foundation for Scientific Research Grant No K75566 and NK 104208 References 1 L Aszal s A Huszti Payment Approval for PayWord D H Lee M Yung Eds Information Security Applications 13th International Workshop WISA 2012 Lec ture Notes in Computer Science 7690 2012 161 176 Springer Verlag 2 Dan Boneh and Matthew Franklin Identity based encryption from the Weil pairing Advances in Cryptography Proceedings of Crypto 2001 Vol 2139 of LNCS 2001 213 229 3 B Blanchet B Smyth ProVerif 1 85 Automatic Cryptographic Protocol Verifier User Manual and Tutorial http www proverif ens fr manual pdf 2011 4 A Boldyreva Threshold Signatures Multisignatures and Blind Signatures Based on the Gap Diffie Hellman Group Signature Scheme International Workshop on Theory and Practice in Public Key Cryptography PKC 2003 Proceedings Vol 2567 of LNCS 2003 31 46 5 D Boneh B Lynn and H Shacham Short signatures from the W
12. nnegligible probability Definition 3 Let P aP bP cP are given for some a b c Z The problem of deciding whether c ab mod q is called Decisional Diffie Hellman problem DDHP in Gy DDH problem in G can be solved in polynomial time by verifying e aP bP e P cP hence DDH problem in G is easy Definition 4 When DDHP is easy but the CDHP is hard on the group G1 we call Gi a Gap Diffie Hellman GDH group Such groups can be found on supersingular elliptic curves or hyperelliptic curves over a finite field 2 2 Building blocks In the proposed scheme we apply a blind signature scheme given in 4 that works as follows Let G be a GDH group P G a generator of G and H 0 1 gt is a one way hash function We assume a bilinear map e G1 x G1 gt G2 is given The signer randomly chooses s Z and calculates sP Users hold the public key PK G1 P H sP In order to blindly sign a message M 0 1 the user picks a random number r Z computes M rH M and sends it to the signer The signer knows secret key SK s computes F sM and sends it to the user The users computes o r sH M and outputs M 0 Signature on M is a valid since e H M sP e sH M P Signatures we receive in this way are called short signatures 5 and have many useful features They are approximately 170 bits long instead of 320 or 1024 having the same security level In protocols dealing with many signatures
13. originating from the same user bilinear short signatures can be verified in an aggregate way calculating only two bilinear maps Hence we can significantly increase efficiency We use bilinear blind short signatures to authorize the coin commitment values and also provide customer s anonymity Security of this blind signature scheme is based on the chosen target CDH problem in G4 Definition 5 chosen target CDH assumption Let G lt P gt be a GDH group of prime order q and y lt Z be a secret and Y yP a public key generated according to security parameter A The adversary is given P G q Y and has access to a target oracle Or that returns random points Zi from G and also a helper oracle Oy that calculates yQ for an input point Q Let nr and ny denote the number of queries the adversary can make to the target and helper oracle respectively Adversary A outputs X1 j1 Xi j1 The advantage of the adversary Adug 7 A defined by PrVl lt i lt ldl lt j lt nr Xi yZ Xi are distinct A ny lt nz The chosen target Computational Diffie Hellman assumption states that for all PPT adversary Adug PF A is negligible Observe that if the adversary A makes exactly one query to the Or then the chosen target CDH assumption is equivalent to the standard CDH assumption We assume that chosen target CDH problem is intractable for all groups where the standard CDH problem is hard 3 The proposed scheme Le
14. p It is easy to see that even if A knows the Broker s and Vendors secret and public keys b bP vt vt P for i 1 k adversary A does not gain more knowledge about the chosen blind factor l Since p ID and pt ID et have the same relation to wi of any adversary with unlimited computational power can guess j correctly with prob ability exactly 1 2 Let us prove coin unreusability of the scheme We assume that a passive adversary A possesses a valid certificate o bH wjv P and the commitment value wij that are sent to vendor i with public key v P Without the loss of generality we consider double spending of w We assume that coin wt is already sent once hence vendor i stores wf as the last coin in the database Resending these values to a vendor leads to two cases 1 Tuple of w w is sent to vendor i The vendor notice that these values are already received before and checks whether H wi is the stored value 2 Tuple o wi wi is sent to vendor j where i 4 j The vendor looks for the certificate in his database since he does not find it verifies the validity of o by testing e H wivs P bP e o P In both cases the vendor detects double spending 5 Comments Due to their good properties bilinear maps are often used in cryptographic protocols Some pairing based constructions provide breakthroughs that other techniques cannot We take advantage of aggregate signature verifica
15. rs then k signature ver ifications are needed by the customer We designed our solution to be off line In 2010 Hosseinkhani Tarameshloo and Shajari in 8 introduced an anonymous multi vendor hash based scheme They achieved anonymity via an Insert Ticket that is different for different customers and makes it possible to insert values in the broker s database This database contains information about the customer s last spent coin and vendors check it for every purchase In this scheme double spending protection is achieved via an all time available on line database that increases costs Bilinear pairings namely Weil pairing and Tate pairing of algebraic curves were used in cryptography for MOV attack 11 using Weil pairing and FR attack 6 using Tate pairing These attacks reduce the discrete logarithm problem on some elliptic or hyperelliptic curves to the discrete logarithm problem in a finite field Bilinear pairings have recently been used to design cryptographic proto cols since as a consequence new constructions of primitives appeared These primitives either cannot be built using other techniques e g three party one round Diffie Hellman key agreement in 10 Identity based encryption in 2 or they can be created via traditional methods but pairings provide improved functionality e g threshold signature multisignature blind signature 4 Here we show how these new primitives can be applied in micropayments to accom
16. s 1997 69 87 14 M D Ryan B Smyth Applied pi calculus Formal Models and Techniques for Analyzing Security Protocols 2011 chapter 6 15 C T Wang C C Chang C H Lin A new micro payment system using general payword chain Electronic Commerce Research 2 2002 159 168 16 H Wang J Ma J Sun Micro payment protocol based on multiple hash chains Second International Symposium on Electronic Commerce and Security 1 2009 71 74 17 Weidong Kou Payment Technologies for E Commerce Springer 1998
17. system parameters which include groups G lt P gt G2 and the bilinear map e runs key generation algorithm for the input 1 gt Public keys are given to the adversarial user A 2 Adversary A makes polynomial number certificate queries from the Broker The Broker provides valid certificates to A 3 Adversary A outputs a list of message certificate pairs m1 01 Me ct We define the advantage of A by Adugfgia A PrlV1 lt i lt t Verpx mi oi 1Al lt t where Verpx mi o 1 denotes that certificate o is valid for message mi A micropayment scheme provides secure payment authorization if for all PPT adversary Adui AA is negligible where probability is taken over the coin flips of A as well as the random coins used in the experiment for key generation A chooses a random value w that is different from the previous ones and must then produce a valid signature on H wv P If he can produce any such document signature pair which is accepted by the verication algorithm then the attack is successful There are situations when customers do not want to reveal their real identity during their shopping process We also consider providing anonymity for the users Definition 7 Anonymity The experiment is parameterized by security param eter and a bit b 1 The challenger generates the public system parameters which include groups G lt P gt G2 and the bilinear map e Broker s and Vendors secre
18. t and public keys are generated for input 1 and they are given to the adversarial user A 2 Adversary A outputs a pair of identity numbers ID ID that represent two different customers 3 The protocol is run with the customer possessing ID and adversary A where b is the randomly chosen input bit 4 Adversary A outputs a bit b according to the knowledge A gained colluding with the Broker and the Vendors We define the advantage of A by Adoi gA A 2Pr b b 1 A micropayment scheme provides customer anonymity if for all PPT adver sary Adugpe A is negligible where probability is taken over the coin flips of A as well as the random coins used in the experiment for key and identity number generation The proposed micropayment scheme is off line hence the Broker is not able to prevent double spending Being a multi vendor scheme we show that coins already spent are not reusable neither at the same vendor nor at different ones Definition 8 Coin unreusability A micropayment scheme provides coin un reusability if an adversary resends a coin that was already spent before then the vendor detects it with overwhelming probability 4 2 Results In this section we show that our proposed scheme is secure i e it provides payment authorization user s anonymity and coin unreusability Theorem 1 Payment authorization The proposed scheme provides secure pay ment authorization under the chosen target Computation
19. t us introduce our micropayment scheme We consider the following partici pants There is a Broker that authorizes the coins and checks whether there is sufficient fund on user s account There are k Vendors that sell their products and there are several Customers who intend to shop at more then one Vendor In order to run the protocol system parameters secret and public keys are generated First of all bilinear map e G1 x G1 gt Gp is set determining groups G lt P gt G with prime order q A security parameter and two hash functions are chosen H Gi G is necessary for signature generation and H Z gt Z is used for generating the coins Secret and public keys are generated for the Broker and all the Vendors The length of the keys depends on the security parameter A The Broker s key pair is SK PK b bP where b Zj and SK denotes the secret and PK the public key Broker s secret key is used for signature generation the public key for signature verification Similarly all Vendors receive SK PK vt v P key pairs where vt Z a In the proposed scheme Customers are not required to possess a key pair The scheme consists of three stages In the first stage Customers apply for the Broker s authorization on their coins During the second stage Customers proceed their shopping with the Vendors and at the end Vendors redeem the coins at the Broker Customer Broker relationship A Customer first deci
20. tion in effi ciency We achieved that customers verify all the certificates by calculating only two bilinear maps Customers time complexity during the shopping process is very low only hash calculations are made In the registration process that happens only once customers compute 2k multiplications 2k additions and k multiplicative inverses in G and only two bilinear maps We refer to 7 that one supersingular mapping e Gi xX Gi Gp is approximately equal to eight multiplications in G for a security level of 256 bits Vendors time complexity is only one multiplication and a hash calculation in G and two bilinear map computations per a customer Brokers proceed k multiplications in G4 per a customer during registration and two multiplications in G per a certificate besides hash calculations Considering implementation of our scheme the Broker is off line and cus tomers do not need to have certificates hence we minimized financial expenses Our scheme minimizes space complexity on the user side Users store k hash root values for calculating hash chain elements with the indexes that show which coins were spent already and also store k short signatures 6 Conclusion Bilinear maps are used for broad wide of cryptographic applications We intro duced a hash based micropayment scheme that is anonymous and multi vendor By using bilinear maps we increased efficiency and decreased space complexity We also proved that our sche
Download Pdf Manuals
Related Search