FARB: Fast Anonymous Reputation-Based Blacklisting without TTPs

ABSTRACT

Anonymous blacklisting schemes that do not rely on trusted third parties (TTPs) are desirable as they can block misbehaving users while protecting user privacy. Recent TTP-free schemes such as BLACR and PERM present reputation-based blacklisting, for which the service provider (SP) can assign positive or negative scores to anonymous sessions and block users whose reputations are not high enough. Though being the state of the art in anonymous blacklisting, these schemes are heavyweight and only able to support tens of authentications per minute in practical settings. We present FARB, the first reputation-based blacklisting scheme which has constant computational complexity both on the SP and user side. FARB thus supports a reputation list with billions of entries and is efficient enough for heavy-loaded SPs with thousands of authentications per minute. On the user side, FARB is fast enough even for mobile devices and supports flexible rate-limiting. We also present a novel fine-grained weighted extension which allows the SP to ramp up penalties for repeated misbehaviors according to the severity of the misbehaving user's past sessions.

References

1. M. H. Au and A. Kapadia. PERM: Practical reputation-based blacklisting without TTPs. In Proceedings of ACM CCS 2012, pages 929--940. ACM, 2012.
2. M. H. Au, A. Kapadia, and W. Susilo. BLACR: TTP-free blacklistable anonymous credentials with reputation. In Proceedings of NDSS 2012, San Diego, CA, USA,.
3. M. H. Au, W. Susilo, and Y. Mu. Constant-size dynamic k-TAA. In Security and Cryptography for Networks, pages 111--125. Springer, 2006.
4. D. Boneh, X. Boyen, and H. Shacham. Short group signatures. In CRYPTO 2004, pages 41--55. Springer, 2004.
5. E. Brickell and J. Li. Enhanced privacy ID: A direct anonymous attestation scheme with enhanced revocation capabilities. In Proceedings of WPES 2007, pages 21--30. ACM, 2007.
6. J. Camenisch, R. Chaabouni, et al. Efficient protocols for set membership and range proofs. In ASIACRYPT 2008, pages 234--252. Springer, 2008.
7. J. Camenisch, S. Hohenberger, M. Kohlweiss, A. Lysyanskaya, and M. Meyerovich. How to win the clonewars: efficient periodic n-times anonymous authentication. In Proceedings of ACM CCS 2006, pages 201--210. ACM, 2006.
8. J. Camenisch and A. Lysyanskaya. Signature schemes and anonymous credentials from bilinear maps. In CRYPTO'04, volume 3152 of LNCS, pages 56--72. Springer, 2004.
9. J. Camenisch and M. Stadler. Efficient group signature schemes for large groups. In CRYPTO'97, pages 410--424. Springer, 1997.
10. I. Damgard. On σ-protocols. Lecture notes for CPT, 2002.
11. R. Dingledine, N. Mathewson, and P. Syverson. Tor: The second-generation onion router. Technical report, DTIC Document, 2004.
12. R. Henry and I. Goldberg. Thinking inside the BLAC box: smarter protocols for faster anonymous blacklisting. In Proceedings of WPES 2013, pages 71--82. ACM, 2013.
13. R. Henry, K. Henry, and I. Goldberg. Making a Nymbler Nymble using VERBS. In Privacy Enhancing Technologies, pages 111--129. Springer, 2010.
14. R. Kohavi and R. Longbotham. Online experiments: Lessons learned. Computer, 40(9):103--105, 2007.
15. Z. Lin and N. Hopper. Jack: Scalable accumulator-based nymble system. In Proceedings of WPES 2010, pages 53--62. ACM, 2010.
16. P. Lofgren and N. Hopper. FAUST: efficient, TTP-free abuse prevention by anonymous whitelisting. In Proceedings of WPES 2011, pages 125--130. ACM, 2011.
17. T. P. Pedersen. Non-interactive and information-theoretic secure verifiable secret sharing. In CRYPTO'91, pages 129--140. Springer, 1992.
18. P. P. Tsang, M. H. Au, A. Kapadia, and S. W. Smith. PEREA: Towards practical TTP-free revocation in anonymous authentication. In Proceedings of ACM CCS 2008, pages 333--344. ACM, 2008.
19. P. P. Tsang, M. H. Au, A. Kapadia, and S. W. Smith. BLAC: Revoking repeatedly misbehaving anonymous users without relying on TTPs. ACM Transactions on Information and System Security (TISSEC), 13(4):39, 2010.
20. P. P. Tsang, A. Kapadia, C. Cornelius, and S. W. Smith. Nymble: Blocking misbehaving users in anonymizing networks. IEEE Transactions on Dependable and Secure Computing, 8(2):256--269, 2011.
21. K. Y. Yu, T. H. Yuen, S. S. Chow, S. M. Yiu, and L. C. Hui. PE(AR)2: Privacy-enhanced anonymous authentication with reputation and revocation. In Proceedings of ESORICS 2012, pages 679--696. Springer, 2012.

Index Terms

• Security and privacy

  • Cryptography

    • Public key (asymmetric) techniques

      • Public key encryption