Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $BW_N$ be a function such that $BW_N:\mathbb{QR}_{N} \mapsto \mathbb{QR}_{N}$ and let if be defined as follow: $BW_N(x) = x^2 \pmod N$ where $N=pq$ and p and q are primes and $p=q=3 \pmod 4$. I am reading on a set of lecture notes that, "$BW_N$ is a permutation over the squares mod N". Does someone know what that means?

Does that mean its a trapdoor permutation? Or what might it mean?

I am not sure if this question would have been more appropriate on the mathematics stack exchange site, but it had to do with crypo so I though it might get a response here.

share|improve this question
Permutation over some set means the same as bijection from that set to that same set. – fgrieu Jan 21 '14 at 9:22
up vote 4 down vote accepted

"$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 under $BW_N$ for every $x\in \mathbb{QR}_N$ there is a unique $y\in \mathbb{QR}_N$ (and clearly the same for its inverse $BW_N^{-1}$).

Now, since you have $N=pq$ being the product of two Blum integers $p$ and $q$, you have that for every of the four possible square roots of $r\in\mathbb{QR}_N$, which are of the form $(\pm\alpha,\pm\beta)$, exactly one of those is also a quardratic residue modulo $N$, i.e., an element of $\mathbb{QR}_N$ (this is not hard to prove).

Consequently, $BW_N$ gives a bijection from $\mathbb{QR}_N$ to $\mathbb{QR}_N$ and this is what is meant by "$BW_N$ is a permutation over the squares mod $N$".

Does that mean its a trapdoor permutation? Or what might it mean?

The factorization of $N$, i.e., the knowledge of $p$ and $q$, is the trapdoor of this permutation and is required to efficiently compute the inverse.

share|improve this answer

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 $p=2p'+1$ for $p'=2p''+1$. So $p=4p''+3$. Consequently the same for q.

share|improve this answer
The word permutation is what is confusing me the most. I know what a quadratic residue is, but I was unsure what it meant by "permutation over the squares". If it just meant that the function $BW_N$ was just a trapdoor function if we focused our attention to the domain and codomain of quadratic residues. Is that what it means? I think I might be confused about the terms they used (and specifically what a trapdoor permutation mean, isn't it just a trapdoor function? or how is it different?). Thanks for your help btw! :) – Pinocchio Jan 21 '14 at 8:14
Suppose that you have a set of numbers $S$ in a specific order.Then randomly rearranging the elements means that you permute the elements.Now in a trapdoor permutation you have a key. Once you know the key you can reinverse the set in its original form.Suppose i.e that i permute by shifting one element at my right.This is the key.Now in your case the trapdoor of the permutation is the integer factorization problem. – curious Jan 21 '14 at 8:17

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.