New answers tagged

4

No, neither of the two blocks of 6 equalities in the current version of the question are correctly describing either a trapdoor one-way function (first citation); or its use for public-key encryption; or signature of a message using a one-way hash and RSA (second citation). The two citations are only distantly related. In particular, the "one-way hash" in ...


2

Your suggested formalization is not quite right. Also your notation isn't consistent with Schneier's. Schneier calls the hash function $f$, the input $x$ and the trapdoor $y$. The hash value of $x$ is the image $f(x)$ of $x$ under $f$. In general it is very difficult to compute $x$ just from $f(x)$. There is an efficiently computable function $g$, however, ...


0

By "one way function" do you mean preimage resistant, or do you mean that the function doesn't ever reveal the input? Assume H(x) is a collision-resistant function. Let L(x) = the last 256 bits of x. Then, let G(x) = H(x) || L(x) That is, G(x) is the concatenation of a collision-resistant hash of x, and the last 256 bits of x. Now, over all ...


0

A Cryptographic hash function as described in the literature has 3 criteria: Preimage resistance: Given $H,y$, it is "hard" to find an $x$ with $H(x)=y$ Second Preimage resistance: Given $H,x,$ it is hard to find $x'\neq x$ with $H(x')=H(x)$ Collision resistance. It is hard to find 2 $x,y$ with $H(x)=H(y)$ The very definition used (the first 1 and the ...


2

Thomas Pornin already explained why such a thing is not usually possible, but I would like to quote a graphic from Rogaway and Shrimpton's "Cryptographic Hash-Function Basics: Definitions, Implications, and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision Resistance" (pdf): The dotted arrow from Collision resistance to ...


7

It is going to be pretty hard to achieve collision resistance without one-wayness. Indeed, negation of one-wayness means that for a given output, you can find a corresponding input. So a collision is easily obtained by simply choosing a random input m, hashing it into output x, then finding a preimage m' for the obtained output x. The only way for such a ...


2

A one-way permutation is just a one-way function in which the function is a permutation (id est, a bijective function). Every OWP is a OWF, the converse is not true. IND-CPA security is a security notion specifically related to encryption schemes. OWF and OWP are not encryption schemes, hence they cannot be said "IND-CPA secure"; however, one can construct ...



Top 50 recent answers are included