In this paper we propose a new method for public key encryption. The scheme's security is based on the well-known clique and learning parity with noise problems. The relevance of this approach is justi ed by its post-quantum nature: unlike RSA and other cryptosystems based on the hardness of factorization or discrete logarithm which could be broken by a suitable large quantum device, no known quantum attacks are known against our candidate system. We examine the time complexity of our scheme and compare it to RSA.
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 e cient 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. 1.1
In the remaining part of this section we brie y describe the hard problems used.
In Section 2 we describe prior work which led to the current state of the art and de ne a building block (encryption method) from an already existing public key encryption scheme, nally 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. 1.2
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 nd 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
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]. 1.3
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 nd 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 ght 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 rst one using the clique problem for constructing a scheme, see e.g. [Kuc91,JP00]. 1.4
In the following subsection we give some basic notations to avoid confusion with the most widely used notations in graph and probability theory.
[n] := f1; :::; ng
8n 2 N a is chosen randomly from A.
Un uniform distribution over binary vectors of length n.
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}os{Renyi random graphs).
G (u) set of the neighbors of node u in G. 2
In the rst 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). 2.1
The encryption method
M 2 F2m n sampled from D. 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 row of M .
Choose a random vector x Ber"m, let b = M x + e.
[m] with Pi2S Mi where Mi denotes the i-th
Un and a random noise vector e To encrypt 0, send the vector b.
To encrypt 1, send the vector b with its last bit ipped .
To decrypt y 2 f0; 1gn, output the Pi2s yi (mod 2). 2.2
Denote the sent message with M x + e + , where the is zero vector if the message 0, and 6664 0... 7757 if 1. 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
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}os{Renyi 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 nd that part. 3.1
The key generation parameters: n - graph size p - edge probability (determines the density of the graph) k - planted clique/independent set size padd - ratio that determines how to change the outer connection number to even (probability for adding) Denote the nodes of G graph with V and the edges with E.
Algorithm 1 The key generation 1. Choose a random G
G (n; p) graph. 2. Choose a random k sized subset from the nodes of the graph containing the last row. Denote it with S [n]. 3. Remove all edges between nodes contained in S: replace E by (En f(u; v) ju; v 2 Sg) (plant an independent set to the positions corresponding to S).
(a) with padd probability add (u; v) for v Sn G (u) to E, (b) else remove (u; v) for v G (u)jS from E.
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. 3.2
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 padd variable.
Theorem 2. The graph generated by our key generation algorithm has similar expected degree as G (n; p) if and only if padd = p 2 podd (n k) + Proof. The expected number of removed edges with planting the independent set: p k2 :
Denote with podd the probability that a node from V nS 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 nS) 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 Gn;p graph, we have to add as many edges as we removed (in expectation). This gives a formula for padd : padd = 2 podd (n k) +
We have a restriction for the parameters because clearly 0 padd 1 has to hold.
Theorem 3. For the parameters of a key generation the following has to hold: where podd is like above in Theorem 2. p + k
n Proof. Plug 0 padd
1 into the formula from Theorem 2. 0 p 2 podd (n k) + k) 1 ) (n k)
n k p podd which directly leads to the given bound. 4
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 rst 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 nally discuss some attacking algorithms. 4.1
In this subsection we discuss the hardness of nding an independent set S in a graph to which every node has an even number of connections. If one could nd such sets S e ciently, this would enable breaking the encryption scheme above.
De nition 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.
De nition 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: Let (V; E) := G V 0 = G f0; 1g E0 = f((u; 0) ; (v; 0)) j (u; v) 2 Eg [ f((u; 1) ; (v; 1)) j (u; v) 2 Eg [ f((u; 0) ; (v; 1)) j (u; v) 2 Eg G0 := (V 0; E0) k0 = 2k
If one had an e cient 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 = jGj. 2) Use the transformation in Theorem 7 to get G0.
3) Use the oracle on G0 which solves even neighbor independent set problem in polynomial time and gets solution S.
4) The original independent set position is fs0js0 s mod n; s 2 Sg 4.2
In the previous subsection we only argued that we cannot expect to be able to e ciently 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 nding cliques in graphs obtained as the public key of this scheme is at least as hard as nding 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 nd 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 modi ed version of the clique problem was investigated by Karp [Kar72], [Kar76]: Is there any polynomial time algorithm that nds 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 log1=p (n) 2 log1=p log1=p (n) + 2 log1=p 21 e + 1 in the Erd}os{Renyi 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 nk=4+o(1) times, we nd a 12 + " k sized clique also with high probability.
The original question hardened by Jerrum [Jer92]: Is there a polynomial time algorithm that nds a clique with k 1:01 log (n) in a random graph which contains a clique of size at least n0:49 ? In this paper they showed that some search techniques fail to e ciently nd a clique of size (1 + ") log (n) in a graph G n; 12 1 even if it is known to contain a clique of size n 2 .
The G (n; p) Erd}os-Renyi random graphs are well-studied (e.g. [Bol98,Wes01]) especially the uniform case G n; 12 . [AKS98] gave an algorithm which solves the planted clique problem in polynomial time with high probability for k > cn0: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. [Vas09] gave an algorithm with O nk= " log (n)k 1 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 nk=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 < < 21 . [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}os-Renyi graph (G n; 12 ) [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 6= N P . This question is still not answered.
We can nd a lot of algorithms solving the k-clique or maximal clique problems but still there are not any e cient 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; 21 distribution, and the interval considered hard for the clique size log (n) < k < pn. If we use this interval as a boundary for the key generation parameters, the attackers do not have any publicly known e cient 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}os{Renyi graphs. To compare the distribution of our key generation to the uniform G (n; p) we used the Wilcoxon rank-sum to measure the di erence 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, eld sieve , Clique/independent set: [Akk73,BK73,TIAS77,CN85,MU04,TTT06]) and the nal 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) p = 0:5 padd = 0:545
We proposed a public key encryption scheme whose security is based on the di culty 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 n22 , 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 < pn interval for secret sizes, because as we can see in previous sections, the hardness of nding 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. [Ajt96]
M. Ajtai. Generating hard instances of lattice problems, In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing 99{108, 1996. [Akk73] E. Akkoyunlu. The enumeration of maximal cliques of large graphs, In SIAM Journal on Computing 2(1):1{6, SIAM, 1973. [AKS98] N. Alon, M. Krivelevich, B. Sudakov. Finding a large hidden clique in a random graph, In Random
Structures and Algorithms 13(3-4):457{466, 1998.
C. Bron, J. Kerbosch. Algorithm 457: nding all cliques of an undirected graph, In Communications of the ACM 16(9):575{577, ACM, 1973.
B. Bollobas. Random graphs, Chapter in Modern Graph Theory 215{252, Springer, 1998. [BSK10] S. Balaji, V. Swaminathan, K. Kannan. A simple algorithm to optimize maximum independent set,
In Advanced Modeling and Optimization 12(1):107{118, 2010.
N. Chiba, T. Nishizeki. Arboricity and subgraph listing algorithms, In SIAM Journal on Computing 14(1):210{223, SIAM, 1985. [DGP14] Y. Dekel, O. Gurel-Gurevich, Y. Peres. Finding hidden cliques in linear time with high probability,
In Combinatorics, Probability and Computing 23(01):29{49,
Errors Problem., In IACR Cryptology ePrint Archive 2012:688, 2012.
U. Feige, D. Ron. Finding hidden cliques in linear time, In 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10) 189{204, 2010. [GLP12] T. Guneysu, V. Lyubashevsky, T. Poppelmann. Practical lattice-based cryptography: A signature scheme for embedded systems, In International Workshop on Cryptographic Hardware and Embedded Systems 530{547, 2012.
G. R. Grimmett, C. J. McDiarmid. On colouring random graphs, In Mathematical Proceedings of the Cambridge Philosophical Society 77(02):313{324, 1975.
L. K. Grover. A fast quantum mechanical algorithm for database search, In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing 212{219, 1996. [Jer92] [JP00] [Kar72] [Kar76] [Kuc91] [Mat72] [Mel13] [MU04] [NP85] [Pei14] [Reg09] [Reg10] [Rob01] [Ros10] [Ros14] [Sho94] [TIAS77] S. Tsukiyama, M. Ide, H. Ariyoshi, I. Shirakawa. A new algorithm for generating all the maximal independent sets, In SIAM Journal on Computing 6(3):505{517, SIAM, 1977. [TTT06] E. Tomita, A. Tanaka, H. Takahashi. The worst-case time complexity for generating all maximal cliques and computational experiments, In Theoretical Computer Science 363(1):28{42, Elsevier, 2006. [Wes01]