The nonlinear complexity of binary sequences and its connections with Lempel-Ziv complexity is studied in this paper. A new recursive algorithm is presented, which produces the minimal nonlinear feedback shift register of a given binary sequence. Moreover, it is shown that the eigenvalue profile of a sequence uniquely determines its nonlinear complexity profile, thus establishing a connection between Lempel-Ziv complexity and nonlinear complexity. Furthermore, a lower bound for the Lempel-Ziv compression ratio of a given sequence is proved that depends on its nonlinear complexity.

Cryptography is traditionally considered as a main information security mechanism, providing several security services such as confidentiality, as well as data and entity authentication. This aspect is clearly relevant to the fundamental human right of privacy, in terms of securing data from eavesdropping and tampering, as well as from masquerading their origin. However, cryptography may also support several other (legal) requirements related to privacy. For example, in order to fulfil the data minimisation principle—i.e., to ensure that the personal data that are being processed are adequate and limited only to what is necessary in relation to the purposes for which they are processed—the use of advanced cryptographic techniques such as secure computations, zero-knowledge proofs or homomorphic encryption may be prerequisite. In practice though, it seems that the organisations performing personal data processing are not fully aware of such solutions, thus adopting techniques that pose risks for the rights of individuals. This paper aims to provide a generic overview of the possible cryptographic applications that suffice to address privacy challenges. In the process, we shall also state our view on the public “debate” on finding ways so as to allow law enforcement agencies to bypass the encryption of communication.

Aim: The imminent advent of large-scale quantum computers within the next years is expected to highly affect the security of several cryptosystems that are now considered secure; this mainly holds for classical, long-established, public key cryptographic algorithms such as RSA and elliptic curve cryptography. Apparently, any security protocol that relies on such ciphers, including the transport layer security (TLS) protocol which constitutes a somewhat de facto standard for the security on the web, will not be considered secure in the post-quantum era. To alleviate the security risks stemming from quantum computing, several proposals have been submitted to the relevant procedure initiated by NIST towards evaluating and standardizing one or more quantum-resistant public-key cryptographic algorithms. This paper focuses on embedding post-quantum secure cryptographic algorithms into the TLS protocol to analyze its performance. More precisely, the paper aims to analyze whether this transition to post-quantum secure algorithms will have a significant impact on the user experience due to the possible increase of client--server communication times. Methods: Having as the starting point several important works in the field, several experiments were carried out, using combinations of cloud and local virtual machines per case and considering all the post-quantum cryptographic algorithm finalists for key exchange from the third round of the ongoing NIST process, for various cryptographic as well as network parameters. Results: Our results exhibit that, for key exchange in TLS, the best performance among the post-quantum secure ciphers is achieved by the Saber and CRYSTAL-Kyber variants for all security levels, regardless of the underlying computing power. The performance is comparable to that of the corresponding one achieved by a classical elliptic curve algorithm for key exchange for both RTT and packet loss ratio — i.e., the network parameters seem to have the same effect on post-quantum secure algorithms as in the case of a conventional elliptic curve algorithm. However, the effect of the network parameters on the performance is more crucial than the effect of the underlying chosen ciphers. Conclusion: According to the experiments, we conclude that there exist very promising algorithms that could be utilized in TLS in the near future, which may behave even better than the conventional elliptic curve algorithms for key exchange. It should also be pointed out that NIST announced on 5 July 2022 (i.e., after the completion of our research experiments) that, for general encryption used when we access secure websites, the CRYSTALS-Kyber algorithm has been selected, having as one of its advantages the speed of operation. Hence, the results of our paper are fully in line with the progress of the NIST process. Taking into account that the NIST process is still ongoing (now in its fourth round) with the aim to select more algorithms, as well as that some algorithms may be standardized outside NIST, it becomes evident that our results provide very useful insights on performance aspects of the post-quantum secure algorithms.

The emergence of quantum computing presents a significant threat to classical cryptographic primitives, particularly those employed in securing internet communications via widely used protocols such as Transport Layer Security (TLS). As conventional key exchange mechanisms will become increasingly vulnerable in the post-quantum era, the integration of post-quantum cryptographic (PQC) algorithms into existing security protocols is of utmost importance. This study investigates the impact of incorporating PQC key encapsulation mechanisms—specifically, the recent standards CRYSTALS-Kyber and HQC, in conjunction with the candidate standard BIKE—into the TLS 1.3 handshake. A comprehensive experimental evaluation was conducted to measure handshake latency under emulated network conditions with varying packet loss probabilities. The findings offer useful insights into the performance trade-offs introduced by PQC integration and further highlight the necessity of a timely transition to post-quantum cryptographic standards.