Proving super-linear lower bounds on the size of circuits computing explicit linear functions $A:{\mathbb {F}}^n \to {\mathbb {F}}^n$ is a fundamental long-standing open problem in circuit complexity. We focus on the case where ${\mathbb {F}}$ is a finite field. The circuit can be either a Boolean circuit or an arithmetic circuit with scalar products and sum gates over ${\mathbb {F}}$.

We extend the notion of natural proofs (Razborov and Rudich, J. Comput. Syst. Sci. 1997) to the context of proving circuit lower bounds for linear functions. Let $L_n = {\mathbb {F}}^{n^2}$ denote the set of all linear functions $A:{\mathbb {F}}^n \to {\mathbb {F}}^n$, represented by their corresponding $n\times n$ matrices over ${\mathbb {F}}$. We say that a lower bound proof for the circuit complexity of a linear function $A:{\mathbb {F}}^n \to {\mathbb {F}}^n$ is natural, if either implicitly or explicitly, the proof defines for every $n$ a subset $C_n \subset L_n$, such that, there exists a polynomial-time recognizable subset $C'_n \subseteq C_n$, such that, $|C'_n| \geq \frac{1}{poly(n)} \cdot |L_n|$ and the lower bound applies for every function $A \in C'_n$. This definition is analogous to the original definition of natural proofs, modified to the study of linear functions $A:{\mathbb {F}}^n \to {\mathbb {F}}^n$, represented by their corresponding $n\times n$ matrices, rather than general Boolean functions, represented by their truth tables.

We observe that recent works on trapdoored matrices, by Vaikuntanathan and Zamir (SODA 2026) and Braverman and Newman (TCC 2025), imply that, assuming (strong but plausible) cryptographic assumptions, natural proofs cannot establish circuit lower bounds higher than $n \cdot polylog(n)$ for linear functions $A:{\mathbb {F}}^n \to {\mathbb {F}}^n$.