Cryptology ePrint Archive: Report 2010/659

Practical Affiliation-Hiding Authentication from Improved Polynomial Interpolation

Mark Manulis and Bertram Poettering

Abstract: 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.

Category / Keywords: cryptographic protocols / affiliation-hiding authentication, privacy-oriented cryptography, IHME

Publication Info: A preliminary version of this paper appears in ACM ASIACCS 2011.

Date: received 28 Dec 2010

Contact author: mark at manulis eu

Available formats: PDF | BibTeX Citation

Version: 20101231:142355 (All versions of this report)

Discussion forum: Show discussion | Start new discussion