1
$\begingroup$

I want to implement this credential system: “Anonymous Credentials Light” (PDF). The implementation would involve some zero-knowledge proof and some exponentiation.

For some basic group computations like $g^x$, do people usually just come up with their own implementation or is there some famous library that provides such basic operations? If, what would be some of the possible libraries or implementations I could (or should) start with?

Improve this question
$\endgroup$
9
  • $\begingroup$ There is no "best", because it's highly subjective. Have a look at Charm Crypto or Sage Math. $\endgroup$
    – Artjom B.
    Dec 21, 2015 at 17:24
  • $\begingroup$ You can look at SCAPI; it has many features built in, including ZK proofs. See github.com/cryptobiu/scapi. $\endgroup$
    – Yehuda Lindell
    Dec 21, 2015 at 17:35
  • $\begingroup$ You can check PBC library for pairings and the for math operations the GMP library. Then Charm crypto abstracts a lot of useful basic crypto operations $\endgroup$
    – curious
    Dec 21, 2015 at 19:45
  • $\begingroup$ The paper you mentioned has implementation results here homepage.rub.de/andy.rupp/papers/p4r_full.pdf $\endgroup$
    – curious
    Dec 21, 2015 at 19:50
  • $\begingroup$ Thanks for the comments. They're really helpful. I'm not really looking for the "best" library. I just wanna know what's out there so that I can take a look at them for myself. I've edited my question. Hopefully it complies with the rules now. $\endgroup$
    – Hongyang
    Dec 21, 2015 at 21:44

1 Answer 1

Reset to default
2
$\begingroup$

You can use any library you like, as long as it is has been tested for the specific algorithm. In other words, if $G^x$ is implemented in a specific library you must make sure that there are unit tests and if it is used in a verified algorithm.

There are some hints you can take from the library to see if it was programmed well:

  • the code should point to the implemented standard;
  • the code should use identifiers that can be mapped to the algorithms specified in the standard it implements.

There are some more general security requirements as well of course:

  • the code should keep to an apparent programming style;
  • the code should be accompanied with the test vectors;
  • the code should provide unit tests for (implementation specific) edge cases (maximum integer values etc.);
  • the code should provide unit tests for the complementary functions;
  • etc. etc.

As for the unit tests of the (complementary) functions: this is not often the case, I've seen horrible failures here, including those made by myself) but also e.g. the DH implementation of Bouncy Castle and the CCM code of SJCL. In some sense you could share heartbleed under this as well.

OK, so back to the question: it depends rather a lot about the size of $G$ to find out which $G^x$ is most efficient. The choice of library would probably depend on that. Runtimes may already include these kind of algorithms as well, but they may not always be the most efficient choice for certain parameters.

I'd recommend reference implementations if not for the fact that they are often horribly programmed. Mathematicians and cryptographers are just as likely to succeed in software development as anybody else. Quite often they do not keep to the requirements above, often for the sake of brevity.

Finally, you probably should chose a library that fits your programming environment of choice. The library should be quite extensive and the functions well defined; single purpose libraries should not be used unless they have been made for your specific problem domain.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.