Please help me identify a family of polynomials P(x,k) with the following properties:

  1. $x\in Z_{2^n} $
  2. $\forall k, \forall p_k\in P,\ \exists\ p_k^{-1} |\ p_k^{-1}(p_k(x)\equiv x\ mod\ 2^n $
  3. Frequency distribution of $y = p_k(x)\ mod\ 2^n$ is an inverted bell curve

Thanks for suggestions

  • $\begingroup$ So why would you name it "cryptographic invertible", not jut "invertible"? $\endgroup$ Sep 2 '18 at 7:42
  • $\begingroup$ I need pseudo-randomness on $y$ for any $x$ $\endgroup$
    – Baruntar
    Sep 2 '18 at 7:45
  • $\begingroup$ How would you measure/define "frequency"? It would be natural to expect just a single "inverse" for any given polynomial. $\endgroup$ Sep 2 '18 at 15:37
  • $\begingroup$ In #3, what is the underlying random process? Uniform choice of x and fixed k? Uniform choice of k and fixed x? $\endgroup$
    – Mikero
    Sep 2 '18 at 16:17
  • $\begingroup$ @Mikero, Uniform choice of x for fixed k. $k$ is chosen randomly once to define $p_k(x)$ i.e. $p_K(x)=p(x,k)|_{k=K}$ $\endgroup$
    – Baruntar
    Sep 3 '18 at 5:42

These requirements are impossible. If $p_k$ is a permutation, then the distribution induced by "choose $x$ uniformly in $\mathbb{Z}_n$, output $y=p_k(x)$" is also uniform in $\mathbb{Z}_n$. It can't follow a normal distribution. For every possible $y$, there is exactly one $x$ that makes it happen, and that $x$ is assigned probability $1/2^n$.


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.