Minimum Number of People Such That No Two People Know the Same Two People
The comment of Carlos actually gives an upper bound. There is a much better (and almost tight) upper bound for $k+1$ being a prime number: $n=k(k+1)$. The construction is a classical result in extremal graph theory, namely $C_4$-free $k$-regular graphs, which can be found here.

The vertices are labeled with $(a,b)$ where $1\leq a\leq k, 0\leq b\leq k$. Two vertices $(a,b)$ and $(c,d)$ are linked if and only if $ac\equiv b+d\mod (k+1)$.
Notice that for any given pair $(a,b)$ the number of solutions $(c,d)$ is exactly $k$, so the graph is $k$-regular. To see the graph is $C_4$-free, consider the following congruence equations
$$\left\{ \begin{array}{ll}ax\equiv b+y\mod (k+1)\\ cx\equiv d+y\mod (k+1)\end{array} \right.$$
Since these imply $(a-c)x\equiv b-d \mod (k+1)$, and $k+1$ is prime, there is at most one solution whenever $(a,b)\neq (c,d)$, so the graph contains no $4$-cycle.

There are many other constructions among this context, for instance, when $k-1$ is a prime power there is a construction of size $n=2(k^2-k+1)$ with bipartite incidence graph (See, e.g., here).