Let $Z(N)$ denote the minimum number of zeros in $[0,2π]$ that a cosine polynomial of the form $$f_A(t)=\sum_{n\in A}\cos nt$$ can have when $A$ is a finite set of non-negative integers of size $|A|=N$. It is an old problem of Littlewood to determine $Z(N)$. In this paper, we obtain the lower bound $Z(N)\geqslant (\log\log N)^{(1+o(1))}$ which exponentially improves on the previous best bounds of the form $Z(N)\geqslant (\log\log\log N)^c$ due to Erdélyi and Sahasrabudhe.