I'm using the Boneh-Boyen-Shacham signature scheme and want to estimate complexity in my scheme.

As reported in "Scott M., Efficient Implementation of Cryptographic pairings", if we set parameters as: MNT curve, k=6 and p~160, then P(point mul)=0.6 ms and P(pairing)=4.5 ms.

These two measured times are used in many references. I found another reference (Lu, Rongxing, et al. "A dynamic privacy-preserving key management scheme for location-based services in vanets.") stating P(point exponentiation)=0.6 ms and P(pair)=4.5 ms.

I cannot understand how can I compute processing time for multiplication and exponentiation operations in BBS scheme in following image…

image copy of referred scheme


  1. How many multiplications and exponentiations do we need, and
  2. what is the processing time of each operation?
  • $\begingroup$ 1) How about counting them? 2) There is no general answer: Which platform (server, desktop, mobile, sensor,...), which language (C, Java,...), etc.? $\endgroup$ – DrLecter Dec 10 '14 at 19:11
  • $\begingroup$ counting number of elliptic curve point multiplication operations and number of exponentiation for computing time of signature. platform is a base station with a processing power at the desktop level with a low-level language like C. for example a sample is stated in "Scott M., Efficient Implementation of Cryptographic pairings": 32-bit 3GHz PIV, Tate pairing, k=6, p~160 bits MNT curve. $\endgroup$ – Parham Dec 12 '14 at 8:51
  • $\begingroup$ What about implementing the scheme using an existing pairing library? $\endgroup$ – DrLecter Dec 12 '14 at 9:01
  • $\begingroup$ I'm using this signature scheme in my protocol. I'm computing time complexity and i want to compare calculated formula for time complexity with the experimental results. So i need to know number of operations and time of them. $\endgroup$ – Parham Dec 12 '14 at 9:15
  • $\begingroup$ Yes, take some existing pairing library and benchmark the single required operations on your platform. Count the number of respective operations required by the BBS scheme, sum everthing together and there you go. $\endgroup$ – DrLecter Dec 12 '14 at 9:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.