1
$\begingroup$

I am currently reading a paper from CRYPTO, which is a top conference in cryptology. In the paper, the authors use a thereom like the one given below without a rigorous proof:

the probability that $Rank(A)\neq n$ is upper bounded by $1/p$, where $p$ is a prime, $n$ is an integer, $\mathbb{Z}_p$ is a ring of integers modulo $p$, and $A$ is a square matrix which is chosen from $\mathbb{Z}_p^{n\times n}$ uniformly at random.

I am curious how to rigorously prove the thereom. I would appreciate it if anyone could teach me how.

$\endgroup$
3
  • $\begingroup$ A good question should always link the paper(s) that you read. How one can know that you miswrote or something else? $\endgroup$
    – kelalaka
    Jun 3 '20 at 8:36
  • $\begingroup$ @Sam Jaques Thank you for giving an answer. To me, the answer looks flawless. $\endgroup$
    – Sarasa
    Jun 4 '20 at 2:28
  • $\begingroup$ The paper is (Hierarchical) Identity-Based Encryption from Affine Message Authentication by Blazy, Kiltz and Pan in CRYPTO2014. Actually, what I am reading is not the conference paper, but its full version uploaded on ePrint archive (eprint.iacr.org/2014/581). In the proof of Lemma A.12 in appendix, they used the theorem whom I earlier mentioned. Since either the lemma or the proof of the lemma is omitted in the conference paper, its correctness must have not been refereed in the reviewing process for CRYPTO. $\endgroup$
    – Sarasa
    Jun 4 '20 at 5:14
2
$\begingroup$

I'll try to show the probability that the matrix has rank equal to $n$. Two important facts, since $\mathbb{Z}_p$ is a field and not just a ring:

  1. Each column of the matrix can be considered as a random vector drawn from a set of an $n$-dimensional vector space over $\mathbb{Z}_p$, which has $p^n$ vectors.
  2. The number of vectors in a $k$-dimensional subspace will be $p^k$.

So, model the construction of the matrix as drawing $n$ vectors independently at random. For the matrix to have full rank, after the $i$th draw, we need all $i$ vectors to be linearly independent. Assuming the previous $i-1$ vectors are linearly independent, they span a space of dimension $i-1$, so the $i$th vector must be outside of this space. A space of dimension $i-1$ has size $p^{i-1}$, so the probability that a random vector is in that space is $p^{i-1}/p^n$, and we want the opposite to happen, so the probability is: $$1-\frac{p^{i-1}}{p^n}=1-p^{i-1-n}$$ This even holds for the first vector, which will have rank 1 as long as it is not the all-zero vector.

Thus, the total chance of being full-rank will be

$$\left(1-p^{-n}\right)\left(1-p^{-n+1}\right)\dots\left(1-p^{-1}\right)$$

This is less than $1-1/p$, which means its converse (that the matrix's rank does not equal $n$) must be at least $1/p$. Are you sure the paper didn't mention a lower bound?

Alternatively, since $(1-p^{-i})\geq 1-1/p$ for $i\geq i$, we can argue that the probability of a full-rank matrix is lower-bounded by $$\left(1-\frac{1}{p}\right)^{n} \geq 1-\frac{n}{p}$$

and thus $\frac{n}{p}$ an upper bound on the probability that $Rank(A)\neq n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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