Join Log in
Score:5
J. Doe avatar Crypto

Can a series of triangle reflections be used for cryptography?

at flag
J. Doe

(I guess no but why is this the case? Any way to make it possible?)

Out of a given equilateral triangle T1 (with his 3 vertices A,B,C lying in a finite Field $\mathbb F_N^D $) another equilateral triangle T2 can get constructed by mirroring one of the 3 vertices at the edge in between the two other vertices. This will be repeated multiple times.

Given just two random triangle T1 and T2 (and $\mathbb F_N^D $) can an adversary compute the shortest way from T1 to T2?
(Assuming there is a way and modulo $N$ and dimensions $D$ are choosen high enough that testing all triangle would take to long)
Or can he do it (much) faster than just applying it step by step?
(like for example at EC a generator $g$ don't need to be applied $m$ times if we want to compute $g^m$. I'm looking for a more-than-one-dimensional technique which can not be reduced to a single dimension problem and need to be computed step-by-step. The 'length' of the 'shortest way' would be the number of (triangle) computations needed)

To mirror point A at edge BC we are looking for a point $S$ and variable $r$ with $$S = B + r (C-B)$$ Let $v$ the direction of edge BC: $$v = \vec{v} = C-B$$

This $S$ would allows us to compute the direction from $A$ to $BC$ and with this compute the mirrored point $A_M$ $$A_M = A + 2(S-A)$$

To do this $S-A$ need to be orthogonal to $v$. So the scalar product need to be 0: $$(S-A)' v = 0$$ $$(B+rv-A)' v = 0$$ $$(B-A)' v = -rv'v$$ $$r = \frac{(B-A)'v}{-(v'v)}$$

(so same like as in euclidean space except for finite field $r$ need to computed with the inverse $(-(v'v))^{-1}$ over $N$)

Edit: fgrieu pointed out there is also a much easier way to compute the reflection of an equilateral triangle: $$A_M = A' = B+C-A$$ (edit end)

I did some tests for 2 dimensions and primes $N$.
The finite field $\mathbb F_N^2 $ can only produce a equilateral triangle if $N$ has a root for $3$.

A equilateral triangle with a given edge-length is able to produce $2 N^2$ other triangles (each has the same edge-length). Each edge length has two such sets. In total $2(N-1) (2N^2)$ which are disjoint with each other.

(I just computed the squared edge length in between two points like in euclidean space)

In euclidean space mirroring a triangle around point ($C$) would look like this:
Frist mirror $A$ at $CB$. Then mirror $B$ at $CA_M$ and so on. If it is a equilateral triangle it will match up again after doing this 6 times.

enter image description here

In a finite field $\mathbb F_{11}^2 $ it can look like this:
It also match up after doing this 6 times (around 1 point).
Doing it in just one direction it will match up after $2N$

enter image description here

Does a cryptography algorithm similar to this exist?
Why is this not secure? Or is it? Would more dimensions help?
Any ideas to make it more secure?

1447
0 + 0
fgrieu avatar
ng flag
fgrieu
If an equilateral triangle is one with equal distance between vertices, how do you define distance in a general finite field $\mathbb F_{p^k}$, or do you restrict to $\mathbb F_p$ with prime $p$? Also I don't get your algebra for the mirror $A'$ of point $A$ w.r.t. edge $BC$, including what $T$ is, and if/how the symmetric $A'$ of $A$ is _uniquely_ defined (I get that in the field $\mathbb R^d$, where $A'=B+C-A$ ). Also, it's hypothetical that the shortest path is a difficult problem; and having a hard problem is a necessary, not sufficient condition to build a cryptosystem.
1
Reply
J. Doe avatar
at flag
J. Doe
@fgrieu thanks for the hint. I did some update. I only used primes p for N. I changed the algebra to some alternative version with some more details. (T was just transpose of vector). A' should be uniquely defined with this. At least I thought so (will think again about it). I wasn't aware of $A' = B + C -A$. Can you give a example for $\mathbb{R^d}$ with $A'$ not uniquely defined?
0
Reply
fgrieu avatar
ng flag
fgrieu
In $\mathbb{R^d}$, the problem is reducible to the plane defined by $ABC$, thus reduces to $\mathbb{R^2}$ by a change of basis, and $A'$ is uniquely defined, and matches $A'=B+C-A$, or perhaps more rigorously $\vec{OA'}=\vec{OB}+\vec{OC}-\vec{OA}$. In ${\mathbb F_p}^d$, if we define $A'$ by that same equation, then $A'$ is also uniquely defined. I'm not sure about what your definition (especially the $T$ part) is when $d\ne2$.
2
Reply
J. Doe avatar
at flag
J. Doe
@fgrieu I changed the equation. There should be no $T$ anymore. I thought you mean there is some exception for $A' = B + C -A$ is not uniquely. If that's not the case I could change the equation to just that. Would be much easier. Also better connects with the answer from Fractalice.
1
Reply
Score:7
Fractalice avatar Crypto
in flag
Fractalice

From the second triangle, we can find an neighbouring triangle that has the same orientation as the first one (all the points will be shifted by the same vector). So we are interested in finding a path between one distinguished corner or the two triangles. It forms a two-dimensional lattice: e.g. $A_M$ can go to $A$ or to it's upper counterpart (on the continuation of $BC$). These two vectors form a basis. We can also include the third vector (going from $A_M$ down through two triangles): it is "redundant" but we need it since we want to find short coordinates, and these three vectors cover all 6 directions.

Now we just want to express the vector connecting the distinguished corner of the two triangles, in our (redundant) basis. This already should hint towards weakness of the problem, since we "just" need to find 3 numbers (coordinates in the basis), i.e., the order of steps does not matter.

This leads to CVP (close vector problem) instance, which can be solved by Babai's algorithm and LLL (you would have a few extra dimensions for coordinates and to add the modulus reduction into the lattice).

Going into higher dimensions might make LLL less effective. I don't know the details about that, but it seems that the basis we have is already reasonably good, so that LLL should find very good decompositions of paths.

0 + 0
J. Doe avatar
at flag
J. Doe
Oh dear how could I miss that, I also thought something like that ( shifted by same vector) and tested it with some example. It didn't work out at that point. I did the mistake to compare triangles after 3 reflections but to get the same shape only 2 reflections are needed. Thank you for pointing that out again. rip idea. I guess there also exists no similar but much more secure alternative.
2
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.