AN AUTHENTICATION METHOD BASED ON A DIOPHANTINE MODEL OF THE COIN BAG PROBLEM

Krzysztof NIEMIEC


(Poland)
https://orcid.org/0009-0008-8101-2789

Grzegorz BOCEWICZ

grzegorz.bocewicz@tu.koszalin.pl
Koszalin Univeristy of Technology (Poland)
https://orcid.org/0000-0002-5181-2872

Abstract

 The article presents the so-called coin bag problem, which is modeled by linear Diophantine equations. The problem in question involves assessing the contents of a set of coins based on its weight. Since this type of problem is undecidable, a special variant of the problem was proposed for which effective problem-solving algorithms can be developed. In this paper, an original heuristic is presented (an algorithm based on problem decomposition) which allows to solve the coin bag problem in fewer steps compared to a brute force algorithm. The proposed approach was verified in a series of computational experiments. Additionally, an authentication scheme making use of the approach was proposed as an example of potential practical use.


Keywords:

Diophantine equations coin bag problem, decomposition algorithm, branch-and-bound method, authentication

Azrour, M., Mabrouki, J., Guezzaz, A., & Farhaoui, Y. (2021). New enhanced authentication protocol for Internet of Things. Big Data Mining and Analytics, 4(1), 1–9. https://doi.org/10.26599/BDMA.2020.9020010
DOI: https://doi.org/10.26599/BDMA.2020.9020010   Google Scholar

Barbeau, A. (2003). Pell’s equation. New York: Springer.
DOI: https://doi.org/10.1007/b97610   Google Scholar

Brody, J., & Verbin, E. (2010). The Coin Problem and Pseudorandomness for Branching Programs. 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, 30–39. https://doi.org/10.1109/FOCS.2010.10
DOI: https://doi.org/10.1109/FOCS.2010.10   Google Scholar

Clausen, M., & Fortenbacher, A. (1989). Efficient solution of linear diophantine equations. Journal of Symbolic Computation, 8(1–2), 201–216. https://doi.org/10.1016/S0747-7171(89)80025-2
DOI: https://doi.org/10.1016/S0747-7171(89)80025-2   Google Scholar

Darmon, H., Diamond, F., & Taylor, R. (1995). Fermat’s last theorem. Current developments in mathematics.
DOI: https://doi.org/10.4310/CDM.1995.v1995.n1.a1   Google Scholar

Gilbert, W. J., & Pathria, A. (1990). Linear Diophantine Equation. Manuscript.
  Google Scholar

Haakegaard, R., & Lang, J. (2015). The Elliptic Curve Diffie-Hellman (ECDH).
  Google Scholar

Jonsson, F., & Tornkvist, M. (2017). RSA authentication in Internet of Things: Technical limitations and industry expectations. Dissertation.
  Google Scholar

Kane, D. M. (2006). An elementary derivation of the asymptotics of partition functions. The Ramanujan Journal, 11(1), 49–66. https://doi.org/10.1007/s11139-006-5307-x
DOI: https://doi.org/10.1007/s11139-006-5307-x   Google Scholar

Karimi, E., Kazemi, F., Heidarzadeh, A., & Sprintson, A. (2018). A Simple and Efficient Strategy for the Coin Weighing Problem with a Spring Scale. 2018 IEEE International Symposium on Information Theory (ISIT), 1730–1734. https://doi.org/10.1109/ISIT.2018.8437774
DOI: https://doi.org/10.1109/ISIT.2018.8437774   Google Scholar

Matiyasevich, Y. (1993). Hilbert’s 10th Problem. MIT press.
  Google Scholar

Mordell, L. J. (1969). Diophantine Equations. Academic Press.
  Google Scholar

Mumtaz, M., Akram, J., & Ping, L. (2019). An RSA Based Authentication System for Smart IoT Environment. 2019 IEEE 21st International Conference on High Performance Computing and Communications; IEEE 17th International Conference on Smart City; IEEE 5th International Conference on Data Science and Systems (HPCC/SmartCity/DSS), 758–765. https://doi.org/10.1109/HPCC/SmartCity/DSS.2019.00112
DOI: https://doi.org/10.1109/HPCC/SmartCity/DSS.2019.00112   Google Scholar

Picciotto, H. (1987). Math McPuzzle. 85(52).
DOI: https://doi.org/10.1163/22116117-90001475   Google Scholar

Pólya, G. (1956). On Picture-Writing. The American Mathematical Monthly, 63(10), 689–697. https://doi.org/10.1080/00029890.1956.11988895
DOI: https://doi.org/10.1080/00029890.1956.11988895   Google Scholar

Schell, E. D. (1945). Weighed and found wanting. 52(42).
DOI: https://doi.org/10.2307/2304840   Google Scholar

Stark, H. (1973). Effective estimates of solutions of some diophantine equations. 24(3), 251–259.
DOI: https://doi.org/10.4064/aa-24-3-251-259   Google Scholar

Tripathi, A. (1978). On a linear Diophantine problem of Frobenius. Journal Für Die Reine Und Angewandte Mathematik (Crelles Journal), 1978(301), 171–178. https://doi.org/10.1515/crll.1978.301.171
DOI: https://doi.org/10.1515/crll.1978.301.171   Google Scholar

Wiles, A. (1995). Modular elliptic curves and Fermat’s last theorem. Annals of mathematics.
DOI: https://doi.org/10.1007/978-3-0348-9078-6_18   Google Scholar

Wright, J. W. (1975). The Change-Making Problem. Journal of the ACM, 22(1), 125–128. https://doi.org/10.1145/321864.321874
DOI: https://doi.org/10.1145/321864.321874   Google Scholar

Download


Published
2024-06-30

Cited by

NIEMIEC, K., & BOCEWICZ, G. (2024). AN AUTHENTICATION METHOD BASED ON A DIOPHANTINE MODEL OF THE COIN BAG PROBLEM. Applied Computer Science, 20(2), 157–174. https://doi.org/10.35784/acs-2024-22

Authors

Krzysztof NIEMIEC 

Poland
https://orcid.org/0009-0008-8101-2789

Authors

Grzegorz BOCEWICZ 
grzegorz.bocewicz@tu.koszalin.pl
Koszalin Univeristy of Technology Poland
https://orcid.org/0000-0002-5181-2872

Statistics

Abstract views: 146
PDF downloads: 56


License

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

All articles published in Applied Computer Science are open-access and distributed under the terms of the Creative Commons Attribution 4.0 International License.


Most read articles by the same author(s)

Similar Articles

1 2 3 4 5 6 7 8 9 10 > >> 

You may also start an advanced similarity search for this article.