Transformation needed to fit three conditions

[nomadreid]

I am working in ℂ³ in this question. (If it will make it easier, we can work in a bounded subspace.)
Suppose you have, in each of the three complex planes whose Cartesian product make up the space in question, a set of points. (You do not have knowledge of generators of these sets, or whether such a generator exists, and you cannot assume connectedness in any of them.) I would like a relatively simple binary transformation, defined on any two sets of points, to combine them such that the method fulfills three conditions:
(1) it is associative (for example, the Cartesian product or the operation of rotating the planes to be all on one plane would fulfill this)
(2) it would be unique in the sense that if the sets A and B are combined to give C, then A cannot be combined with anything else to give C (For example, the Cartesian product would fulfill this condition, but the above rotation would not, since points could overlap)
(3) it is a trapdoor transformation: that is, if A and B are combined to give C, then given only C it is very hard to get A and B back. (For example, the Cartesian product would not fulfill this condition, but the rotation method would.)

Neither the Cartesian product nor the rotation method would fulfill all three conditions.

Can anyone imagine such a transformation?

 

[fresh_42]

Are you looking for an encryption scheme? And what is associativity good for?

 

[nomadreid]

Are you looking for an encryption scheme?

fresh_42, you have guessed correctly that the question has something to do with an encryption scheme. More precisely, a version of the Diffie-Hellman key exchange that does not depend on prime numbers; a sort of analogue Diffie-Hellman. Wikipedia does a cute version with mixing paints (although one could question the artist's colour sense); I wish to do one with sets of points. [Each sets of points could be any subset of the complex plane, even a fractal, or a subset which had no finite generator.] Because this is for educational purposes, I would like it to be relatively simple.

And what is associativity good for?

Letting # mean a binary transformation, so that the process is:
(0) Given: Alice set A, Bob set B, Common set C
(1) Alice forms C#A, sends it to Bob
(2) Bob forms C#B, sends it to Alice
(3) Alice forms A#(C#B)
(4) Bob forms B#(C#A)
So that Alice and Bob end up with the same key, one needs associativity and, come to think of it, also commutativity.

 

[chiro]

Hey nomadreid.

It sounds like you are combining a number of constraints here including:

- This being a group (closure, identity, inverse, associativity)
- The second condition would be violated if one had the identity element
- If you were to use a vector geometry analogue (like cross product) it wouldn't form a group since A x A = 0 and A x 0 = 0 as well
- The One-Way-Function constraints which are based on cryptography and specific kinds of groups in abstract algebra
- One is dealing with sets and not numeric quantities.

You mention you are working on C^3 but one thing that has to be mentioned is that dealing with information requires quantization.

What this means is that you are dealing with finite fields (integers) instead of uncountable fields (real, complex numbers).

If you are working with complex numbers you can't do the kinds of cryptography that you do with computers since computers require information to be quantized.

The thing that makes the one way function hard has to do with the operations (on a Turing machine with assumptions in computer science algorithms and computational complexity) that work on finite data. This is not the same as symbolic stuff on structures that can potentially in a number of bases have infinite information.

If there is no symbolic way of finding an inverse then to get the actual number you would be potentially doing an infinite number of computations to actually get the result.

You mention a binary transformation but your space involves syntheses of real numbers (with the complex number constraints added in).

If you could address these issues then I could give some more feedback.

 

[nomadreid]

Thanks, chiro. In the following, please do not equate expressions like "I do not see ..." with a negation. I am just saying that I do not understand (difference between provability and truth ), but would be glad to be corrected and enlightened. (Which is why I post.)

This being a group (closure, identity, inverse, associativity)

First, it is not immediately obvious to me why I would need an inverse or an identity.

If you are working with complex numbers you can't do the kinds of cryptography that you do with computers since computers require information to be quantized.

Fine. My mistake in mentioning Diffie-Hellman . I don't need the process to be practical on a computer. (Today's computer's; I am convinced that future computers will handle infinities that today's does not.) The only quantisation that is required is that one can distinguish one member of your truth-values lattice from another, but I see no reason that the sets themselves need be discrete.

You mention a binary transformation but your space involves syntheses of real numbers (with the complex number constraints added in).

I don't understand this. By a binary transformation I just mean that the transformation has two arguments; I see no reason why the two arguments cannot be real or complex. But I am probably reading it wrong. Could you elaborate?

The other points in your post arise from the necessity of finiteness which I have not yet seen the necessity for, given my original constraints. But if I am just overlooking some consequence of the constraints, I will try to deal with them in the next post.

 

[fresh_42]

Does it have to be the complex numbers? This kind of destroys possible polynomial solutions.

I haven't found an example yet, but I'm fishing in lattice theory (ordered sets). Its close relationship to Boolean algebras can perhaps be used to take the decision problem as trapdoor function.

 

[nomadreid]

Does it have to be the complex numbers?

No, I'm very flexible on that point.

 

[chiro]

The reason I mention a group is because you want to "undo" things (you use one way function and I assume you want to be able to "undo" it).

If you don't want to undo things then perhaps the group axioms are too restrictive - but I'm assuming with cryptography in mind that you want to be able to have some sort of 1-1 correspondence with un-encrypted and encrypted information which means that eventually the group axioms will have to hold (particularly inverse). You also mentioned associativity which lends itself to group axioms.

I think you may want to define the lattice because it's probably a lot simpler than I'm thinking it is.

If it is a binary transformation (i.e. takes two values and spits out another) then again the group is fine and well suited.

You could structure the process with a group and show a transformation exists to do what you need to do - but the moment you introduce the constraints for "hardness" regarding one-way functions (i.e. easy to do and hard to undo unless you have specific information required to undo it easily).

Any time you have to recover information with a decomposition you will need invertibility.

It's the idea that you pre-multiply or post-multiply something to "remove" that element by its inverse and if information is to be preserved (which I imagine it does) then inverses have to exist to enforce that.

If you don't have that property then information is lost and it doesn't matter whether you use dimension or entropy - you need invertability to retain the information in a system - otherwise it becomes a projection and you (potentially) lose information in one way or another.

 

[nomadreid]

chiro, sorry for the delay in the response. Various things going on (not just Brexit). Anyway, it appears that my original conditions, if I changed the trapdoor condition (3) from "very difficult to get A and B back" to "not necessarily possible to uniquely get A and B back", and disassociated the process from any mention of cryptography and keys, then strictly from a logical point of view, the conditions would not require invertibility. You are right, having a group structure would be convenient on one hand, but then the conditions could not be met without excluding the identity from the universal quantifiers in the conditions.
I think that clears up the issues that motivated me to post the problem. Thanks.