Number-Theoretic Methods in Cryptology

We consider the problem of solving multivariate systems of Boolean polynomial equations: starting from a system of m polynomials of degree at most d in n variables, we want to find its solutions over \(\mathbb {F}_2\). Except for \(d=1\), the problem is known to be NP-hard, and its hardness has been used to create public cryptosystems; this motivates the search for faster algorithms to solve this problem. After reviewing the state of the art, we describe a new algorithm and show that it outperforms previously known methods in a wide range of relevant parameters. In particular, the first named author has been able to solve all the Fukuoka Type I MQ challenges, culminating with the resolution of a system of 148 quadratic equations in 74 variables in less than a day (and with a lot of luck).

Elliptic curves over finite fields are an essential part of public key cryptography. The security of cryptosystems with elliptic curves is based on the computational intractability of the Elliptic Curve Discrete Logarithm Problem (ECDLP). The paper presents requirements which cryptographically secure elliptic curves have to satisfy, together with their justification and some relevant examples of elliptic curves. We implemented modular arithmetic in a finite field, the operations on an elliptic curve and the basic cryptographic protocols.

In this article the attack on elliptic curve discrete logarithm problem (ECDLP) with partial information is considered. If unknown bits of discrete logarithm are continuous then 1-dimensional algorithms for ECDLP may be used. One of these algorithms is improved Gaudry-Schost using equivalence classes which requires \(O(1.47\sqrt{n}) \) operations. It will be showed that if unknown bits are not continuous and are given in \(c>1\) partitions and also two most significant bits are known, transformation of this partitions into one partition to use 1-dimensional algorithm without increasing size of the problem is impossible. It is also showed that in some situations it is better to “forget” some of known bits to transform the problem to 1-dimensional ECDLP.

We give explicit numerical estimates for the generalized Chebyshev functions. Explicit results of this kind are useful for estimating the computational complexity of algorithms which generate special primes. Such primes are needed to construct an elliptic curve over a prime field using the complex multiplication method.

This paper presents a new hard problem for use in cryptography, called Short Solutions to Nonlinear Equations (SSNE). This problem generalizes the Multivariate Quadratic (MQ) problem by requiring the solution be short; as well as the Short Integer Solutions (SIS) problem by requiring the underlying system of equations be nonlinear. The joint requirement causes common solving strategies such as lattice reduction or Gröbner basis algorithms to fail, and as a result SSNE admits shorter representations of equally hard problems. We show that SSNE can be used as the basis for a provably secure hash function. Despite failing to find public key cryptosystems relying on SSNE, we remain hopeful about that possibility.

In this paper we present a novel RSA-like cryptosystem. Specifically, we define a novel product that arises from a cubic field connected to the cubic Pell equation. We discuss some interesting properties and remarks about this product that can also be evaluated through a generalization of the Rédei rational functions. We then exploit these results to construct a novel RSA-like scheme that is more secure than RSA in broadcast applications. Moreover, our scheme is robust against the Wiener attack and against other kind of attacks that exploit the knowledge of a linear relation occurring between two plaintexts.

In this paper, we will study some possible generalizations of the famous Diffie-Hellman algorithm. As we will see, at the end, most of these generalizations will not be secure or will be equivalent to some classical schemes. However, these results are not always obvious and moreover our analysis will present some interesting connections between the concepts of commutativity, associativity, and public key cryptography.

In this work we investigate the problem of private statistical analysis of time-series data in the distributed and semi-honest setting. In particular, we study some properties of Private Stream Aggregation (PSA), first introduced by Shi et al. 2011. This is a computationally secure protocol for the collection and aggregation of data in a distributed network and has a very small communication cost. In the non-adaptive query model, a secure PSA scheme can be built upon any key-homomorphic weak pseudo-random function as shown by Valovich 2017, yielding security guarantees in the standard model which is in contrast to Shi et al. We show that every mechanism which preserves \((\epsilon ,\delta )\)-differential privacy in effect preserves computational \((\epsilon ,\delta )\)-differential privacy when it is executed through a secure PSA scheme. Furthermore, we introduce a novel perturbation mechanism based on the symmetric Skellam distribution that is suited for preserving differential privacy in the distributed setting, and find that its performances in terms of privacy and accuracy are comparable to those of previous solutions. On the other hand, we leverage its specific properties to construct a computationally efficient prospective post-quantum protocol for differentially private time-series data analysis in the distributed model. The security of this protocol is based on the hardness of a new variant of the Decisional Learning with Errors (DLWE) problem. In this variant the errors are taken from the symmetric Skellam distribution. We show that this new variant is hard based on the hardness of the standard Learning with Errors (LWE) problem where the errors are taken from the discrete Gaussian distribution. Thus, we provide a variant of the LWE problem that is hard based on conjecturally hard lattice problems and uses a discrete error distribution that is similar to the continuous Gaussian distribution in that it is closed under convolution. A consequent feature of the constructed prospective post-quantum protocol is the use of the same noise for security and for differential privacy.

Lattice basis reduction algorithms have been used as a strong tool for cryptanalysis. The most famous one is LLL, and its typical improvements are BKZ and LLL with deep insertions (DeepLLL). In LLL and DeepLLL, at every time to replace a lattice basis, we need to recompute the Gram-Schmidt orthogonalization (GSO) for the new basis. Compared with LLL, the form of the new GSO vectors is complicated in DeepLLL, and no formula has been known. In this paper, we give an explicit formula for GSO in DeepLLL, and also propose an efficient method to update GSO in DeepLLL. As another work, we embed DeepLLL into BKZ as a subroutine instead of LLL, which we call “DeepBKZ”, in order to find a more reduced basis. By using our DeepBKZ with blocksizes up to \(\beta = 50\), we have found a number of new solutions for the Darmstadt SVP challenge in dimensions from 102 to 123.

In this paper we describe the reduction of factorization of a square-free integer n to the problem of determining the number of points in \(\mathbb {Z}_n^{d+1}\) on twists of Kummer hypersurfaces \(y^k = f(x_1,\ldots , x_d)\,{\text {mod}}\,n\), where \(f(x_1,\ldots , x_d)\in \mathbb {Z}_n[x_1,\ldots , x_d]\) and \(k>1\). This reduction is expected to be polynomial time (in \({\text {log}}\,n\)) for small k and fixed number of prime divisors of n provided that some necessary for this reduction conditions are satisfied. This extends the known reduction of factorization to determining the number of points on elliptic curves \(y^2 = x^3 +ax +b\) over \(\mathbb {Z}_n\). In particular our reduction implies that factorization of n can be reduced to determining the number of points on quadrics in \(\mathbb {Z}_n^{d}\), \(d>1\), which extends the known reduction of factorization to determining the order of \(\mathbb {Z}_n^*\). We also describe the reduction of factorization to determine the number of points in \(\mathbb P^2(\mathbb {Z}_n)\) on superelliptic curves \(y^k = f(x_1)\,{\text {mod}}\,n\). To study the complexity of these reductions we introduce some notions and prove useful facts for a more precise analysis. In greater detail we consider the case of the reduction when \(n=pq\) is a product of two primes and \(k=2\).

We consider the following problem: given the set of residues modulo p of all divisors of some squarefree number n, can we find efficiently a small set of residues containing all residues coming from prime factors? We present an algorithm which solves this problem for p and n satisfying some natural conditions and show that there are plenty of such numbers. One interesting feature of the proof is that it relies on additive combinatorics. We also give some application of this result to algorithmic number theory.

A few years ago new quantitative measures of pseudorandomness of binary sequences have been introduced. Since that these measures have been studied in many papers and many constructions have been given along these lines. In this paper the connection between the new measures and the NIST tests is analyzed. It is shown that finite binary sequences possessing strong pseudorandom properties in terms of these new measures usually also pass or nearly pass most of the NIST tests.

The cross-combined measure (which is a natural extension of the cross-correlation measure) is introduced and important constructions of large families of binary lattices with optimal or nearly optimal cross-combined measures are presented. These results are also strongly related to the one-dimensional case: An easy method is shown obtaining strong constructions of families of binary sequences with nearly optimal cross-correlation measures based on the previous constructions of families of lattices. The important feature of this result is that so far there exists only one type of construction of very large families of binary sequences with small cross-correlation measure, and this only type of construction was based on one-variable irreducible polynomials. However there are relatively fast algorithms to construct one-variable irreducible polynomials, still in certain applications these algorithms are too complicated or are not fast enough, thus it became necessary to show other types of constructions where the generation of sequences is much faster. Using binary lattices based on two-variable irreducible polynomials this problem can be avoided. (Since, contrary to one-variable polynomials, using the Schöneman-Eisenstein criteria it is possible to generate two-variable irreducible polynomials over \(\mathbb F_p\) easily and very fast.)

The cube attack has been introduced by Dinur and Shamir [8] as a known plaintext attack on symmetric primitives. The attack has been applied to reduced variants of stream ciphers Trivium [3, 8] and Grain-128 [2], a reduced to three rounds variant of the block cipher Serpent [9] and a reduced version of the keyed hash function MD6 [3]. In another form the attack appeared in the Vielhaber ePrint articles [13, 14], where it was named AIDA (Algebraic Initial Value Differential Attack) and applied to reduced variants of Trivium. We applied the cube attack to the reduced variant of Courtois Toy Cipher (CTC) consisting of four rounds and 120-bit key. After that we extended the attack to five rounds of CTC by applying the 4 + 1 cryptanalytic principle. The article also presents experimental results of recovering the key.

A Hadamard matrix is a square matrix with entries \(\pm 1\) whose rows are orthogonal to each other. Hadamard matrices appear in various fields including cryptography, coding theory, combinatorics etc. This study takes an interest in \(\gamma \) near Butson-Hadamard matrix that is a generalization of Hadamard matrices for \(\gamma \in {\mathbb R}\cap {\mathbb Z}[\zeta _m] \). These matrices are examined in this study. In particular, the unsolvability of certain equations is studied in the case of cyclotomic number fields. Winterhof et al. considered the equations for \(\gamma \in {\mathbb Z}\), and by the authors for \(\gamma \in {\mathbb R}\cap {\mathbb Z}[\zeta _m]\). In this study, we obtain another method for checking the nonexistence cases of these equations, which uses the tool of norm from algebraic number theory. Then, the direct applications of these results to \(\gamma \) near Butson-Hadamard matrices are obtained. In the second part of this study, the connection between nonlinear Boolean cryptographic functions and \(\gamma \) near Butson-Hadamard matrices having small \(|\gamma |\) is established. In addition, a computer search is done for checking the cases which are excluded by our results and for obtaining new examples of existence parameters.

The secret sharing scheme by Dileep et al. [19] uses Level ordered access structure which is missing in the existing access structures. In their scheme, sequential reconstruction of the secret is achieved by adding a virtual player at all the levels except at the first level. In this paper, we propose a variation of sequential secret sharing scheme for level ordered access structure (LOAS) [19], where multisecrets are distributed to multilevels each corresponding to a level by using the concepts of quadratic residues and discrete logarithm problem. The method consists of sharing of m secrets in m levels, each corresponding to a level. The distribution of secrets is based on quadratic residues concept and that of the discrete logarithm problem. The reconstruction of secrets is such that players of different levels find their respective level secrets individually only after they get their immediate higher level permission. Verification phase is also added at all the levels which guarantees the correctness of the shares in the presence of any cheater. The comparison of the proposed secret sharing scheme with existing secret sharing schemes, time complexity of the scheme and security analysis of the scheme for passive adversary model are discussed.