Tag Info

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 ...

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 ...

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 ...

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 ...

The wide class of NP problems meets your general question, almost to the exact definition. The summary is that (we conjecture that) there are problems that cannot be solved in as little as polynomial time but have solutions that can be verified to be correct in just polynomial time, so solving for the answer takes much longer than verifying the answer is ...

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 ...

Many lattice schemes are based on the shortest vector problem and it's variants. Elliptic curve crypto systems are based on something akin to discrete logarithms but it is different in its details. Some authentication schemes like HB are based on learning parity with noise and systems are based on the more general learning with errors. Subset sum was ...

The Merkle–Hellman knapsack cryptosystem was based on a variation of the subset sum problem. (It was broken by Adi Shamir a few years after it was developed.) Given a set of numbers $A$ and a number b, find a subset of $A$, which sums to b. The cryptosystem relies on the fact that in this form of the subset sum problem if the set $A$ is ...

Each additional signature halves the security level. 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 you use 256 pairs, which is a reasonable level, since it offers 256 bit security against second-preimage attacks, and 128 bits against collisions, ...

As Mike asked, it's not clear if you're asking about onewayness, or collision resistance (as you call the function a 'cryptographic compression function'). Assuming you're asking about onewayness, well, given a single 128 bit value $h(M)$, we obviously cannot uniquely deduce the 1408 bit value $M$. However (hint), let us assume that we can ask for the ...

I will just like to contribute in light of what has been told above. There are few cryptosystems (just signature schemes as far as my knowledge goes) that are based on the hardness of solving a system of multi-variate polynomial. Solving a system of multi-variate polynomial is proved to be $\mathsf{NP}$-hard and just like the "hard" problems on lattices, ...

Now, the AES Key Schedule may be weak (it certainly does appear to be the weakest part of AES), however I don't believe invertability is really the problem. If someone has a way to get some information on the last-round subkey for an N round cipher, well, he has some information on the original key if the key schedule is invertible; if he determined $k$ ...

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 ...

Yes, it makes sense to truncate the hash to 128 bits. The security proof actually says that if finding a preimage for F requires effort 2^n, then breaking the Lamport signature scheme with G having k-bit digests requires effort (2^n)/(2k). So strictly speaking, with F truncated to 128 bits and G having 256 bits (2k=512=2^9), you will have 128-9=119 bits of ...

Well, if "weak one way" means that you shouldn't be able to consistently find preimages, that is, inputs that generate a specific output, and $mult(a, b)$ is defined as the integer multiplication $a \times b$, then $mult$ would not meet that definition. For an arbitrary output $C$, we can set $a = C$ and $b = 1$; hence $mult(a, b) = C$.

Yes, there are hash-like algorithms that are able to produce variable-length outputs without any extra efforts. This is something "sponge functions" do. One such sponge construction is KeccaK which is one of five finalists in the SHA-3 competition.

I'm curious about your purpose. Generally the primary operation involving a message digest is ultimately to compare two digest values. Hashing passwords allows comparing the digest values instead of carrying the super secret password around the systems. Hashing messages allows the transmitter and sender to verify the data was correctly received without ...

What do you mean by forge? If you are asking about (the common) existential forgery, then two message, signature pairs are enough, given that the messages differ in at least two bits. As an example consider that you have the signatures for $m_1 = 1111$ and $m_2 = 1100$. Considering the preimages you now have, you can forge signatures for $m_3=1101$ and ...