# Tag Info

13

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

12

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

11

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

10

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

9

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

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

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

8

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

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

8

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

8

They don't, and in fact the sponge construction used in Keccak (SHA-3) allows for variable length output. In other hashes the Merkle-Damgård construction was used which has a fixed output length due to the nature of its design. But there is no reason to not allow for variable output length other than ease of development or use.

8

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

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

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

7

Security is clearly broken if there is a polynomial-length period with non-negligible probability (where by this I mean if a random point falls in a cycle with a poly-length period with non-negligible probability). In order to find a preimage, just go forward until you get back to the starting point, keeping the previous value each time.

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

6

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

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

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

Your scheme would make a nice puzzle for amateur codebreakers. That's about the best that can be said for it. It does not meet the generally accepted standards for a modern encryption scheme; in particular, it is not semantically secure. In fact, the security of your scheme would be seriously compromised if an attacker obtained even a small amount of ...

6

No, you can find $f$ such that $f(x)$ is a OWF, but $f(x)\oplus x$ is not. One example would be $f(x) = AES_k(x) \oplus x$ (for a public key $k$, perhaps the all-zeros key). $f(x)$ is believed to be one way; as there is no known practical way, given a value $y$, to find an $x$ with $f(x) = y$. However, $g(x) = f(x) \oplus x = AES_k(x)$ is easy to invert ...

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

5

The modulus 77 leads to a short period.

5

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

5

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

5

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

5

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

5

Yes you could use a hash function as round function, but if you are using the "same key" over all rounds, you are vulnerable to slide attacks. Using a hash function is not a very good idea. Your round function should not introduce biases, should not lead to special differences (attack: differential cryptanalysis), and it should also not be writable as a ...

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