Scored Anonymous Credentials

Sherman S. M. Chow, Jack P. K. Ma & Tsz Hon Yuen

Abstract: Securely maintaining “credits” of users judging their behavior in past authenticated sessions is vital to encourage user participation, but doing it over anonymous credentials is non-trivial, especially when users would avoid claiming negative credit and escape from blocklisting. Prevalent designs impose an authentication cost linear in the blocklist size or a stringent requirement of sequential and timely judgment of each session without retrospective adjustment, as a single unjudged session curbs the authentication of all users. We propose scored anonymous credentials, a new design storing a number of active sessions with volatile scores downgradable before finalized. Sessions can be judged in any order and at varying times without affecting all users. Any backlog of unjudged sessions only affects the users behind them. We achieve efficiency and flexibility using verifiable shuffle, which is hardly used in existing anonymous blocklisting/reputation enforcement systems.

References

  1. Abe, M., Chow, S.S.M., Haralambiev, K., Ohkubo, M.: Double-trapdoor anonymous tags for traceable signatures. Int. J. Inf. Secur. 12(1), 19–31 (2013)
  2. Acar, T., Chow, S.S.M., Nguyen, L.: Accumulators and U-prove revocation. In: Sadeghi, A.-R. (ed.) FC 2013. LNCS, vol. 7859, pp. 189–196. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-39884-1_15
  3. Acar, T., Nguyen, L.: Revocation for delegatable anonymous credentials. In: Catalano, D., Fazio, N., Gennaro, R., Nicolosi, A. (eds.) PKC 2011. LNCS, vol. 6571, pp. 423–440. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-19379-8_26
  4. Au, M.H., Kapadia, A.: PERM: practical reputation-based blacklisting without TTPs. In: CCS, pp. 929–940 (2012)
  5. Au, M.H., Kapadia, A., Susilo, W.: BLACR: TTP-free blacklistable anonymous credentials with reputation. In: NDSS (2012)
  6. Au, M.H., Susilo, W., Mu, Y., Chow, S.S.M.: Constant-size dynamic k-times anonymous authentication. IEEE Syst. J. 7(2), 249–261 (2013)
  7. Backes, M., Hanzlik, L., Schneider-Bensch, J.: Membership privacy for fully dynamic group signatures. In: CCS, pp. 2181–2198 (2019)
  8. Barki, A., Brunet, S., Desmoulins, N., Traoré, J.: Improved algebraic MACs and practical keyed-verification anonymous credentials. In: Avanzi, R., Heys, H. (eds.) SAC 2016. LNCS, vol. 10532, pp. 360–380. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-69453-5_20
  9. Bayer, S., Groth, J.: Efficient zero-knowledge argument for correctness of a shuffle. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 263–280. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29011-4_17
  10. Bernstein, M.S., Monroy-Hernández, A., Harry, D., André, P., Panovich, K., Vargas, G.G.: 4chan and /b/: An analysis of anonymity and ephemerality in a large online community. In: AAAI Conference on Web and Social Media (ICWSM) (2011)
  11. Boneh, D., Boyen, X.: Short signatures without random oracles and the SDH assumption in bilinear groups. J. Cryptol. 21(2), 149–177 (2008)
  12. Boneh, D., Boyen, X., Shacham, H.: Short group signatures. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 41–55. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-28628-8_3
  13. Brickell, E., Li, J.: Enhanced Privacy ID: a direct anonymous attestation scheme with enhanced revocation capabilities. In: WPES, pp. 21–30 (2007)
  14. Bünz, B., Bootle, J., Boneh, D., Poelstra, A., Wuille, P., Maxwell, G.: Bulletproofs: short proofs for confidential transactions and more. In: S & P. pp. 315–334 (2018)
  15. Camenisch, J., Chaabouni, R., Shelat, A.: Efficient protocols for set membership and range proofs. In: Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol. 5350, pp. 234–252. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-89255-7_15
  16. Camenisch, J., Drijvers, M., Hajny, J.: Scalable revocation scheme for anonymous credentials based on n-times unlinkable proofs. In: WPES, pp. 123–133 (2016)
  17. Camenisch, J., Kohlweiss, M., Soriente, C.: Solving revocation with efficient update of anonymous credentials. In: Garay, J.A., De Prisco, R. (eds.) SCN 2010. LNCS, vol. 6280, pp. 454–471. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15317-4_28
  18. Camenisch, J., Lysyanskaya, A.: An efficient system for non-transferable anonymous credentials with optional anonymity revocation. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 93–118. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44987-6_7
  19. Camenisch, J., Lysyanskaya, A.: Dynamic accumulators and application to efficient revocation of anonymous credentials. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 61–76. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45708-9_5
  20. Camenisch, J., Stadler, M.: Efficient group signature schemes for large groups (extended abstract). In: Kaliski, B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 410–424. Springer, Heidelberg (1997). https://doi.org/10.1007/BFb0052252
  21. Chase, M., Meiklejohn, S., Zaverucha, G.: Algebraic MACs and keyed-verification anonymous credentials. In: CCS, pp. 1205–1216 (2014)
  22. Chow, S.S.M.: Real traceable signatures. In: Jacobson, M.J., Rijmen, V., Safavi-Naini, R. (eds.) SAC 2009. LNCS, vol. 5867, pp. 92–107. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-05445-7_6
  23. Chow, S.S.M., Egger, C., Lai, R.W.F., Ronge, V., Woo, I.K.Y.: On sustainable ring-based anonymous systems. In: IEEE Computer Security Foundations (CSF) Symposium (2023)
  24. Chow, S.S.M., Liu, J.K., Wong, D.S.: Robust receipt-free election system with ballot secrecy and verifiability. In: NDSS (2008)
  25. Chow, S.S.M., Susilo, W., Yuen, T.H.: Escrowed linkability of ring signatures and its applications. In: Nguyen, P.Q. (ed.) VIETCRYPT 2006. LNCS, vol. 4341, pp. 175–192. Springer, Heidelberg (2006). https://doi.org/10.1007/11958239_12
  26. Chow, S.S.M., Zhang, H., Zhang, T.: Real hidden identity-based signatures. In: Kiayias, A. (ed.) FC 2017. LNCS, vol. 10322, pp. 21–38. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70972-7_2
  27. Couteau, G., Reichle, M.: Non-interactive keyed-verification anonymous credentials. In: Lin, D., Sako, K. (eds.) PKC 2019. LNCS, vol. 11442, pp. 66–96. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17253-4_3
  28. Derler, D., Hanser, C., Slamanig, D.: A new approach to efficient revocable attribute-based anonymous credentials. In: Groth, J. (ed.) IMACC 2015. LNCS, vol. 9496, pp. 57–74. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-27239-9_4
  29. Dingledine, R., Mathewson, N., Syverson, P.F.: Tor: the second-generation onion router. In: USENIX Security Symposium, pp. 303–320 (2004)
  30. Doerner, J., Kondi, Y., Lee, E., abhi shelat, Tyner, L.: Threshold BBS+ signatures for distributed anonymous credential issuance. In: S & P. pp. 2095–2111 (2023)
  31. Ferrara, A.L., Green, M., Hohenberger, S., Pedersen, M.Ø.: Practical short signature batch verification. In: Fischlin, M. (ed.) CT-RSA 2009. LNCS, vol. 5473, pp. 309–324. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-00862-7_21
  32. Fiore, D., Garms, L., Kolonelos, D., Soriente, C., Tucker, I.: Ring signatures with user-controlled linkability. In: Atluri, V., Di Pietro, R., Jensen, C.D., Meng, W. (eds.) ESORICS Part II. LNCS, vol. 13555, pp. 405–426. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-17146-8_20
  33. Gurtler, S., Goldberg, I.: SoK: privacy-preserving reputation systems. Proc. Priv. Enhancing Technol. 2021(1), 107–127 (2021)
  34. Hajny, J., Dzurenda, P., Marques, R.C., Malina, L.: Privacy ABCs: now ready for your wallets! In: PerCom Workshops, pp. 686–691 (2021)
  35. Jøsang, A., Ismail, R., Boyd, C.: A survey of trust and reputation systems for online service provision. Decis. Support Syst. 43(2), 618–644 (2007)
  36. Lai, R.W.F., Cheung, K., Chow, S.S.M., So, A.M.: Another look at anonymous communication. IEEE Trans. Depend. Secur. Comput. 16(5), 731–742 (2019)
  37. Lai, R.W.F., Ronge, V., Ruffing, T., Schröder, D., Thyagarajan, S.A.K., Wang, J.: Omniring: scaling private payments without trusted setup. In: CCS, pp. 31–48 (2019)
  38. Lofgren, P., Hopper, N.: FAUST: efficient, TTP-free abuse prevention by anonymous whitelisting. In: WPES, pp. 125–130 (2011)
  39. Ma, J.P.K., Chow, S.S.M.: SMART credentials in the multi-queue of slackness (or Secure management of anonymous reputation traits without global halting). In: IEEE European Symposium on Security and Privacy (EuroS&P), pp. 896-912 (2023)
  40. Mittal, P., Olumofin, F.G., Troncoso, C., Borisov, N., Goldberg, I.: PIR-Tor: scalable anonymous communication using private information retrieval. In: USENIX Security Symposium (2011)
  41. Narayanan, A., Shmatikov, V.: De-anonymizing social networks. In: IEEE Symposium on Security and Privacy, pp. 173–187 (2009)
  42. Papamanthou, C., Tamassia, R., Triandopoulos, N.: Optimal verification of operations on dynamic sets. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 91–110. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22792-9_6
  43. Rosenberg, M., Maller, M., Miers, I.: SNARKBlock: federated anonymous blocklisting from hidden common input aggregate proofs. In: IEEE Symposium on Security and Privacy (S&P), pp. 1290–1307 (2022)
  44. Tsang, P.P., Au, M.H., Kapadia, A., Smith, S.W.: Blacklistable anonymous credentials: Blocking misbehaving users without TTPs. In: CCS, pp. 72–81 (2007)
  45. Tsang, P.P., Au, M.H., Kapadia, A., Smith, S.W.: PEREA: towards practical TTP-free revocation in anonymous authentication. In: CCS, pp. 333–344 (2008)
  46. Xi, L., Feng, D.: FARB: fast anonymous reputation-based blacklisting without TTPs. In: WPES, pp. 139–148 (2014)
  47. Yu, K.Y., Yuen, T.H., Chow, S.S.M., Yiu, S.M., Hui, L.C.K.: PE(AR)2: privacy-enhanced anonymous authentication with reputation and revocation. In: Foresti, S., Yung, M., Martinelli, F. (eds.) ESORICS 2012. LNCS, vol. 7459, pp. 679–696. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-33167-1_39
  48. Zhang, T., Wu, H., Chow, S.S.M.: Structure-preserving certificateless encryption and its application. In: Matsui, M. (ed.) CT-RSA 2019. LNCS, vol. 11405, pp. 1–22. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-12612-4_1