I have been thinking recently about inherently sequential functions. In trying to wrap my head around them, I tried to come to the simplest possible function that looks inherently sequential to me. For didactical purposes, I'd like some feedback.

Consider two sequences of 64-bit integers: $a_1, \ldots, a_N$ and $b_1, \ldots, b_N$. Now, consider the sequence of 64-bit integers $x_0, \ldots, x_N$ defined by \begin{align} x_0 &= 0 \\ x_{n + 1} &= (x_n \oplus a_{n + 1}) + b_{n + 1} \end{align} where I use $\oplus$ to denote bitwise-XOR and $+$ to denote the sum modulo 64 bits. Intuitively, $x_N$ is obtained by a long sequence of alternating XORs and sums. I am wondering: is the computation of $x_N$ inherently sequential?

I cannot seem to easily see how one could achieve $x_N$ faster than just going through each operation. But, I realise that I might be missing something.

Here I am interested about both theory and practice: I'm curious to know if this function can be proved to be inherently sequential, but also if this function could be safely assumed to be inherently sequential, just like, e.g., cryptographic hash functions are safely assumed to approximate well a random oracle.

More specifically

I'll try to be more specific. What I am wondering is whether or not all bits in $x_N$ can be computed by a polynomially-sized boolean circuit whose critical depth is smaller than that of the trivial circuit, sequentially applying XORs and sums.

  • 3
    $\begingroup$ Do you have a precise definition of "inherently sequential"? At least, the low-order bit of the result is not inherently sequential (for whatever sound definition of that): it is the XOR of all the low-order bits, and that has depth $O(\log(n))$, not $O(n)$. It think some depth optimizations are possible for other bits too. $\endgroup$ – fgrieu Feb 8 at 12:22
  • $\begingroup$ That's a very good point :) I'll try to rephrase more precisely! $\endgroup$ – Matteo Monti Feb 8 at 13:19
  • $\begingroup$ for completeness, what is the depth of the trivial circuit? $\endgroup$ – kodlu Feb 9 at 4:53

This is actually touching to the notion of "rotational cryptanalysis", except you're missing the rotation part.

We usually use (modular) "Addition" or "Add" instead of "Sum", Add-Rotate-Xor are the core functions used by the so-called "ARX"-based algorithms which nowadays constitute an important part of the "fastest" stream ciphers (See Salsa/Chacha20, or the more controversial Speck, etc.) and hash functions (Blake, etc) out there.

The main idea behind ARX ciphers is that (modular) addition is not associative with the rotate, nor the XOR operation, and thus are difficult to simplify. (Exactly what you're interested in here.)

However skipping the rotation part as you did in a ARX design is an issue because it has been shown that systems made only of additions and XOR are broken since they can be reworked from rightmost to leftmost bit. To see the gory details I'll refer you to this Paul & Prenel paper that explain why this is broken: https://eprint.iacr.org/2004/294.pdf As you'll see in the linked paper, A(R)X construct are a pain to study because they do not have nice algebraic structure like AES, RSA or ECC, which sadly means that they are usually less anayzed. This is why some cryptographers believe it would be best to avoid ARX designs when designing new cipher and schemes, and we've seen cipher such as NORX or Gimli which are explicitly not-ARX designs.

Interestingly, using only Additions and Rotations, it is possible to emulate Xor, so the Xor can be removed in a "secure way" in ARX designs, unlike the rotation. (At the cost of a somewhat lower security bound though.)

  • $\begingroup$ This is really interesting! So, ARX functions are conjectured to be inherently sequential, and while their properties are more difficult to study formally, a great deal of real-world, fast functions leverage their sequentiality in their design. Did I understand correctly? :) $\endgroup$ – Matteo Monti Feb 8 at 20:16
  • $\begingroup$ I want to underline again that the only thing I care about is sequentiality: I don't care, for example, whether some of the values of $a$ or $b$ can be worked back from $x[n]$, or if an appropriate choice of $a$ and $b$ can affect the final value of $x[n]$. All I care is for $x[n]$ to be long to compute, even by a parallel adversary! $\endgroup$ – Matteo Monti Feb 8 at 20:19
  • $\begingroup$ Actually using ARX and a constant such as 1, you can build all functions that work on n-bit strings, which means you could also easily build non-sequential functions. I'm guessing you're more interested in your specific AX design, but since AX designs are broken, I'd expect it is possibly to simplify it. I'll try to add a section about it to my answer if I can find a solution. $\endgroup$ – Lery Feb 9 at 9:19
  • $\begingroup$ The overarching goal of my question is to learn how simple an inherently sequential function we can design! Now that you pointed me to ARX, I’m wondering what is the simplest ARX function that is (conjectured to be?) inherently sequential! $\endgroup$ – Matteo Monti Feb 9 at 9:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.