Tag Info

Hot answers tagged permutation

11

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

First of all, we need to review what they mean by "parity of a permutation"; they don't mean whether the input block had a even number of 1's. Instead, they view the $n$ bit cipher (with a specific key) as a permutation on $2^n$ objects; that is, it can be review as a way of rearranging that set of $2^n$ objects onto itself. Now, permutations on a finite ...

5

If I understand correctly, you want a function that for each input string $p$ assigns a permutation over an alphabet $L$. If the number of elements in $L$ is small enough, the permutation set $P(L)$ will be enumerable. More precisely, $|P(L)| = |L|!$. There exists a surjective function $f:\{0,1\}^k \to P(L)$ that for each bit string $s$ of length $k$ ...

4

This is purely a counting problem. We want the number $N(n,m)$ of possible permutations of $n$ things, with the constraint that only $m$ among these things can map to themselves ($0\le m\le n$). The values in the question are $n=11$, $m=5$. It holds that $N(n,n)=n!$ (that's the number of permutations of $n$ elements). It holds that ...

4

"$BW_N$ is a permutation over the squares $\mod N$". Does someone know what that means? You define your map $BW_N:\mathbb{QR}_N\rightarrow \mathbb{QR}_N$. Note that $$\mathbb{QR}_N:=\{r\in Z_N: r\equiv y^2 \pmod{N}, y\in Z_N\}$$ and a permutation is a one-to-one mapping (bijection) from a set into the same set. Basically, this map is a permutation if ...

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 ... 3 How secure is this cipher? At first glance, not very. It would appear to be vulnerable to a ciphertext-only attack, for example, the attacker can recover the plaintext given a ciphertext of about 10k (actually, he probably can deal with less), even assuming that all the attacker initially knows is that the plaintext is "ASCII English", and he has no ... 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 ... 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 It means that it maps quadratic residues$\mathbb{QR}_{N} \mapsto \mathbb{QR}_{N}$to quadratic residues. A quadratic residue is a number$x$such that$x = y^2 \pmod N$where$N=pq$. A trapdoor means that once you know the factorization of$N$it is easy to break quadratic residuocity problem.$p=q=3 \pmod 4$because you choose 'safe' primes$p,q\$ such that ...

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

My own answer would be: 2048, 2048, and still 2048 bits. Why ? Because: 2048-bit is the current "standard recommendation"; it has been so for quite some time, and is likely to remain so for quite some time (decades). See this site for pointers. There are plans for removing support for keys shorter than 2048 bits in some widespread software, e.g. Firefox. ...

1

The closest to my choice is: C. (a) 2048; (b): 4096; (c): I would not use RSA My answer takes in account not only details mentioned in question, but currently widely deployed security practices. I try to point out useful resources to study. Things are not as simple as pick one of A-D. I recommend to study resources I've included and draw your own ...

1

Consider Shor's algorithm, which solves RSA in polynomial time on a quantum computer and the fact that there is publicly available software that could factor a 512 bit modulus on a modern PC in a few days' time.

1

This was covered on scicomp (http://scicomp.stackexchange.com/questions/4923/random-access-random-permutations), but I'll copy the answer here (not sure if that's appropriate but it definitely belongs in both places). You are looking for Black and Rogaway, Ciphers with Arbitrary Finite Domains, 2001. ...

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