Otokar Grošek

PQC migration represents multiple challenges in education. We will need to educate our future cryptography researchers and engineers on new topics, introduce new challenges, and explain new cryptographic primitives. In the paper, we present our view on education challenges associated with the transition to post-quantum cryptography.

A prefix code minimal with respect to a bitstring x is a prefix code where x is a concatenation of its codewords and it is minimal with respect to this property. What is the maximum size M(n) among all minimal codes over all bitstrings of length n ? In this paper we determine the value of M(n) for all natural numbers n , discuss its computational complexity, relation to the Lambert function, provide tight upper bounds, and describe how the value of M(n) enables one to construct efficiently a Huffman code in the case of uniform probability distribution of the codewords.

In the presented paper, we investigate the problem of finding the maximum possible cardinality of a dictionary of a prefix code for a string of a given length. Namely, we present a sharp proof of the cardinality of such a dictionary using results from the number theory. What is more, the presented formula is for the general case of a string over any, not just binary, alphabet. Furthermore, we give conditions on the existence of the so-called canonical dictionary for such a string, where the codewords of the dictionary have at most two different lengths, differing by one. Our approach is based on reformulating the problem of finding the maximum possible cardinality of a dictionary for a string of a given length as the problem of finding the maximum possible number of summands in the Kraft-Szillard partition of the number representing the length of the string, by solving a Diophantine equation related to the canonical partition of the number. One of the areas of applications of presented results is the security-estimate of ciphers based on prefix codes.

In this paper, we investigate the maximum size of a minimal dictionary of a binary prefix-code string. We develop exact formulas for the maximum number of codewords of a minimal dictionary, which belongs to a binary string of some length. Further, we elaborate on the computational complexity of our approach and its relation to the Lambert function. We also present a way, how this information enables us to efficiently construct a Huffman code in the case of uniform probability distribution of codewords.The paper is of mathematical nature, i.e. all the methodology used in the paper is based on mathematical proofs.

A prefix code, a P-code, is a code where no codeword is a prefix of another codeword. In this paper, a symmetric cipher based on prefix codes is proposed. The simplicity of the design makes this cipher usable for Internet of Things applications. Our goal is to investigate the security of this cipher. A detailed analysis of the fundamental properties of P-codes shows that the keyspace of the cipher is too large to mount a brute-force attack. Specifically, in this regard we will find bounds on the number of minimal P-codes containing a binary word given in advance. Furthermore, the statistical attack is difficult to mount on such cryptosystem due to the attacker’s lack of information about the actual words used in the substitution mapping. The results of a statistical analysis of possible keys are also presented. It turns out that the distribution of the number of minimal P-codes over all binary words of a fixed length is Gaussian.

Here is information on how to publish, spread your research, and search for your publications. Most of LiU's research publications are directly imported into DiVA from the Web of Science. Before registering a publication, always check if the publication is already in DiVA!

It has been mentioned by Shannon that a Vigenère autokey ciphertext can be transformed into a Vigenère ciphertext, provided the length of the priming key is known. We revisit this transformation and argue that combining it with the Friedman test, in fact, allows revealing of the length of the priming key. Thus, Shannon’s transformation together with the Friedman test allow transforming a Vigenère autokey ciphertext into a Vigenère ciphertext without any prior information. This allows an adversary to solve a Vigenère autokey ciphertext as if it was a Vigenère ciphertext. In addition, we show that the same method can be used to solve a modification of the Vigenère autokey cipher used in the Russian Civil War in 1917–1922.

We study a method of computing multiplicative inverses in finite fields using long division. In the case of fields of a prime order p, we construct one fixed integer d(p) with the property that for any nonzero field element a, we can compute its inverse by dividing d(p) by a and by reducing the result modulo p. We show how to construct the smallest d(p) with this property. We demonstrate that a similar approach works in finite fields of a non-prime order, as well. However, we demonstrate that the studied method (in both cases) has worse asymptotic complexity than the extended Euclidean algorithm.

In the past when only “paper and pencil” ciphers were in use, a mnemonic Bellaso’s method was applied to obtain a permutation from a meaningful phrase. It turns out that even nowadays this method and its variations are employed and provide a simple but at the same time efficient tool for some ciphers. To the best of our knowledge the security of such ciphers has not been evaluated yet in all respects. Therefore, in this paper we initiate a study of their security with respect to the probability distribution of permutations obtained by Bellaso’s method.

In this paper we study equivalence classes of binary vectors with regards to their rotation by using an algebraic approach based on the theory of linear feedback shift registers. We state the necessary and sufficient condition for existence of an equivalence class with given cardinality and provide two formulas. The first represents the sharp distribution of cardinalities for given length and Hamming weight of binary vectors and the second enables us to determine the number of different classes with the same cardinality.