Score:3

Fastest order-sensitive operations

in flag

For any $v$ many $b$-bits vectors $(\mathbf{x}_0, \mathbf{x}_1, \ldots, \mathbf{x}_{v-1}) \in \{\{0, 1\}^b\}^v$, what's the fastest way to combine $\mathbf{x}_0, \mathbf{x}_1, \ldots, \mathbf{x}_{v-1}$ into a single number, such that the operation is order-sensitive?

E.g. say that $\hat+$ is some method of combining numbers (not necessarily addition, but we can define it however we want). The goal is to have $\mathbf{x}_0 \hat+ \mathbf{x}_1 \hat+ \ldots \hat+ \mathbf{x}_{v-1}$ result in a unique number different than any other order, such as, $\mathbf{x}_{v-1} \hat+ \mathbf{x}_{v-2} \hat+ \ldots \hat+ \mathbf{x}_0$.

As for fastest, speed is measured on general purpose CPUs. E.g. x86-64.


My thought so far is:

b_bits_variable xor = 0;
for (i = 0; i < v; i++) {
  xor = xor ^ (xor + x_i);
}

where:

  • b_bits_variable is a variable that has exactly $b$ many bits. E.g. if $b=16$, then we may use uint16_t in the C programming language.
  • v is $v$ (quantity of vectors as in question above).
  • x_i is $\mathbf{x}_i$ (a vector among the $v$ many ones as in question above).
  • i++ $= i+1$.
  • ^ is bit-wise XOR.
  • + is addition as commonly used in programming languages, which overflows if number is larger than $2^b - 1$. I think such overflow is basically modulo $2^b$ addition. I.e. xor + x_i $=\text{xor} + \mathbf{x}_i \mod 2^b$.
kodlu avatar
sa flag
please use mathematical notation. what is uint_8t?
caveman avatar
in flag
Unsigned integer with 8 bits. `uint8_t` is used in C. I thought it's common among cryptography community to speak in C since most implementations eventually boil down to optimisations in them? Maybe I'm wrong. Got a better way to write this?
kodlu avatar
sa flag
writing the problem mathematically will make it clearer to those who do not code. What set do your variables lie in? what are the operations defined on them? rand_pick_pool means what?
kodlu avatar
sa flag
Let us say I have $X_1,\ldots,X_N \in \{0,1\}^m$ so these are $m-$bit vectors. You can also think of them as integers in $\{0,1,..,2^m-1\}$ with modulo $2^m-1$ addition. Using this, re express your question.
caveman avatar
in flag
@kodlu - IMO that's too much, because this question is about fast implementations. IMO a subset of cryptography is closely related to implementations when it comes to performance, and my question is one. I think too much mathematical abstraction will take us away from the goal of the question
kodlu avatar
sa flag
Fair enough. *But* if you wanted to understand if there is an intrinsic reason, based on the parameters $N,m$ in my comment and the exact order of the two operations that determine whether the overall outcome's order sensitivity, that is a mathematical crypto question. I am talking about your question 1. I still don't understand what exactly is the setup, but no matter.
caveman avatar
in flag
@kodlu - Done (thanks, you're right; I overlooked that).
Score:1
sa flag

This is one simple idea.

I will use $x_i$ for the vector in $d$ dimensions and use $a_i$ for the corresponding integer in $\{0,1,\ldots, 2^d-1\}$.

Sort the $a_i$ from small to large. Let $r_i$ be the rank of $a_i$ use ranks from $\{0,1,\ldots,v-1\}$. Break ties arbitrarily during sorting.

Example: $(a_1,a_2,a_3)=(1,7,2)$ has rank vector $(r_1,r_2,r_3)=(0,2,1).$ There are three entries numbered from 0 to 2 and the middle entry 7 is the largest with rank 2.

Now consider the list of permutations of 3 objects in standard lexicographic order and their index

$$ 012~~0\\ 021~~1\\ 102~~2\\ 120~~3\\ 201~~4\\ 210~~5\\ $$ and note that this permutation is 021 so has position 1 in the list of permutations. Encoding the position as a binary vector takes $r=\lceil \log_2 v\rceil$ bits.

If $r\leq d,$ we can define $$ x_1+x_2+\cdots+x_v=x_1\oplus x_2\oplus \cdots\oplus x_v \oplus index(permutation(x_1,\ldots,x_v)), $$ so at the end we xor the index of the permutation which changes if the $x_i$ are reordered.

caveman avatar
in flag
How does this compare to my idea above? E.g. recursively for any $i$, $x_i + x_{i+1} = x_i \oplus (x_i + x_{i+1} \mod 2^d)$, with the base case being $x_0 = x_0$. Basically I mainly wonder about two aspects: (1) sensitivity to order, and (2) speed. As for (1) I think it implies reduced collisions; e.g. how likely is it for different numbers of different orders to eventually get same final number?
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.