As Berstein [Ber09] wrote: "Imagine that it's fifteen years from now and someone announces the successful construction of a large quantum computer. The New York Times runs a front-page article reporting that all of the public-key algorithms used to protect the Internet have been broken. Users panic."
In this apocalyptic "post-quantum" world, we suppose that we already have a big enough quantum machine, hence we can solve the factorization and the discrete logarithm problems in polynomial time. But what does it mean exactly to cryptography?
It is an accepted practice to use hard problems (that presumably cannot be solved in polynomial time) as assumptions and use them to postulate the hardness of a public key encryption scheme. The current widely used methods ("classic methods") like RSA, DSA or ECDSA are based on problems that can be solved by Shor's quantum algorithm [Sho94] in polynomial time (Shor's algorithm needs a bigger quantum machine than what we can build today).
What will we be able to do if that world comes? The classic schemes will be broken, but we can use other types of methods which remain secure against quantum machines. Several such schemes have been proposed but most such schemes are not considered efficient enough for practical purposes, so we have to give novel algorithms and/or optimize the existing ones to reach an acceptable scheme.
In this paper we follow this idea and approach for public key encryption to extend the possibilities for constructions. Our aim is to open a new way, but admittedly this method is still not efficient enough for real life internet usage.
We note that post-quantum cryptography is not to be confused with quantum cryptography. In post-quantum cryptography the schemes use only classic computers but are assumed to be secure against algorithms run on a quantum machine; whereas in quantum cryptography we use quantum techniques, i.e. physical quantum phenomena for encryption.
In our approach we combine a well-studied lattice problem with a problem from graph theory to obtain a new scheme.
In the remaining part of this section we briefly describe the hard problems used.
In Section 2 we describe prior work which led to the current state of the art and define a building block (encryption method) from an already existing public key encryption scheme, finally discuss the correctness and validity.
Section 3 gives the proposal of the new key generation method for the given encryption method and we discuss the security of the key.
Finally in Section 4 we discuss the key security of the new scheme.
A popular area in post-quantum cryptography is lattice-based cryptography, introduced by Ajtai in 1996 [Ajt96].
Here, lattices are used for building an encryption scheme. A widely studied lattice-based problem is the closest vector problem (CVP) where we have a vector (not necessary on the lattice) and a lattice, and we have to find the closest lattice point and determine that with the given basis. In small dimension it is an easy problem, but in higher dimensions it gets hard -NP-hardness results exist proving that random instances of the problem are basically as hard as the worst case instances. Outside theoretical computer science, the linear code decoding problem is closely related to the CVP, if the lattice is the codeword space and the given vector is the transmitted message with some noise. This problem is also considered hard.
A further closely related problem is the learning with errors (LWE) lattice problem introduced in [Reg09]. In the last few years it has been shown to have nice post-quantum cryptographic uses (summarized by Regev in 2010 [Reg10]) one of which is the following inversion problems which is hard under certain assumptions: Given M ∈ F m×n q and s ∈ F n q , a secret value, we have to determine s from M s + e where e is some small error.
Two of the most promising candidates today for post-quantum cryptography are lattice-based schemes: NTRU [HPS98] and Ring-LWE [LPR10,DXL12,GLP12,Pei14].
In the special case where q = 2 we use only binary values in LWE.
The learning parity with noise problem is a well-studied problem widely considered appropriate for constructing cryptography schemes. It has the big advantage that the calculation (M s + e) is a lot cheaper than the classic solutions, but inversion is hard. For some uses and more details, see [Mel13].
The clique problem is a basic problem from graph theory where given an input graph and an integer k, we have to decide whether the graph contains a complete subgraph (clique) of size k. A classical result is the following (we give quantitative formal hardness results later).
It is hard to find a clique (complete subgraph) of size k in a random graph.
The main advantage of using this problem is that it is an NP-complete problem, so if we can reduce breaking our encryption scheme to this hard problem, the attacker will also fight against the millennium problem "P versus NP".
In the post-quantum world there is a quantum algorithm that solves NP-complete problems: Grover's algorithm [Gro96]. This algorithm gives a reasonable speedup compared to known classical algorithms but still doesn't pose a threat to NP-hard problems in general.
The proposed encryption method is not the first one using the clique problem for constructing a scheme, see e.g. [Kuc91,JP00].
In the following subsection we give some basic notations to avoid confusion with the most widely used notations in graph and probability theory.
• U n uniform distribution over binary vectors of length n.
• Ber n ε distribution binary 0 − 1 vectors of length n where each entry is 1 independently with probability ε.
• G (n, p) distribution of n sized random graphs where every two nodes are adjacent with probability p (Erdős-Rényi random graphs).
• Π G (u) set of the neighbors of node u in G.
In the first section we could see the origin of our main problems, but now we describe the encryption algorithm (based on the LPN) which serves as the base of our scheme. The algorithm was introduced in [ABW10] and we can see it is a one-bit encryption method, but it can be easily extended to longer messages (make sure of the independent randomness of x and e).
The encryption method
Public key
The distribution D is over matrices, in which the last row is a linear combination of q − 1 other rows. (q must be small compared to m and n)
A q sized subset S ⊂ [m] with i∈S M i where M i denotes the i-th row of M .
Choose a random vector x ← U n and a random noise vector e ← Ber m ε , let b = M x + e.
• To encrypt 0, send the vector b.
• To encrypt 1, send the vector b with its last bit flipped .
To decrypt y ∈ {0, 1} n , output the i∈s y i (mod 2).
Denote the sent message with M x + e + σ, where the σ is zero vector if the message 0, and
Clearly the explained scheme is valid, because the M x product is linearly dependent on the position corresponding to S.
Error occurs in the decryption only with at most
probability by Lemma 5.3 from [ABW10].
Remark 1. We have to keep q small to achieve a good success ratio for transmission.
Theorem 7.3 from [ABW10] proves the existence of a semantically secure public key encryption scheme under some hardness assumptions using a distribution of d-sparse matrices that is computationally indistinguishable from the uniform distribution of d-sparse matrices.
3 Proposed public key encryption scheme
In this section we propose a public key encryption scheme using the encryption method from [ABW10] described in the preceding section. The scheme has a key generation algorithm based on the NP-complete clique problem.
Our approach uses Erdős-Rényi random graphs for creating a public key -private key pair. Our aim is to inject a small linearly dependent part into the adjacency matrix of the graph and make sure it is hard to find that part.
The key generation parameters:
• n -graph size 3. Remove all edges between nodes contained in S: replace E by (E\ {(u, v) |u, v ∈ S}) (plant an independent set to the positions corresponding to S).
Public key: G Private key: S Steps 1 to 3 create a graph with a planted independent set in the position denoted by S.
Step 4 adds and removes random edges to until we make sure that every node has an even number of connections to S. This latter property guarantees that this generation algorithm gives the (mod 2) linearly dependent part in the adjacency matrix that we need for the encryption scheme.
To achieve a graph that "looks" similar to an original G (n, p) instance, we make sure that the expected degree in the generated graph equals to the expected degree of a graph instance from G (n, p). To achieve this, we have to add similar number of random edges as we remove during the key generation. Using this observation we can give a formula for the p add variable.
Theorem 2. The graph generated by our key generation algorithm has similar expected degree as G (n, p) if and only if
where
Proof. The expected number of removed edges with planting the independent set: p k 2 .
Denote with p odd the probability that a node from V \S has an odd number of edges to the nodes corresponding in S:
In the key generation algorithm after the planting we check all of the nodes outside the clique (V \S) and calculate the parity. If the connection number to the S is odd, we have to add or remove one edge to make the connection number even, otherwise we do not do anything, hence the expected number of edges that are added is
To achieve a similar expected degree as a normal random G n,p graph, we have to add as many edges as we removed (in expectation). This gives a formula for p add :
We have a restriction for the parameters because clearly 0 ≤ p add ≤ 1 has to hold.
Theorem 3. For the parameters of a key generation the following has to hold:
where p odd is like above in Theorem 2.
Proof. Plug 0 ≤ p add ≤ 1 into the formula from Theorem 2.
which directly leads to the given bound.
In this section we discuss the hardness of computing the private key from public key without message sending.
In cryptography it is ordinary to prove the security with some deduction to a well-known problem, so first of all we deduct our key attacking problem to the well-known clique problem via Karp reductions. Next we focus on the distribution G (n, p), and finally discuss some attacking algorithms.
In this subsection we discuss the hardness of finding an independent set S in a graph to which every node has an even number of connections. If one could find such sets S efficiently, this would enable breaking the encryption scheme above.
Definition 4. The independent set problem consists of deciding the following property Input: graph G, positive integer k.
Property: G has k nodes which do not have edges between each other.
Lemma 5. The independent set problem is NP-complete.
Definition 6. Even neighbor independent set problem Input: graph G, positive integer k.
Property:
1) G has a set of k nodes (denoted by S) which don't have edges between them.
2) Each node outside S has an even number of neighbors from S.
Theorem 7. The even neighbor independent set problem is NP-hard.
Proof. Using Karp reduction to the independent set problem:
If one had an efficient algorithm for the search problem version of the even neighbor independent set problem, one could also solve the search problem version of the clique problem.
1) We have a k-sized independent set problem with G graph and k, n = |G|.
2) Use the transformation in Theorem 7 to get G .
3) Use the oracle on G which solves even neighbor independent set problem in polynomial time and gets solution S.
4) The original independent set position is {s |s ≡ s mod n, s ∈ S}
In the previous subsection we only argued that we cannot expect to be able to efficiently solve the even neighbor independent set problem in the worst-case. In order to formally prove the security of the proposed scheme, one would have to prove that finding cliques in graphs obtained as the public key of this scheme is at least as hard as finding cliques in general random graphs. We were not (yet) able to prove this, but below we give heuristic arguments about why this might be the case. The analysis below helps us find the optimal parameters for our encryption, therefore we discuss the potential attacking algorithms and related studies.
The simple brute force approach needs to check all the combinations of k nodes and check whether every node adjacent with each other. In worst case after we found an independent set we have to check the even connections from outside property.
The second intuitive approach is the greedy one, which has a lot of good improvement and all of them are based on the following two base steps:
1. Choose a random node.
2. Choose a new node which is adjacent with all of the nodes selected before.
We revise some relevant results from the literature on the clique problem.
• The following modified version of the clique problem was investigated by Karp [Kar72], [Kar76]: Is there any polynomial time algorithm that finds a k = (1 + ε) • lg (n) sized clique for any constant ε > 0?
• In [Mat72], it is proved that the expected size of the maximal clique is 2
1 2 e + 1 in the Erdős-Rényi model with parameter p. Many papers consider the p = 1/2 case and the approximation 2 • lg (n).
• In [GM75,Kar76], it is proved that in a uniformly generated graph, the greedy algorithm outputs a clique of size lg (n) with high probability. By running the greedy algorithm for n k/4+o(1) times, we find a 1 2 + ε k sized clique also with high probability.
• The original question hardened by Jerrum [Jer92]: Is there a polynomial time algorithm that finds a clique with k ≥ 1.01 • log (n) in a random graph which contains a clique of size at least n 0.49 ? In this paper they showed that some search techniques fail to efficiently find a clique of size (1 + ε)
• The G (n, p) Erdős-Rényi random graphs are well-studied (e.g. [Bol98,Wes01]) especially the uniform case G n, 1 2 .
• [AKS98] gave an algorithm which solves the planted clique problem in polynomial time with high probability for k > cn 0.5 cases which have some improvements [DGP14,FR10], but only the probability is improved, the lower bound not.
• In [NP85] the runtime is n (ω/3)k+o(1) , where n ω+o(1) is the runtime of the matrix multiplication. The lowest possible value (we have not reached that yet) of ω is 2, so if we have the theoretically best matrix multiplication algorithm, this algorithm gives a n (2/3)k+o(1) runtime. In practice this algorithm is inapplicable for our cases, because asymptotically fast matrix multiplication algorithms are not practical for the problem sizes we consider.
runtime and O (n ε ) space requirement.
• Several slight improvements appear in the following papers: [Rob01,BSK10,Ros14].
• Rossman [Ros14] analyzed Boolean circuits bounds for average case clique complexity and prooved that the boolean circuits of size O n k/4 and depth at most k −2 • log (n) /log (log (n)) cannot solve the k-clique problem with high probability on G (n, p).
Cryptosystems:
• Kucera [Kuc91] started to use the clique problem for cryptographic purposes in 1991, they used k = n κ clique size, where 0 < κ < 1 2 .
• [JP00] used the planted clique problem to construct an encryption scheme, but none of them proposed a public key encryption scheme. They proved it is hard to claim a planted clique from an uniform Erdős-Rényi graph (G n, 1 2 )
[Ros10] raised a question in 1.3: Is there an O n (1−δ)k/4 time algorithm which solves the k-clique problem with high probability on G (n, p)? If we have a negative answer for it, that would imply P = N P . This question is still not answered.
We can find a lot of algorithms solving the k-clique or maximal clique problems but still there are not any efficient algorithms even for Karp's question on a clique of size slightly above lg n.
Remark 8. The most frequently considered case is the uniform G n, 1 2 distribution, and the interval considered hard for the clique size log (n) < k < √ n. If we use this interval as a boundary for the key generation parameters, the attackers do not have any publicly known efficient algorithms.
We saw in the previous section that the hardness of the decryption strongly depends on the size of the independent set. It is clear, we have to use at least a log (n) sized independent set as a secret key, but that is an open question which upper bound would be better for us.
It was shown that the expected maximum clique size is k ≈ 2 • log (n), so in the remaining part of this paper we investigate only graphs with k = 1.95 • log (n) sized injected independent sets.
We could not formally prove that the distribution of graphs obtained as a public key of our scheme is computationally indistinguishable from the set of all Erdős-Rényi graphs. To compare the distribution of our key generation to the uniform G (n, p) we used the Wilcoxon rank-sum to measure the difference between the two distribution and it shown a really good p-value for the typical properties like diameter, degree, average maximum clique size etc.
As part of the research we implemented our cryptosystem in sage and compared to the classical RSA security level with some experimental tests. Our aim was to break the cryptosystems with a publicly available algorithm. We tried many implementations of the best algorithms against both of problems (RSA: Pollard Rho, Pollard p-1, field sieve , Clique/independent set: [Akk73,BK73,TIAS77,CN85,MU04,TTT06]) and the final choice against the RSA was the Pari/GP computer algebra system (It was faster than the publicly available sieve based on gmp in c++, polard, etc.), and the Tomita algorithm [TTT06] against our cryptosystem (which was also faster than the famous Bron-Kerbosch algorithm in our cases).
In our measurements we used the k = 1.95•log (n) clique size, because naturally the expected maximum clique size is 2 • log (n), so our graph will be more similar to the uniform distribution. Our experimental results show that we can use nearly similar n parameter (needed little bit bigger) as used for the RSA, so we can claim an acceptable encryption if we use the following parameter set.
n ≥ 1024 k = 1.95 • log (n) ≈ 14 p = 0.5 p add = 0.545
We proposed a public key encryption scheme whose security is based on the difficulty of the clique problem and we expect it to be secure against quantum algorithms as well. Yet there are several improvements to be made.
Currently, our key size is n 2 2 , and the encrypted size / message size ratio is n, so during further development we plan to improve the algorithm to get a better ratio, because now it equals to the graph size, which is a really huge overhead to the encrypted message. The big key size can be negligible in practice, because it has to be transfered only once and can be cached in middle points on the internet.
By research of Jerrum [Jer92] we will investigate the 2 • log (n) < k < √ n interval for secret sizes, because as we can see in previous sections, the hardness of finding an independent set exponentially grows together with the size of the independent set. We expect to supplement present work with additional formal proofs of security and perform more extensive experiments in the future.