First, there has been followup work to BPR, including a practical PRF and PRG. Here "practical" means extremely fast --- ~5 cycles per byte, (and as small as ~3 for the PRG iirc). This is well within a factor 10 of AES using AES-NI. There are a few caveats to this though:
- The keys are very large
- I believe AVX instructions are used, so some hardware acceleration is used
- Very small parameters are chosen.
These small parameters are such that the LWR/LWE equivalence is no longer known to hold [1], and moreover there's not really any meaningful reduction to a hard lattice problem. Therefore, security/parameters are chosen concretely by analyzing a handful of known attacks. This sounds like it would be of interest to you.
- What is the relation between k, n and m? How large does p and q have to be?
It depends on if you want it to be provably secure or heuristically secure. For provable security, theorem 5.2 of the paper you link seems to give you precisely the relationship that you want. For heuristic security (using smaller parameters), the relevant things to look at are:
- section 4 of the PRF paper, and
- section 3 of the PRG paper.
but they don't give nice inequalities that you might want, because such inequalities aren't known.
Instead, they evaluate a handful of known attacks for particular choices of parameters.
- How would the time taken by the best known algorithm to break the security of this function scale with k, n, and m?
See section 4 of the PRF paper, and section 3 of the PRG paper, where several relevant computations are done.
3.a The output of F is a matrix. What does entropy of a matrix mean?
Strictly speaking, nothing. Entropy is a property of a probability distribution, so the claim would only make sense if one views $F$ not as a matrix, but as a distribution over matrices. To get some idea of what the authors mean, let $q = p_0 p_1$ be a semiprime.
Then, if $A, S_1,\dots S_k$ are distributed such that (with probability 1):
- $A\bmod p_0 \equiv 0$, and
- $S_i\bmod p_1\equiv 0$ for all $i$,
then $F(A, S_1,\dots, S_k) \equiv 0\bmod q$ constantly, so the PRF will be predictable. The restriction to $A, S_i$ being invertible $\bmod q$ stops this particular (potential) issue (and perhaps more).
3.b And, does this statement indicate that F is a one to one function?
No, but it isn't expected to be. We want $F$ to be indistinguishable from a random function. Note that random functions are not 1-1 (you can quantify this via a technique called "PRP-PRF switching", but this isn't particularly relevant).
[1] Note that for most "practical" lattice-based primitives, this is already the case --- for example SABER bases itself on the concrete security of small-moduli MLWR, although its moduli of $2^{13}\approx 8k$ is much larger than the moduli of $q = 257$ that these PRF/PRGs use. This is somewhat relevant, as it has been recently discussed that small-moduli LWR has not been cryptanalyzed particularly well. See this NIST PQC google group thread. Since this thread in ~December people have run some experiments (and not found anything unexpected), but from the thread it seems like people hadn't tried directly cryptanalyzing small-moduli LWR until a month or two ago.
There are some sitautions one can use practical LWR-based primitives and get provably security based on lattice problems, but the only "standard" one I know of this is Sam Kim's (Key Homomorphic) Lattice-based PRF. Hart Montgomery also has a Non-standard version of LWR he can prove security for.
