We initiate a systematic study of linear sketching over F 2 . For a given Boolean function f : 0 1 n 0 1 a randomized F 2 -sketch is a distribution over d n matrices with elements over F 2 such that x suffices for computing f ( x ) with high probability. We study a connection between F 2 -sketching and a two-player one-way communication game for the corresponding XOR-function. Our results show that this communication game characterizes F 2 -sketching under the uniform distribution (up to dependence on error). Implications of this result include: 1) a composition theorem for F 2 -sketching complexity of a recursive majority function, 2) a tight relationship between F 2 -sketching complexity and Fourier sparsity, 3) lower bounds for a certain subclass of symmetric functions. We also fully resolve a conjecture of Montanaro and Osborne regarding one-way communication complexity of linear threshold functions by designing an F 2 -sketch of optimal size. Furthermore, we show that (non-uniform) streaming algorithms that have to process random updates over F 2 can be constructed as F 2 -sketches for the uniform distribution with only a minor loss. In contrast with the previous work of Li, Nguyen and Woodruff (STOC'14) who show an analogous result for linear sketches over integers in the adversarial setting our result doesn't require the stream length to be triply exponential in n and holds for streams of length O ( n ) constructed through uniformly random updates. Finally, we state a conjecture that asks whether optimal one-way communication protocols for XOR-functions can be constructed as F 2 -sketches with only a small loss.