66
Data integrity is another usage. For example, when you want to send/download data, you want to make sure that the data is not modified or transmitted/downloaded correctly. To achieve this the data hashed and the hash value sent/downloaded on another channel. One may see examples of this file verification on Linux ISO download pages. Of course, hashing is not ...
26
Applications for one-way-functions in cryptography
Hash-collisions may happen in rare cases, but are mostly disregarded here.
Data integrity
Integrity
A quick way to ensure integrity of data is to compare two hashes, where one is a previously calculated hash and the other is the newly calculated hash of the data, which is presumed to be unmodified. If ...
25
In the Lecture Notes on Cryptography of Goldwasser and Bellare, one can find (page 35) the following text:
Recall that f(x) does not necessarily hide everything about x even if f is a one-way function. E.g. if f is the RSA function then it preserves the Jacobi symbol of x, and if f is the discrete logarithm function EXP then it is easy to compute the ...
21
A trapdoor function is a function that is easy to perform one way, but has a secret that is required to perform the inverse calculation efficiently. That is, if $f$ is a trapdoor function, then $y = f(x)$ is easy to compute, but $x = f^{-1}(y)$ is hard to compute without some special knowledge $k$. Given $k$, then it is easy to compute $y = f^{-1}(x, k)$. ...
16
Sure. If you want a $b$-bit hash of the message $m$, then use the first $b$ bits of AES-CTR(SHA256($m$)). That'll do the trick.
In other words, compute SHA256($m$) and treat the resulting 256-bit string as a 256-bit AES key. Next, use AES in counter mode (with this key) to generate an unending stream of pseudorandom bits. Take the first $b$ bits from ...
14
It is easier to prove that $P = \mathit{NP}$ implies one-way functions do not exist:
Let $P = \mathit{NP}$, and assume $f$ is one-way. Then consider the language $L$ of pairs $(x^\ast, y)$ such that $x^\ast$ is a prefix of some $x$ satisfying $f(x) = y$. $L$ is in $\mathit{NP}$ because $x$ itself is a witness (up to minor formal details; see this question ...
13
There are techniques for doing online surveys on sensitive subjects. They don't follow the approach you outlined, but here's a sketch of how they work.
Suppose we want to survey people to determine how many people have ever seriously considered suicide (say), but we suspect many people might be unwilling to answer honestly because of the stigma associated ...
13
As D.W. notes, you can use the output of any conventional hash function to key a stream cipher (or a block cipher in a streaming mode like CTR), and then take the output of the cipher as your digest.
However, there has been a trend in modern hash function design to support arbitrary-length output directly, without the need for additional layers. For ...
13
While poncho's answer gives an interesting example, why this can go wrong in practice, it does not necessarily answer the question from a theoretical point of view.
After all, we don't know whether $f(x) = AES_k(x) \oplus x$ is one-way. (Even if it might be reasonable to assume that.)
So, let's give a theoretical example.
Assume that a one-way function $h$ ...
13
The function $f$ introduced by Maeher in this answer to a related question should also do the job here (as both $g$ and $h$). For convenience, let me quote that answer here:
Assume that a one-way function $h$ exists where in- and output length are the same. We call this length $n/2$. I.e. we have a one-way function $$h : \{0,1\}^{n/2} \to \{0,1\}^{n/2}.$$...
13
Simon [Sim98] showed that is not possible to build a collision-resistant hash function from a one-way permutation (which is a stronger statement) in a black-box manner .
The main idea is to use the so-called oracle-separation technique. You can read more about it either here or in this survey.
[Sim98]: Daniel Simon. Finding collisions on a one-way ...
11
I'm not sure how much simpler than Wikipedia one can explain this.
Assume you have a function $f$ which gets some input $x$, and produces from it some output $y = f(x)$. As one example, consider the function $f(x) = x·x$.
Assume that $x$ is a non-zero real (or rational, or integer) number. Then $y = f(x) = x·x$ is still a non-zero number, and in this case,...
11
I'm also afraid you couldn't understand this as D.W., but let us start.
I sometimes cannot understand your questions. Please restate them, if possible.
The definition of the Ajtai hash functions
Let $n$, $m$, and $q$ be positive integers.
Let $R = \mathbb{Z}_q$ be the quotient ring of integers modulo $q$.
Let us define a function, which maps a vector in $D^...
10
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 ...
9
It's a fine one-way function, based (as you noted) on the computational difficulty of the discrete logarithm problem. As far as its relation with modern-day cryptographic hash functions, however, it lacks two quite important properties.
Here's an okay definition: a function $H$ is called a cryptographic hash function if it possesses the following three ...
9
This requirement is a killer:
The paper (or any medium other than the brain) must not at any time contain data that leaks information about the plaintext.
Almost any security proof for a hash assumes an adversary only gets to see digests, not any mid-state. Mid-state has not had enough confusion and diffusion, so it leaks information.
This means that ...
9
In general, each combination of a (secure) hash function for input with a (deterministic) pseudo random number generator for output will work here - one "state of the art" example is the one given by D.W. (using AES-CTR as PRNG and SHA-256 as hash).
Another way is similar to what PBKDF-2 does to have output with the right length: hash the input (or a hash ...
9
ChaCha builds on a 512 bit permutation and then applies a feed-forward by xoring the input into the output. Without truncation, that feed forward is essential for one-way-ness.
We're going to build a one-way function that maps a 32 byte value x to another 32 byte value y.
Using truncated ChaCha including the feed-forward
Put the x into the 32 key part of ...
9
No, it is not collision-free. All possible sequences of 0's produce the same output:
0 --> (2 ** 0) = 1
00 --> (2 ** 0) * (3 ** 0) = 1
000 --> (2 ** 0) * (3 ** 0) * (5 ** 0) = 1
0000 --> (2 ** 0) * (3 ** 0) * (5 ** 0) * (7 ** 0) = 1
In fact, it can be seen that $f(s) = f(s||0)$, for every bit-string $s$.
This could be easily solved by ...
9
This is very confusing because it seems as it should be something really easy to prove. However, it actually is not, and in fact the proof uses the Borel-Cantelli lemma. Anyway, it was formally proven by Rudich and Impagliazzo in their groundbreaking work on black-box separations. You can find a formal proof in Rudich's thesis, Section 6.2, or in the paper ...
9
If a permutation $f$ is not one way, we can not conclude about the one-wayness of $f^{p(n)}$. In fact, even $f^2$ could be one-way, if there are one-way length-preserving permutations that is.
Constructive proof: assume $g:\{0,1\}^*\rightarrow \{0,1\}^*$ is a length-preserving OWP, not invertible starting with rank $m$. Define $f$ from $g$ such that, for ...
8
If the message is random each additional signature halves the security level. If the message is chosen by the attacker, two signatures (of messages where each bit differs) are enough for a complete break.
A security level of about 64 bits can be broken by a determined attacker, and a level of 32 bits can be trivially broken on a single home computer.
So if ...
8
An advantage of a cryptographic accumulator and actually the reason to use them is that due to the quasi commutativity you can compute witnesses for
membership of values in the accumulator where the accumulator and the witnesses are of constant size.
Say you
have a set $Y=\{y_1,y_2,y_3\}$ and compute the accumulator as $acc=f(f(f(x,y_1),y_2),y_3)$ you ...
8
You'll find it in any textbook on basics of cryptography, for example Foundations of Cryptography by Goldreich. I have added a figure which sums up the relationship between the primitives: arrow represent reductions (i.e. $A\rightarrow B$ means that primitive $B$ can be constructed in a black-box manner from primitive $A$) and dashed arrows represent ...
8
Yes, it could be that in the language you give, $x$ is exponentially long in $(y,x')$, and $f$ is an efficiently computable one-way function (note that it only has to run in time polynomial in its input length, so $f(x)$ needs not be computable in time polynomial in $(y,x')$).
However, this is really a minor issue: the answers to this question that you read ...
7
There exist efficient algorithms to compute quadratic roots modulo a prime or prime power.
If you know the factorization of the modulus you can use the above to compute quadratic roots mod the prime factors and then combine them using the chinese remainder theorem to efficiently compute the quadratic root of the full modulus.
Thus, if you can factor the ...
7
Factoring $\longrightarrow$ square roots.
Computing square roots modulo a prime $p$ is easy: if $p \equiv 3 \pmod 4$ and $a$ is a quadratic residue modulo $p$, then $a^{(p + 1)/4}$ is a square root of $a$ modulo $p$; for $p \equiv 1 \pmod 4$, you can use Cipolla or Tonelli–Shanks.
Computing square roots modulo a composite of known prime factorization is ...
7
It sounds like you're looking for a proof-of-work system.
One way to implement such a system would be, given a message $m$, to ask for a suffix $s$ such that the hash $H(m \operatorname{\|} s)$, where $H$ is some standard cryptographic hash function and $\|$ denotes concatenation, begins with a specific prefix (e.g. $n$ zero bits).
Of course, the execution ...
7
I still don't understand your desire for a hash, especially considering (as already stated at other places in this forum) that you don't gain any entropy by subjecting a PW
to a deterministic function like a hash. So, when decrypting your ciphertext, you will be as secure with a H(key) as with (key), thus you might as well just memorize a good long ...
Only top voted, non community-wiki answers of a minimum length are eligible
