Question about public key cryptography with chemlambda

In this post Alice and Bob will communicate through #chemlambda computations.

Alice and Bob have each a mol file: Alice has A.mol and Bob has B.mol.

Step 1.  Alice partitions her file into A1.mol and A2.mol. She keeps A1.mol secret. The partition of the A.mol into two files creates some new free ports in A1.mol and A2.mol. Indeed, recall that free port variables are those which appear only once in the mol file. Thus every port variable which appears twice in A.mol, but only once in A1.mol and once in A2.mol, is not free in A.mol, but is free in both A1.mol and A2.mol. Every such variable corresponds to an edge which goes between a node from A1.mol and a node from A2.mol.

Let’s call these port variables “inner” port variables.



Alice renames all (or some of) the port variables from A2.mol and keeps the correspondence between the new names and the old names of the inner port variables.

Then she reduces only the A2.mol and she publishes it.


The published file, A2_red.mol is a mol file. Alice publishes also the partition of free port variables into inner and outer public free ports.

Important remark.  I see the reduction of the  A2.mol  to the reduced A2_red.mol as an encryption of A2mol. This is not a very accurate point of view, but the idea is that the reduction can be seen as a one way function which is easy to compute, but with an inverse which is hard to compute. More accurately,  chemlambda is universal, therefore the reduction of A2.mol may correspond to any computation. The file  i.e. A2_red.mol represents the result of the computation and A2.mol represents the program which has as result A2_red.mol.

Step 2. Bob takes the file A2_red.mol (which is public) and adds it to his own file B.mol. The file B.mol is secret. He connects the outer free ports of the file A2_red.mol to the free ports of the file B.mol, in a way which he keeps secret.


Then Bob reduces this mol file and obtains a file (A2_red-B)_red.mol. He sends this file to Alice.

Step 3. Alice uses her secret correspondence between public and private inner free ports variables to connect her A1.mol with the mol file received from Bob.

She reduces this file.



What happened?

Let’s look at the whole picture at once.


We have a mol file which is partitioned into three parts A1, A2 and B. Then it is reduced in the following way.

1. First the A1 and B parts of the file are frozen and only the A2 is reduced.

2. Then the wave of reductions spread and now only A1 is frozen and reductions are allowed everywhere else.

3. Finally A1 is unfrozen and the reductions continue in the whole file.

This is what Alice gets after the step 3.


Question: what can Alice learn about B.mol by looking at the result?


 UPDATE:   I started thinking about that since the summer 2014, when Louis Kauffman described a  Rope Ceremony in his visual style, using his characters Cookie and Parabel:


Trying to understand what’s going on, I made [my first] video. Here is it:



Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s