6
$\begingroup$

This question is a generalization of this old, unanswered question.


Suppose we're given a strong PRP $E:\mathcal K\times\mathcal M\to\mathcal C,(K,M)\mapsto C=E(K,M)$. Suppose further we pick a constant parameter $S\in\mathcal M$.

Is $F_S:\mathcal K\to \mathcal C, X\mapsto E(X,S)$ a secure one-way-function?
If the above is not answerable: Is $F_S$ at least a secure OWF for practical purposes?

As example instances one can imagine $S=0^{128},E=\operatorname{AES}$ or $E$ being a fixed-key AES instance within an Even-Mansour construction.

$\endgroup$
1
  • $\begingroup$ FWIW some X9 committee thought the variant of known and predictable but not constant data was safe when designing DUKPT decades ago; it uses K_(n+b) = DES(K_n, n+b) plus a little whitening as a claimed-irreversible 'transform' to derive a sequence of keys K_i that are intended to be forward-secure. $\endgroup$ Dec 21, 2017 at 4:15

2 Answers 2

2
$\begingroup$

Since $E$ is a secure PRP, instead of giving $C=E(X, S)$ to the adversary, you can give a uniform random $C\gets\mathcal{C}$. To 'invert' this, adversary has to find a key $X'$ such that $E(X', S)=C$.

So, the construction being one-way function is equivalent to the property that, given a uniform random $C$, it should be hard to find $X$ such that $E(X, S)=C$. I don't think that this necessarily follows from $E$ being secure, strong PRP. For example, when the block cipher has polynomial-sized small domain (rather unusual case, I know), then this would not hold. On the other hand, most reasonable block cipher constructions would have this property, I guess. So, I think it could be considered as a secure OWF for practical purposes, in reasonable settings.

$\endgroup$
2
$\begingroup$

I will take ‘one-way function’ to mean preimage-resistant in the concrete setting, where for a preimage-finding algorithm $A$ we have $$\operatorname{Adv}_H^{\mathrm{pre}}(A) = \Pr[H_\mathit{salt}(A(\sigma)) = \sigma],$$ where $\mathit{salt}$ and $\sigma$ are uniform random bit strings, and presumably we hope $\operatorname{Adv}_H^{\mathrm{pre}}(A)$ to be bounded by $C(q)/2^n$ if $A$ makes $q$ queries with some plausibly small $C(q)$ when the output of $H$ has $n$ bits.

PRP security of $E$ does not imply preimage resistance of $H_\mathit{salt}\colon X \mapsto E_X(\mathit{salt})$, because there may be arbitrarily much structure known to the attacker about the input $X$, which violates the assumptions of PRP security. We have no reason to doubt the PRP security of AES-256, but it does not provide this preimage resistance.

An ideal cipher $E$ would imply preimage resistance of this construction, as shown by Black, Rogaway, and Shrimpton as case $j=17$ with $v = 0$, with the adversary's best probability in the interval $[0.15q^2/2^n, 9(q + 3)^2/2^n]$. But you need to find a better cipher than AES-256 for this to work out.

$\endgroup$

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.