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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .