Ok, here it is. I currently belive that this publishing makes the system un-patentable by anyone but me (and I can only patent it in the US, not in the EC). It is my intent that this algorithm be unfettered by copyright, liscence, trademark, patent, or any other icky intelectual property right. So let me state here that the algorith is in the public domain. I release all copyright to it. There, i hope that does it. But if I'm wrong, oh well. I don't think there is much economic worth in this scheme. But, I would be happy to be proven wrong! I expect that the odds that this system actually work are pretty long. But I've been over it too much, and can't see any holes, its time for others to poke at it. Besides, I like the tase of crow. j' This is an -*-outline-*- of my public key crypto system (setq outline-regexp "[!$=*]+") (setq paragraph-start "^[ ]+\\|^[!$=*]+") (setq paragraph-separate "^[ ]*$\\|^[!$=*]+") * Informal introduction ** Description of the system *** Key generation In total secrecy, Andy generates two graphs, one for encoding 1's and the other for encoding 0's. He then openly publishes these two graphs. *** Sending a bit In total secrecy, Beth selects one of the two graphs, and generates a new graph isomorphic to the selected graph based. Then Beth publicly sends the new graph to Andy. *** Recieving a bit To decrypt which bit Andy recieved, he must determin which graph Beth selected, and permuted. He must solve one case of the GI problem. To make this easy, he has hidden trapdoor indentifiers in the published graphs. Using my special JGI algorithm, and the trapdoor identifiers, Andy will be able to discover which bit Beth sent. *** The trapdoor information To make hiding a trapdoor identifier possible, Andy also publishes a labeling of the two graphs. For each node and each edge in the published graphs, Andy associates a labeling string. (He uses 2k-bit binary numbers as labels.) When he constructs the graphs, Andy insures that each one has a Hamiltonian Circuit. The trapdoor information is the labeling of the Hamiltonian Circuits of the two graphs. Naturally, each graph has a different Hamiltonian Circuit from the other, with a different labeling. ** Informal security argument For Eve to be able to determin the bit sent from Beth to Andy, she must be able to either solve instances of the Graph Isomorphism problem, or find the trapdoor identifier in the graph that Beth sends to Andy and also in the two published graphs. (I will ignore the posibility that Andy's and Beth's 'total secrecy' is penetrable by Eve. She might have psychic powers, or access to sophisticated spying technology. If this is the case, too bad for Andy and Beth.) *** The Graph Isomorphism problem Graph Isomorphism (GI) is a problem for which people believe there is no polynomial time solution. Although GI is belived to be easyer than problems known to be NP complete. So we belive that Eve has a fairly hard problem ahead of her, although the problem might not quite fit the usual definition of intractable. *** The Hameltonain Circuit problem Instead Eve could try to discover the trapdoor information. But since the Hamiltonian Circuit Decision problem is NP complete, and since NP complete problems are (belived) at least as hard as GI, it doesn't seem that there is much profit for Eve to try this aproach. * The formal version ** Key generation For a particular security parameter k, the published key consists of an ordered pair of graphs <G0, G1>. G0 is used for sending 0 bits, and G1 for sending 1 bits. Both G0 and G1 contain 2^4k nodes, and 2^4k*2^2k==2^6k edges. Each graph contains a Hameltonian Circuit. Each node, and each edge of each graph is labled with a member of {0,1}^k (the set of bit strings k bits long). Each node has exactly 2^2k outgoing edges (and 2^2k incomming?). To construct a graph, begin with a random set of labled nodes. Construct the Hameltonian Circuit by adding edges from vi to vj, each with a random label. Note (one of) the string(s) which is formed by appending the node and edge lables in order along the Hameltonian Circuit. This is the trapdoor information which makes the graph isomorphism problem easy. Next add edges to the graph until each node has exactly 2^2k outgoing edges, label each edge at random. (Here is where I should talk about how the GI problem is only rarely hard, and that the edges labeled at random garantees that we _sometimes_ land in the hard susbset of the GI problem. It would be nice to make a better construction which always landed in the hard subset of GI. But this is likely to be a hard research problem. Oh well.) ** Sending a bit Reciever sends two graphs as described above to the sender. The sender decides which bit to send -- 1 or 0. The sender then selects a permutation P of the nodes of the apropriate graph. The sender then sends the isomorphic graph defined by the permutation P to the reciever. The reciever uses my GI algorithm to determin which graph was sent. ** Recieving a bit The reciever runs the folowing algorithm twice in parallel, and the algorithm to finish first determins which graph was sent. The other algorithm is terminated (since its result is unnecesary.) *** Description of the algorithm The JGI algorithm takes as input a trapdoor string T of labels <tn1, te1, tn2, te2...> (tni, and tei are strings of binary digits), and a graph G=<V,E> of |V| nodes. It either halts and accepts the input, or halts and rejects the input. After initializing, the algorithm will halt in exactly V iterations of the main loop. **** Initialization For each node v in the graph, if the node's label matches the first label in the trapdoor, create a set sv containing v. Also create a pair pv of <v, sv>. Finally add the pair pv to the active set. Remove the first label from the trapdoor string. **** Main Loop While the trapdoor string T is not empty and the active set is not empty, do the Outer Loop. After performing the outer loop, make the next active set be the active set, and then remove the first two labels from the trapdoor string. ***** Outer Loop For each pair pi=<vi, svi> in the active set, do the Inner Loop. ****** Inner Loop For each edge e=<vj, vk> in E where vi==vj, if T's first label matches e's label, and if vk is not in svi, and if T's second label matches vk's label, then add the pair pi'=<vk, svi union {vk}> to the next active set. **** Final step If the trapdoor string is empty, halt and accept. If the active set is empty, and the trapdoor string is not, halt and reject. *** Proof of polynomial time and space behavior (This is a little weak, but I belive it can fly.) The main loop executes no more than |V| times since the trapdoor string contains exactly |V| node labels, and each iteration removes one of them. The important question is how many new pairs are added to the next active set, for each pair in the active set, by the outer and inner loops. For one of my graphs, the expected number is (less than) one. To see this note that the product of number of edge labels and the number of node labels equals the numbe of edges leaving a node. However, the test to see if the new vk is already a member of the old svi reduces this number. ** Proof of security The evesdropper must solve the GI problem for the subset of graphs constructed, or must discover the trapdoor information, and use my GI algorithm. To show how hard this is, I will show that GI of the subset of graphs generated is (polynomial time) GI complete, and I will show that discovering the trapdoor information is as hard as the Hameltonian circuit path discovery problem. *** The reduction to HP Now how am I going to do this? Ideas are solicited. *** The reduction to GI (All I actually present are the constructions for the reductions. I don't proove that isomorphism and (where apropriate) hameltonian posetion is retained. But I am convinced. Just tiered of typeing.) I will write GI for graph isomorphism, LGI for labeld graph isomorphism, HLGI to Hameltonian posesing labeled graph isomorphism, FAHLGI for fixed (at |V|^1/2) arity Hameltonian posesing labeled graph isomorphism. The subset of graphs that are generated in the key generation process are exactly those of the FAHLGI problem. (This is true by construction.) **** FAHLGI <= GI <= FAHLGI I will now prove that FAHLGI <= GI <= FAHLGI. I will prove this by the chain FAHLGI <= HLGI <= FAHLGI, HLGI <= LGI <= HLGI, LGI <= GI <= LGI. ***** FAHLGI <= HLGI <= FAHLGI ****** FAHLGI <= HLGI Obvious: Since FAHLGI is a subset of HLGI, a HLGI algorithm will work just fine when given graphs from the FAHLGI problem. ****** HLGI <= FAHLGI Replace each node with a clique of size |V|. Label the nodes in the clique as the original node, and the edges in the clique 00. For each ordered pair of nodes <v1,v2> in V^2, add an edge from one of the nodes in the clique for v1 to one of the nodes in the clique for v2. Label the new edge 11x if the there is an edge <v1,v2> in E and its label is x, label the new edge label 10x for some random x, if <v1,v2> is not in E. ***** HLGI <= LGI <= HLGI ****** HLGI <= LGI Obvious: Since HLGI is a subset of LGI, a LGI algorithm will work just fine when given graphs from the HLGI problem. ****** LGI <= HLGI For each v labeled x, construct v', v'' labeled 0x and 1x resp. For each v', and each v'', add the edges <v', v''> and <v'', v'> each labeled 0x for some random x. For each e= <v1, v2> in E labeled x add e'= <v1', v2'> labeled 1x. ***** LGI <= GI <= LGI ****** LGI <= GI For each node label add a new node, and an edge from the new node to each of the nodes so labeled. For each edge, add an intermediate node. For each label of the edges, construct a new node, and edges from it to the new edge nodes. ****** GI <= LGI Obvious construction: give each node and edge the label 0.