Complexity calculation of coding and information security system based on threshold secret sharing scheme used for electronic voting

Introduction . One of the tasks arising in cryptography is to ensure the safe and honest conduct of e-voting. This procedure provides that voters submit their votes electronically - for example, through electronic terminals. A new algorithm for the distribution of threshold sensitive data for electronic voting is proposed. Materials and Methods . The results are obtained on the basis of the following methodology: finite field theory, theory of algorithms, projective geometry, and linear algebra. The developed cryptosystem is based on the application of geometric objects from projective geometry which makes it possible to use the apparatus of linear algebra to make effective decisions on cryptographic problems. To estimate the complexity of the described algorithms, classical results from the theory of algorithms are applied. Research Results . This paper describes the cryptographic algorithms of secret sharing and its subsequent restoration based on special structural properties of projective spaces over finite fields, and their link with Galois fields of the appropriate order. The component parts of these algorithms, specifically, the construction of injective mapping from a residue ring prime modulo into the projective space over finite field of specific dimension; the generation of secret shares and secret; the procedure of secret sharing and its restoration, are described in great detail. The algorithmic time complexity calculations of the formal algorithms are given. Discussion and Conclusions . The described scheme is useful for electronic voting and in other spheres where methods of threshold cryptography are applied.

криптография, электронное голосование, пороговая криптография, разделение секрета, криптосистема Эль-Гамаля, криптосистема с открытым ключом, криптографический секрет, криптографический алгоритм, информационная безопасность, криптографический ключ, cryptography, electronic voting, threshold cryptography, secret sharing, ElGamal encryption system, public-key cryptography, cryptographic secret, cryptographic algorithm, information security, cryptographic key

1. Arkhangelskaya, N.S., Mazurenko, A.V. Matematicheskaya model' elektronnogo golosovaniya na osnove metodov porogovoy kriptografii. [Mathematical model of electronic voting based on threshold cryptography methods.] Sistemnyy analiz, upravlenie i obrabotka informatsii: sb. tr. VI mezhdunar. seminara. [System analysis, control and information processing: Proc. VI Int. Workshop.] Rostov-on- Don, 2015, vol. 1, pp. 275–280. Available at: http://ntb.donstu.ru/content/2015421/ (accessed: 16.10.16) (in Russian).

2. ElGamal, T. A public-key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory, 1985, vol. 31, no. 4, pp. 469–472.

3. Alferov, A.P., et al. Osnovy kriptografii. [Cryptography fundamentals.] Moscow: Gelios-ARV, 2001, 480 p. (in Russian).

4. Barbulescu, R., et al. A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic. Advances in Cryptology — EUROCRYPT 2014: Annual International Conference on the Theory and Applications of

5. Cryptographic Techniques. 2014, vol. 8441, pp. 1–16.

6. Stallings, W. Computer security: principles and practice. Boston: Pearson, 2012, 182 p.

7. Ryabko, B.Y., Fionov, A.N. Kriptograficheskie metody zashchity informatsii. [Cryptographic methods of information security.] Moscow: Hot Line — Telecom, 2005, 229 p. (in Russian).

8. Joux, A., Odlyzko, A.-M., Pierrot, C. The past, evolving present and future of discrete logarithm. Open Problems in Mathematics and Computational Science. Cham: Springer, 2014, pp. 5–36.

9. Mogilevskaya, N.S., Kulbikayan, R.V., Zhuravlev, L.A. Porogovoe razdelenie faylov na osnove bitovykh masok: ideya i vozmozhnoe primenenie. [Threshold separation of files based on bit masks: idea and potential application.] Vestnik of DSTU, 2011, vol. 11, no. 10, pp. 1749–1755 (in Russian).

10. De Anindya, et al. Fast Integer Multiplication Using Modular Arithmetic. SIAM Journal on Computing, 2013, vol. 42, no. 2, pp. 685–699.

11. Schneier, B. Applied Cryptography: Protocols, Algorithms, and Source Code in C. 2nd ed. New York: John Wiley & Sons, 1995, 792 p.