# Tag Info

7

In theory. No. The inverse of a secure PRP need not be a secure PRP. Here is what we can guarantee. The inverse of a secure sPRP (strong-pseudo random permutation) is guaranteed to be a secure sPRP. Any secure sPRP is a secure PRP. Therefore, the inverse of a secure sPRP will be a secure PRP. FYI, if you are not familiar with PRP/sPRP, the difference ...

6

a permutation will rearrange the input producing something of arbitrary length. I'm not sure about this. My understanding of a permutation is that it will always produce an output of the same length as the input. That is, a permutation simply reorders all the parts of the input without adding or removing any elements. A hash function does not have ...

6

As Henrick notes, permutation is a mathematical term for a function (or map; these two words are essentially synonymous in mathematics) that rearranges the elements of its domain so that exactly one input is mapped to each output. In other words, a function $f$ from a set $S$ to $S$ is a permutation if and only if: no two inputs are mapped to the same ...

4

In Algebra, a Permutation of a set $X$ is a bijective function $\sigma:X{\rightarrow}X$ that for each element $x \in X$ assigns a unique value $\sigma(x) \in X$. In practice, this could mean a lot of things. For instance, in DES a permutation is used that rearranges the position of the bits of the half block. This is a permutation ...

3

There are so many possible solutions here. Without giving your requirements more carefully, it's just not possible to tell what would count as a valid solution. Here are a bunch of schemes that offer better security than simply truncating to $N/2$ bits and applying 4 rounds of Luby-Rackoff: For instance, one approach is to truncate the random function to ...

3

At some level, there is no essential difference. Certainly, there is no difference in the distribution on the random variable $O$ vs $f$. However, there is a potential difference in how the terms are typically used. If we say that $O$ is a random (bijective) oracle, then we are usually implicitly hinting that it is available to everyone: the legitimate ...

3

If you take a pseudo random permutation permutation you usually get a hard to invert PRF. AES with its 128 bits is a bit narrow, but Salsa's 512 bits are certainly wide enough. Commonly used compression functions are built from block-ciphers with similar techniques: For example Davies–Meyer (used in popular hashes such as MD5, SHA-1 and SHA-2) uses: $H_i ... 2 If you are asking about a truly theoretical limit for a theoretical block cipher (as opposed to a practically usable one, like AES), you could calculate the number of possible keys like this: A block cipher, together with a key$k$($|k|$=$M$), describes one of many possible random permutations: For every plaintext block, there is exactly one ciphertext ... 2 There is a generic construction called Permutator, which can turn a seekable stream of random bits into a permutation. A "seekable stream" is obtained from a PRF by applying the PRF on an input index. This construction works with any target space (it generates a permutation of a space of size$n$where$n$is not necessarily a power of 2). Also it is ... 2 Measuring the size of the key space in transposition algorithms is not important, because their security is far less than the size of the key space would suggest. Therefore, any measure of effective key length will be misleading and will not give an accurate picture of the true security of the scheme. In general the standard way to compute the effective ... 2 Each one of your first two sentences has a mistaken premise: you're starting from some assumptions that aren't actually true. DES does not use small PRPs for saving memory. It doesn't use small PRPs at all. The DES S-boxes are not PRPs. The DES F-function is not a PRP. A SPN does not use several small PRPs for saving memory. A SPN doesn't use PRPs at ... 2 In a strict sense, no. NP is about worst-case hardness. Cryptography requires average-case hardness.$P \ne NP\$ implies the existence of problems that are hard in the worst-case (the worst-case running time is super-polynomial) but says nothing about average-case hardness. For block ciphers, we need average-case hardness. Therefore, there are good ...

1

There's been similar questions before but the answer is probably no with very high probability. You can imagine a hash as being a little box with a dwarf in it. You give him a message and the first thing he does is looks for the message in his book. If he finds it, he gives you the n-bit string he wrote in his book. If it's not in his book, he rolls some ...

1

There is a recent paper by Hoang, Morris & Rogaway which proposes an alternative construction of PRPs from PRFs. Viet Tung Hoang, Ben Morris, Phillip Rogaway, An Enciphering Scheme Based on a Card Shuﬄe, CRYPTO 2012 The construction has a few nice features. First, the domain of the PRF is preserved, which is one of your requirements. Second, it ...

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