# A candidate for one-way functions

For every $$n \geq 3$$ consider a bipartite random $$3$$-regular graph $$G_n$$ with two parts $$X=\{x_1, \dotsc, x_n\}$$ and $$Y=\{y_1, \dotsc, y_n\}$$. For any $$i \leq n$$ assign either 0 or 1 to each vertex $$x_i$$, and denote it $$\ell(x_i)$$. For every $$i \leq n$$ define $$\ell(y_i)$$ as follow: $$\ell(y_i)=1$$ if and only if the function $$\ell(.)$$ over at least 2 of neighbors of $$y_i$$ is 1. In other words, $$\ell(y_i)$$ takes the majority value of $$\ell(.)$$ over its neighbors. Finally, define the function $$f_n: \{0, 1\}^n \rightarrow \{0, 1\}^n$$ by $$f\left(\ell(x_1), \dotsc, \ell(x_n)\right):= \left(\ell(y_1), \dotsc, \ell(y_n)\right)$$.

Can the family of function $$\{f_n\mid n \in \mathbb{N}\}$$ be a candidate for one-way functions, where $$\{G_n\mid n \in \mathbb{N}\}$$ is public? Has this family been studied before? Do you know of any references related to this?

• If you consider a candidate assignment $\ell'(x)$ given by the majority function over the neighbours in $Y$, any deviation from that candidate assignment has strong implications. If $x_i$'s neighbours are assigned $0,1,1$ and we instead were to assign $0$ to $x_i$ then that forces (in general) four other values of $x_j$ to $1$. They may in turn force more values. It might be worth experimenting with medium-sized graphs to estimate how many values can be determined on average by searching for contradictions in these implication chains, which takes quadratic time. Commented Sep 4 at 7:36
• Ninth edition of a question asked just yesterday. Commented Sep 5 at 0:04
• Why is your function defined? That is, why does every tuple in $\{0, 1\}^n$ arise this way, and why does the result of the function depend only on the tuple, and not on the weighting $\ell$ chosen to achieve it? Commented Sep 5 at 1:01

3-majority can be modeled with 2-SAT, so $$f$$ can be inverted in polynomial time. The majority of $$x_1,x_2,x_3$$ is 1 iff $$(x_1\lor x_2)\land(x_1\lor x_3)\land(x_2\lor x_3)$$, and it is 0 iff $$(\lnot x_1\lor \lnot x_2)\land(\lnot x_1\lor\lnot x_3)\land(\lnot x_2\lor\lnot x_3)$$.
• Are you suggesting the problem is NP-complete by Shaeffer's theorem? I don't see how that's supposed to work. Letting $\mathrm{MAJ}_5$ denote majority on 5 variables, $\mathrm{CSP(\{MAJ_5,\neg MAJ_5\})}$ is NP-complete all right, but this is a more general problem, where the sizes of $X$ and $Y$ are unrelated, and vertices of $X$ can have arbitrary degree rather than the graph being 5-regular. Commented Sep 5 at 20:26
• @EmilJeřábek The sizes of $Y$ and $X$ being equal doesn't matter, as you can just pad them. However, I haven't thought about the vertices of $X$ being regular, you're right Commented Sep 6 at 1:25