Paper 2010/659

Practical Affiliation-Hiding Authentication from Improved Polynomial Interpolation

Mark Manulis and Bertram Poettering


Among the plethora of privacy-friendly authentication techniques, affiliation-hiding (AH) protocols are valuable for their ability to hide not only identities of communicating users behind their affiliations (memberships to groups), but also these affiliations from non-members. These qualities become increasingly important in our highly computerized user-centric information society, where privacy is an elusive good. Only little work on practical aspects of AH schemes, pursuing optimized implementations and deployment, has been done so far, and the main question a practitioner might ask --- whether affiliation-hiding schemes are truly practical today --- remained widely unanswered. Improving upon recent advances in the area of AH protocols, in particular on pioneering results in the multi-affiliation setting, we can give an affirmative answer to this question. To this end, we propose numerous algorithmic optimizations to a recent AH scheme leading to a remarkable performance gain. Our results are demonstrated not only at theoretical level, but we also offer implementations, performance measurements, and comparisons. At the same time, our improvements advance the area of efficient polynomial interpolation in finite fields, which is one of our building blocks.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. A preliminary version of this paper appears in ACM ASIACCS 2011.
affiliation-hiding authenticationprivacy-oriented cryptographyIHME
Contact author(s)
mark @ manulis eu
2010-12-31: received
Short URL
Creative Commons Attribution


      author = {Mark Manulis and Bertram Poettering},
      title = {Practical Affiliation-Hiding Authentication from Improved Polynomial Interpolation},
      howpublished = {Cryptology ePrint Archive, Paper 2010/659},
      year = {2010},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.