A Survey on Complexity Measures for Pseudo-Random Sequences
Round 1
Reviewer 1 Report
Comments and Suggestions for AuthorsThis paper discusses the complexity measures of FSR sequences.
The content of this paper is interesting and technically sound.
Author Response
Dear Reviewer,
Your positive comment on my efforts in the survey paper is highly appreciated.
For your information, according to the comments of the other reviewers, I have made slight adjustments (in blue) in several parts of the survey, corrected some typos and grammar errors, and revised the reference list for better presentation quality of the survey.
Best regards
Chunlei
Reviewer 2 Report
Comments and Suggestions for AuthorsThis is a unique survey of mathematical results on different complexity measures of random sequences, covering the application of linear, quadratic and maximum-order complexities and correlation measures concerning pseudorandom sequences to the study of randomness properties such as Lempel-Ziv complexity, expansion complexity, 2-adic complexity, and correlation measures. The topic of randomness has a broad scope the author based on his research perspective from sequence theory, he has tried to relate the concepts to explore the topic of complexity measures for randomness, which are central to Cryptography and theoretical computer science. This collection of results will be useful to researchers looking for new questions from the perspective of sequences theory.
The survey collects some important mathematical theorems from the theory of sequences, which are essential to understanding the issues concerning the study of randomness. There are interesting open problems for research. The narration is easy to read.
The references seem to be exhaustive. I have found the following paper having very early results on linear complexity properties of sequences: If it is relevant I request author to include it in the survey:
Analysis of the Berlekamp-Massey Linear Feedback Shift-Register Synthesis Algorithm
F. G. Gustavson
IBM Journal of Research and Development
Year: 1976 | Volume: 20, Issue: 3 | Journal Article | Publisher: IBM
Here are some of the minor English and other errors in the paper, that can be fixed after the revision.
1. The two conditions mentioned for the definition of random sequences line 16-20 are long and requires little rearrangement; has too many “if” clauses.
2. Expand the acronym LFSR at least when first used in the paper: line 49.
3. In Proposition 2: R_2(n) not defined.
4.In Theorem 1: line 155: Change “this implies” to “ This conditions implies” or “Consequently then we have”.
5. line 163: This condition should be ..
6. Proposition 3: the “discrete Fourier transform” not defined.
7. line after 196: This relation implies..
8. Proposition 5:Insert “,” after equation
9. Theorem 2: Increase the size of “Sigma” in the equations.
10. line 84: In the previous section…
11: Theorem 6: insert “,” at the end of the equation after line 407.
12. Section 6 title: Relation to “Relations”
13. Line 436: change “of all such sequences” to “ of sequences with max order complexity”.
14: Section 6.21. insert “,” before “where”
15. Section 5.3 line 462: “neither” to “either”?
16. Paragraph after Problem 1. The first sentence does not read propertly—The preceding discussion is more applicable for generic sequences.?
17. line 181: certain points?
Comments on the Quality of English Language
1, Line16: “condition” to “conditions”. (Plural)
2. line 366: “were” to “was”
3. 18, change “if” to “such that”.
4. Section 5.3 line 459: calculable -> computable?
5. Section 5.3 line 462: “neither” to “either”?
6. line 624: was ïƒ were
7. Line 459: This property reveals that certain terms..
Author Response
Dear Reviewer,
Thank you very much for your positive review of this survey paper and your detailed comments. I have carefully addressed all your comments in the revision. In addition, according to the comments of the other reviewers, I have made slight adjustments (in blue) to several parts of the survey, corrected grammar issues and typos, and revised the reference list in a consistent format. These revisions improved the presentation quality of the survey.
Below are my specific responses to your comments and suggestions.
*...If it is relevant I request author to include it in the survey:...
Response: Thanks for this valuable suggestion. In Lines 162-164, in addition to the paper you suggested, I added another significant paper about the Berlekamp-Massey algorithm;
1. The two conditions mentioned for the definition of random sequences line 16-20 are long and requires little rearrangement; has too many “if” clauses.
Response: Thanks for the suggestion. I rephrased the two conditions (Lines 47-52)
2. Expand the acronym LFSR at least when first used in the paper: line 49.
Response: Done as suggested
3. In Proposition 2: R_2(n) not defined.
Response: "R_2(n) denotes n modulo 2" was mentioned
4. In Theorem 1: line 155: Change “this implies” to “ This conditions implies” or “Consequently then we have”.
Response: Done as suggested
5. line 163: This condition should be ..
Response: Done as suggested
6. Proposition 3: the “discrete Fourier transform” not defined.
Response: I added the expression of DFT before Proposition 3
7. line after 196: This relation implies..
Response: Done as suggested
8. Proposition 5:Insert “,” after equation
Response: Done as suggested
9. Theorem 2: Increase the size of “Sigma” in the equations.
Response: Done as suggested
10. line 84: In the previous section…
Response: Done as suggested
11. Theorem 6: insert “,” at the end of the equation after line 407.
Response: Done as suggested
12. Section 6 title: Relation to “Relations”
Response: Done as suggested
13. Line 436: change “of all such sequences” to “ of sequences with max order complexity”.
Response: Done as suggested
14: Section 6.21. insert “,” before “where”
Response: Done as suggested
15. Section 5.3 line 462: “neither” to “either”?
Response: I rephrased the text here to improve readability
16. Paragraph after Problem 1. The first sentence does not read propertly—The preceding discussion is more applicable for generic sequences.?
Response: I rephrased this sentence.
17. line 181: certain points?
Response: I changed "certain point" to "a certain point" since the linear complexity profile of a periodic sequence s remains unchanged when at most two periods of terms in s are considered
All the grammar issues were fixed.
Reviewer 3 Report
Comments and Suggestions for AuthorsThis work presents a review of the main methods to measure the complexity of pseudo-random bitstreams over the years, in particular the ones generated by Feedback Shift Registers (FSRs).
The overall quality of the presentation is good since it is clear and the manuscript includes several mathematical definitions and equations that are informative and easy to understand, as well as the figures. The applied approach is technically sound and rigorous, including also a discussion of the main outcomes and the implications that the analyzed measures to evaluate the complexity of an FSR have, therefore the corresponding conclusions are convincing.
However, the manuscript seems to lack a practical perspective, oriented to link the theoretical and mathematical methods with the applications and the context of pseudo-random number generators (PRNGs), and that could highlight the contribution that this manuscript can give to the corresponding literature, in particular regarding the cryptographic application. This is because the most widely used techniques to implement PRNGs are the Deterministic Random Bit Generator (DRBG) methods standardized by NIST, while the author proposes the analysis and characterization of FSRs as a method to implement them. Also, FSRs are a valuable and significant method, but instead of directly starting with their analysis, it is recommended to first start with a discussion of the main methods used to implement PRNGs, including the mentioned DRBGs methods such as Elliptic Curve (EC)-based methods, Advanced Encryption Standard (AES)-based methods, and Secure Hash Algorithm (SHA)-based methods. Therefore, the main recommendation is to modify the organization of the first section (Section 1, Introduction) by first giving a presentation and discussion of the main methods used in cryptographic applications to implement PRNGs and focusing on FSRs by making a preliminary and overall comparison with the other methods (i.e. by highlighting the advantages of FSRs with respect to the other solutions), and introducing the concept of sequence s and the methods to measure its randomness. For this purpose, references to the other solutions should be included to support this preliminary analysis. Some references are given in the attached file.
In addition, some minor points, mainly related to typos, should be addressed to improve the readability of the manuscript. For more information, refer to the attached file.
Comments for author File: 
Comments.pdf
Author Response
Dear Reviewer,
Thank you for the positive review of my work in this survey. I highly appreciate your valuable suggestion about motivating the work in the introduction part, and the detailed reading and comments.
According to your suggestions and comments, I have made slight adjustments (in blue for your convenience) to several parts of the survey, corrected grammar issues and typos, and revised the reference list in a consistent format. I believe the presentation quality of the survey has been further improved in the revision. Below are my point-to-point responses to your suggestions.
"..... Therefore, the main recommendation is to modify the organization of the first section (Section 1, Introduction) by first giving a presentation and discussion of the main methods used in cryptographic applications to implement PRNGs and focusing on FSRs by making a preliminary and overall comparison with the other methods (i.e. by highlighting the advantages of FSRs with respect to the other solutions), and introducing the concept of sequence s and the methods to measure its randomness. For this purpose, references to the other solutions should be included to support this preliminary analysis. Some references are given in the attached file....."
Response: Thank you very much for this valuable suggestion. I have added a paragraph at the very beginning of the introduction, aiming to introduce some background of pseudo-random sequences in practical cryptographic applications, discuss the advantages of using FSR-based DRBG and motivated the importance of assessing the randomness of sequences in terms of complexity measure. As the construction of DRBGs and their security assessment are broad topics and beyond the scope of the survey, I gave a high-level description of this part and motivated the randomness evaluation in the end. I added several references in this part.
Minor Points
Thank you for the detailed comments in your attachment, I have revised all of them as you suggested.
Round 2
Reviewer 3 Report
Comments and Suggestions for AuthorsAll aspects highlighted in the previous round of review have been addressed, improving the quality of the manuscript and its already high content. In particular, the integration of some background information on pseudorandom sequences in practical cryptographic applications, discussing the advantages of FSR-based DRBGs, covered the weakest point of the manuscript.
