Research into methods and algorithms for generating (pseudo) random sequences over an arbitrary alphabet
DOI:
https://doi.org/10.30837/rt.2024.1.216.01Keywords:
random sequences, sequence generation, arbitrary alphabet, generation methods, crypto providers, random number generatorsAbstract
Randomness is an integral component of most special software and hardware CIP tools. Work and development towards improving the process of randomness generation is actively underway and requires special attention.
This paper is devoted to the research into algorithms for generating (pseudo)random sequences over an arbitrary alphabet, estimating their complexity (time and capacity), as well as statistical characteristics. This study is important because modern post-quantum algorithms use such sequences to generate keys and random components of digital signatures and key encapsulation.
Obtained results can serve as a motivation for choosing an algorithm for generating sequences of an arbitrary alphabet for use in certain cryptographic transformations or algorithms.
References
FIPS.203. https://csrc.nist.gov/pubs/fips/203/ipd
FIPS.204. https://csrc.nist.gov/pubs/fips/204/ipd
ДСТУ 9212-2023. ДСТУ 9212:2023 Інформаційні технології. Криптографічний захист інформації. Алгоритм електронного підпису на модульних решітках
Олексійчук А.М., Курінний О.В. Методи криптоаналізу потокових шифрів : навч. вид. Київ : КПІ ім. Ігоря Сікорського, 2023. 172 с.
Blum M., Micali S. How to generate cryptographically strong sequences of pseudo-random bits // SIAM Journal of Computing. 1984. Vol. 13(4). P. 850–864.
Yao A.C. Theory and application of trapdoor functions // The 23-th. Annual Symposium on Foundations of Computer Science. IEEE, 1982. P. 80–91.
Katz J., Lindell Y. Introduction to modern cryptography. CRC Press, 2015. 598 p.
Lumbroso J. Optimal discrete uniform generation from coin flips, and application // arXiv.1304.1916v1 [cs.DS] 11 Apr 2013.
Кнут Д. Искусство программирования. Т. 2. Получисленные алгоритмы. 3-е изд. ; пер. с англ. Москва : Изд. дом “Вильямс”, 2000. 832 с.
Алексейчук А.Н. Неасимптотические нижние границы информационной сложности статистических атак на симметричные криптосистемы // Кибернетика и системный анализ. 2018. №. 1. С. 93–104.
Zvi Drezner,Ofir Turel & Dawit Zerom. A Modified Kolmogorov – Smirnov Test for Normality. 2010. URL: https://www.tandfonline.com/doi/citedby/10.1080/03610911003615816?scroll=top&needAccess=true (дата звернення: 12.03.2024).
William G. Cochran. The χ2 Test of Goodness of Fit. 1952. URL: https://www.jstor.org/stable/2236678 (дата звернення: 12.03.2024).
NIST Engineering Statistics Handbook. Kolmogorov – Smirnov Goodness-of-Fit Test. URL: https://www.itl.nist.gov/div898/handbook/eda/section3/eda35g.htm (дата звернення: 12.03.2024).
Taylor B. Arnold and John W. Emerson. Nonparametric Goodness-of-Fit Tests for Discrete Null Distributions. 2011. URL: http://www.stat.yale.edu/~jay/EmersonMaterials/DiscreteGOF.pdf (дата звернення: 12.03.2024).
R Development Page. Proposed Revision to stats::ks.test(). URL: https://r-forge.r-project.org/R/?group_id=802 (дата звернення: 12.03.2024).
Docs Tibco. Kolmogorov-Smirnov Tests. URL: https://docs.tibco.com/pub/enterprise-runtime-for-R/6.0.0/doc/html/Language_Reference/stats/ks.test.html (дата звернення: 12.03.2024).
Purrr: Functional Programming Tools. URL: https://uribo.github.io/rpkg_showcase/programming/purrr.html (дата звернення: 12.03.2024).
S. Massa. Lecture 13: Kolmogorov Smirnov Test & Power of Tests. Department of Statistics, University of Oxford. 2016. URL: https://www.ime.unicamp.br/~dias/Lecture%2013.pdf (дата звернення: 12.03.2024).
Kolmogorov-Smirnov Test Critical Values. URL: https://people.cs.pitt.edu/~lipschultz/cs1538/prob-table_KS.pdf (дата звернення: 12.03.2024).
NIST Engineering Statistics Handbook. Chi-Square Goodness-of-Fit Test. URL: https://www.itl.nist.gov/div898/handbook/eda/section3/eda35f.htm (дата звернення: 12.03.2024).
NIST Engineering Statistics Handbook. Critical Values of the Chi-Square Distribution. URL: https://www.itl.nist.gov/div898/handbook/eda/section3/eda3674.htm (дата звернення: 12.03.2024).
Soper D.S. Critical Chi-Square Value Calculator. 2024. URL: https://www.danielsoper.com/statcalc (дата звернення: 12.03.2024).
Jetbrains. PyCharm 2023.3.3. URL: https://www.jetbrains.com/pycharm/whatsnew/ (дата звернення: 12.03.2024).
Генератор рівномірно розподілених ймовірних чисел: пат. 33361 Україна : G06F7/58, 07C15/00. №99020855; заявл. 16.02.1999; опубл. 15.02.2001 Бюл. №1
Офіційний сайт КГВЧ Quantis RNG від швейцарської компанії ID Quantique (IDQ) [Електроний ре-сурс]. Режим доступу: https://www.idquantique.com/random-number-generation/overview/.
Downloads
Published
How to Cite
Issue
Section
License
Authors who publish with this journal agree to the following terms:
1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
