# Tag Info

11

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

10

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

8

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

8

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

8

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

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

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

6

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

6

This is highly insecure, for the same reason that ECB mode and simple substitution ciphers are. Every time you use the word the in your message, it will be encrypted the same way. The same goes for other, lower-frequency (but still fairly common) words -- like as or with or will (or any of hundreds of other examples). This is a humongous clue to ...

6

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

6

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

6

This is probably not secure enough for a proof of work. I'll outline some attacks, of increasing sophistication/complexity and increasing effectiveness (decreasing runtime). Brute force The obvious attack is brute force: enumerate all $2^{32}$ possible inputs and check to find the first that produces the desired output. This takes $2^{32}$ time. I'm ...

5

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

5

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

4

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

4

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

4

"Frequency analysis of the output might help determine simple words in the ciphertext such as 'the' etc if that word is repeated and sent multiple times. This isn't necessarily a problem as it's only a simple word and doesn't convey much meaning to the message". If the word "the" doesn't convey much meaning, then why have you used that particular ...

4

A trapdoor one-way injection is a trapdoor one-way function such that two different elements of a single domain are never mapped to the same element of the corresponding codomain. By Goldreich-Levin, if there exists an trapdoor one-way injection then semantically secure public key encryption exists.

4

It is not entirely clear what you want, but suppose you need a trapdoor permutation - the function that is easy to invert only if you know a secret parameter - and which is not based on number-theoretic assumptions. There are two well known families of such schemes: Multivariate Cryptography (MQ) and Code-based cryptosystems (for instance, McEliece ...

3

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

3

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

3

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

3

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

3

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

3

Hard-core bits are related to one-way functions. For some intuition on what hard-core bits are, consider a one-way function $f$. SInce it's a one-way function, it's hard to invert: that is, if I select a random $x$ in the function's domain and give you $f(x)$, you cannot find a $x'$ such that $f(x) = f(x')$ with non-negligible probability in probabilistic ...

3

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

3

Say $m$ is the number and $h=f(m)$ it will be pretty easy to find $m'$ (not necessarily equal to $m$) such that $f(m)=f(m')$ on a modern computer. Brute Force The output of $f(m)$ is 32 bits. The following python function will do it def find_collision(val): while True: test = random.getrandbits(32) target = ((test*test) >> 16) & 0xffffffff) ...

3

Someone can find a preimage (or prove that there is no such preimage) with about $2^{20}$ trial squares, and no precomputed storage. ACtually, I believe that the below procedure will actually achieve $2^{18}$ trial squares; that requires closer analysis than I feel like at the moment. Here is the key observation that we can take advantage of to show this: ...

3

Quite a difficult question. What you seem to need is a one-way permutation $P$. Indeed, suppose you have it of width $d$, then consider the function $$F(K,S,R_S) = E_{K_2}(P(E_{K_1}(S,R_S))),$$ where $E$ is any good 64-bit block cipher (say, Simon) and $K_1,K_2$ are derived from $K$. This function $F$ should fulfill (2) because of the encryptions of both ...

2

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.

Only top voted, non community-wiki answers of a minimum length are eligible