1
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Peter Taylor
    Commented Sep 4 at 7:36
  • $\begingroup$ Ninth edition of a question asked just yesterday. $\endgroup$
    – Gerry Myerson
    Commented Sep 5 at 0:04
  • $\begingroup$ 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? $\endgroup$
    – LSpice
    Commented Sep 5 at 1:01

1 Answer 1

Reset to default
5
$\begingroup$

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)$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ What about 5-majority in random bipartite 5-regular graphs? $\endgroup$
    – Arash Ahadi
    Commented Sep 5 at 5:48
  • $\begingroup$ Then reversing this is NP-complete by the dichotomy theorem, but I don't know about the average case $\endgroup$
    – Daniel Weber
    Commented Sep 5 at 15:59
  • $\begingroup$ 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. $\endgroup$
    – Emil Jeřábek
    Commented Sep 5 at 20:26
  • $\begingroup$ @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 $\endgroup$
    – Daniel Weber
    Commented Sep 6 at 1:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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