Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?
share|improve this question
1) How about counting them? 2) There is no general answer: Which platform (server, desktop, mobile, sensor,...), which language (C, Java,...), etc.? – DrLecter Dec 10 '14 at 19:11
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. – user11254 Dec 12 '14 at 8:51
What about implementing the scheme using an existing pairing library? – DrLecter Dec 12 '14 at 9:01
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. – user11254 Dec 12 '14 at 9:15
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. – DrLecter Dec 12 '14 at 9:22

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.