Score:0

Crypto

Are there crypt. methods $f,g,h$ which commute and finding $x$ for given $c=f^ig^jh^k(x)$ is harder than $O(i+j+k)$ but with only $<2^{256}$ values?

J. Doe

7/18/23, 8:57 PM

Are there any cryptographic methods $f,g,h$ which can be applied in any order to an input $x$ while still resulting in the same result $r$: $$f(g(h(x)))=h(g(f(x)))=ghf(x)=fhg(x)=hfg(x)=gfh(x) = r$$

Same for their inverse function: $$f^{-1}(g^{-1}(h^{-1}(r)))=h^{-1}(g^{-1}(f^{-1}(r)))=g^{-1}(h^{-1}(f^{-1}(r))) =...= x$$

If now $f,g,h,$ is applied $i,j,k$-times to an input $x$ finding/computing $x$ for given $c$ $$c=f^i(g^j(h^k(x)))$$ should be as hard as possible and with this taking more than $O(|i|+|j|+|k|)$ steps.
Furthermore the methods $f,g,h$ are format-preserving: $X \mapsto X$, so every output can serve as new input.
The number of different values $|X|$ should be as small as possible while still maintaining adequate security.
The max size should be: $$|X| < 2^{256}$$

Further nodes:
Computing $f,g,h$ and their inverses need to take a similar time for each input (independent of $i,j,k$).

Furthermore $f,g,h$ have to produce a cycle like $f(f(....f(x)...)) = x$ with size $F,G,H$ with $F\approx G \approx H \gg 1$

And random $x$ can be generated without the knowledge of secret parameter from $f,g,h$ (the adversary has access to the running code).

Target: Given two random $x_1,x_2$ with $x_2=f^ig^jh^k(x_1)$ computing/finding $i,j,k$ should be as hard as possible while the number of different $x$ should be as small as possible.
Not preferable but some combinations of $x_1,x_2$ may not have any $i,j,k$, methods $f,g,h: X_d \mapsto X_d$ with $d<\approx 10$

Target security $\approx 2^{100}$ steps (= number of computations of $f,g$ or $h$ (or equivalent)) needed.
With perfect $f,g,h$ (if they exist) it should only need $|X| \approx 2^{150}$ (e.g. intersection of line $f^l(x_1)$ with surface $g^mh^n(x_2)$)
(The adversary has no quantum computer)

Related question: If we ignore the max domain size $|X|<2^{256}$ the answer of my very similar question leads to a large $|X|$ to avoid factorization. I'm looking for a as small as possible $|X|$.

0 + 0

algorithm-design

kodlu

7/19/23, 1:24 AM

some brackets missing in the first set of compositions

J. Doe

7/19/23, 2:30 AM

@kodlu do you mean at 'ghf(x)'? I left them for better overview. If they commute with each other it should make no difference. Or?

Score:1

Crypto

poncho

7/18/23, 10:12 PM

Here is an idea that would appear to meet all of your stated requirements. Now, it doesn't meet other reasonable cryptographical requirements; however you never asked for them.

Here is the idea: we work in an appropriately sized Elliptic Curve group (say, P224) with group size $q$ (which is prime), and pick three generators $F, G, H$ (with unknown relationships; perhaps generated using a Hash2Curve method); and:

$$f(X) = F + X$$

$$g(X) = G + X$$

$$h(X) = H + X$$

These operations obviously commute, and we have $f^i(g^j(h^k(X))) = iF + jG + kH + X$.

Going through your requirements:

If now $f,g,h$, is applied $i,j,k$-times to an input $x$ finding/computing $x$ for given $c = f^i(g^j(h^k(x)))$ should be as hard as possible and with this taking more than $O(|i|+|j|+|k|)$ steps.

I assume that, in this requirement, the attacker doesn't know the values of $i, j, k$ (he does know the relative range). In that case, the best search I can find to verify a value $c$ takes $O( \sqrt{i \cdot j \cdot k } )$ time (assuming $i \cdot j \cdot k < q$, obviously); this is larger than $O(i + j + k)$. This search is done by taking the $0F, 1F, ..., iF$, $0G, 1G, ..., jG$, $0H, 1H, ..., kG$, dividing them into two lists where the sum of any three items in the three lists can be expressed as a sum of two if the items in the list, and then applying a 'big-step/little-step' style algorithm.

Furthermore the methods $f,g,h$ are format-preserving: $X \rightarrow X$, so every output can serve as new input.

As long as you're cool with $X$ being the set of elliptic curve points, we good here.

The max size should be: $|X|<2^{256}$

With P-224, this is true.

Computing $f,g,h$ and their inverses need to take a similar time for each input (independent of $i,j,k$).

We're good here

Furthermore $f,g,h$ have to produce a cycle like $f(f(....f(x)...))=x$ with size $F,G,H$ with $F \approx G \approx H \gg 1$

True; $f, g, h$ all have order $q$, which is much larger than 1

You can easily select ranges for $i, j, k$ so that the target security is met.

Now, the one thing that this idea does not provide is that, given $c, x$ with $c = f^i(g^j(h^k(x)))$, it is trivial to compute $c' = f^i(g^j(h^k(x')))$. However, you never asked that be hard...

0 + 0

dave_thompson_085

7/19/23, 1:23 AM

ITYM f,g,h commute not commit.

J. Doe

7/19/23, 1:45 AM

Ye, your are right thats not what I'm actually looking for but it's an answer to the written question and also already a possible backup plan If I dont find anything better. I've should had added the sequences $f,g,h$ are generating contain different values or they can generate more different values together than alone or product of their individual sequence size should be close to $|X|$. Or at least in best case they do so. Hard to include all without writing a roman nobody is reading. So thank you for answering again.

J. Doe

7/19/23, 1:46 AM

'As long as you're cool with $X$ being the set of elliptic curve points, we good here' -> I'm fine with everything which can be generated by random without the knowledge of secret parameter. Also fine if some member of $X$ can't be generated by random. ### 'Now, the one thing that this idea does not provide is that, given $c$,$x$ with[..] -> That's not a problem, $i,j,k$ will be different (almost) each time. $c$ and $x$ are picked by random and related $i,j,k$ should be unknown/hard to compute.

J. Doe

7/19/23, 1:51 AM

Could you give a short note why it is $O(\sqrt{i\cdot j \cdot k})$ please. I though it is $O(\sqrt{q})$ (and if we assume $q\equiv |X|$ and $f,g,h$ are *not* generating the same values (and can not be transferred to each other, so the best use case (as far as I know))) it would be $O(|X|^\frac{2}{3})$)

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Are there crypt. methods $f,g,h$ which commute and finding $x$ for given $c=f^ig^jh^k(x)$ is harder than $O(i+j+k)$ but with only $<2^{256}$ values?

TH: มีห้องใต้ดินหรือไม่วิธีการ $f,g,h$ ซึ่งการเดินทางและการค้นหา $x$ สำหรับ $c=f^ig^jh^k(x)$ นั้นยากกว่า $O(i+j+k)$ แต่มีเพียง $

RO: Există o criptă.metodele $f,g,h$ care fac naveta și găsirea de $x$ pentru $c=f^ig^jh^k(x)$ este mai dificilă decât $O(i+j+k)$ dar numai cu $

RU: Есть ли склеп.методы $f,g,h$, которые коммутируют, и найти $x$ для заданного $c=f^ig^jh^k(x)$ сложнее, чем $O(i+j+k)$, но только с $

VI: Có mật mã không.các phương pháp $f,g,h$ đi lại và tìm $x$ cho $c=f^ig^jh^k(x)$ khó hơn $O(i+j+k)$ nhưng chỉ với $

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.