La somme $ f + g $ de deux fonctions unidirectionnelles est-elle une fonction unidirectionnelle?
-
05-11-2019 - |
Question
Puisqu'il existe une bijection d'ensembles de $\{0,1\}^*$ à $ mathbb {n_0} $, nous pourrions considérer les fonctions unidirectionnelles comme des fonctions $ f: mathbb {n_0} rightarrow mathbb {n_0} $. Ma question est, supposons $ f, g $ sont des fonctions unidirectionnelles, c'est alors $ (f + g) (n): = f (n) + g (n) $ une fonction à sens unique ou peut-on construire un contre-exemple? (La longueur de $ n $ est $ text {plancher} ( frac { log (n)} { log (2)}) = $ le nombre de bits à représenter $ n $)
Commentez la réponse de @Bulat: Supposons $ f $ est un OWF. Si (?) Il existe un $ k in mathbb {n} $ de tel que pour tous $ x in mathbb {n_0} $ Nous avons $ f (x) le x ^ k $. Ensuite, comme @bulat l'a mentionné, construire $ g (x) = x ^ kf (x) ge 0 $. Alors $ g (x) $ est un owf comme $ f $ est, mais $ h (x) = g (x) + f (x) = x ^ k $ n'est pas un OWF. La question est donc de savoir s'il existe un tel $ k $. L'argument fonctionnerait également en considérant $ k ^ x $ à la place de $ x ^ k $. Mais la même question demeure? Pourquoi un tel $ k $ exister?
Merci pour ton aide!
Pas de solution correcte