Geodesic
Group authentication scheme based~on~zero-knowledge~proof
Prikladnaâ diskretnaâ matematika, no. 1 (2021), pp. 68-84.

Voir la notice de l'article provenant de la source Math-Net.Ru

In this paper, we address the problem of mutual authentication in user groups in decentralized messaging systems without trusted third party. We propose a mutual authentication algorithm for groups using zero-knowledge proof. Using the algorithm, which is based on trust chains existing in decentralized network, users are able to authenticate each other without establishing a shared secret over side channel. The proposed algorithm is based on Democratic Group Signature protocol (DGS) and Communication-Computation Efficient Group Key algorithm for large and dynamic groups (CCEGK). We have performed security analysis of the proposed mutual authentication scheme against several attacks including Sybil attack and have made complexity estimation for the algorithm. The algorithm is implemented in an experimental P2P group messaging application, and using this implementation we estimate overhead of the authentication scheme and convergence time for several initial configurations of user groups and trust chains.
Keywords: authentication, zero-knowledge proof, decentralized communications. 
@article{PDM_2021_1_a3,
     author = {E. A. Shliakhtina and D. Yu. Gamayunov},
     title = {Group authentication scheme based~on~zero-knowledge~proof},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {68--84},
     publisher = {mathdoc},
     number = {1},
     year = {2021},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2021_1_a3/}
}
TY  - JOUR
AU  - E. A. Shliakhtina
AU  - D. Yu. Gamayunov
TI  - Group authentication scheme based~on~zero-knowledge~proof
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2021
SP  - 68
EP  - 84
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2021_1_a3/
LA  - ru
ID  - PDM_2021_1_a3
ER  - 
%0 Journal Article
%A E. A. Shliakhtina
%A D. Yu. Gamayunov
%T Group authentication scheme based~on~zero-knowledge~proof
%J Prikladnaâ diskretnaâ matematika
%D 2021
%P 68-84
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2021_1_a3/
%G ru
%F PDM_2021_1_a3
E. A. Shliakhtina; D. Yu. Gamayunov. Group authentication scheme based~on~zero-knowledge~proof. Prikladnaâ diskretnaâ matematika, no. 1 (2021), pp. 68-84. http://geodesic.mathdoc.fr/item/PDM_2021_1_a3/

[1] M. V. Korosteleva, D. Y. Gamayunov, “Protocol for secure group communications with deniability features”, Problemy Informatsionnoy Bezopasnosti. Komp'yuternyye Sistemy, 2014, no. 3, 74–79 (in Russian)

[2] I. Goldberg et al., “Multi-party off-the-record messaging”, Proc. 16th Conf. Computer Commun. Security, ACM, 2009, 358–368

[3] V. F. Sheidaev, D. Y. Gamayunov, “Deniable group communications in the presence of global unlimited advisory”, Prikladnaya Diskretnaya Matematika, 2018, no. 40, 72–86 (in Russian) | MR | Zbl

[4] Moscow State University Seclab mpOTR, https://bitbucket.org/Enr1g/p2p_mpotr.js

[5] K. K. Nguen, Zero-knowledge proof based authenticathion for group chat users, Graduation Project, MSU, M., 2018 (in Russian)

[6] F. Boudot, B. Schoenmakers, J. Traore, “A fair and efficient solution to the socialist millionaires' problem”, Discr. Appl. Math., 111:1 (2001), 23–36 | DOI | MR | Zbl

[7] M. Manulis, “Democratic group signatures: on an example of joint ventures”, Proc. 2006 ACM Symp. Inform. Comput. Commun. Security, 2006, 365

[8] Real-time communication for the web, https://webrtc.org/

[9] I. Stoica et al., “Chord: A scalable peer-to-peer lookup service for internet applications”, ACM SIGCOMM Comput. Commun. Rev., 31:4 (2001), 149–160 | DOI

[10] J. Alves-Foss, “An efficient secure authenticated group key exchange algorithm for large and dynamic groups”, Proc. 23rd National Inform. Systems Security Conf., 2000, 254–266

[11] Y. Kim, A. Perrig, G. Tsudik, “Communication-efficient group key agreement”, IFIP Intern. Inform. Security Conf., Springer, Boston, MA, 2001, 229–244

[12] Y. Kim, A. Perrig, G. Tsudik, “Group key agreement efficient in communication”, IEEE Trans. Computers, 53:7 (2004), 905–921 | DOI

[13] S. Zheng, D. Manz, J. Alves-Foss, “A communication-computation efficient group key algorithm for large and dynamic groups”, Computer Networks, 51:1 (2007), 69–93 | DOI | Zbl

[14] J. Camenisch, M. Stadler, “Efficient group signature schemes for large groups”, Ann. Intern. Cryptology Conf., Springer, Berlin–Heidelberg, 1997, 410–424 | Zbl

[15] A. Fiat, A. Shamir, “How to prove yourself: Practical solutions to identification and signature problems”, Conf. Theory Appl. Cryptogr. Techniques, Springer, Berlin–Heidelberg, 1986, 186–194 | MR

[16] D. Boneh, X. Boyen, H. Shacham, “Short group signatures”, Ann. Intern. Cryptology Conf., Springer, Berlin–Heidelberg, 2004, 41–55 | MR | Zbl

[17] Chain of groups method realisation for decentralized chat

[18] J. Leskovec, E. Horvitz, “Planetary-scale views on an instant-messaging network”, Proc. 17th Intern. Conf. World Wide Web, 2008, 915–924

[19] J. Ugander et al, The anatomy of the facebook social graph, 2011, arXiv: 1111.4503

[20] Three and a half degrees of separation – Facebook Research, , 2016 https://research.fb.com/blog/2016/02/three-and-a-half-degrees-of-separation/