Frequent patterns mining is an important task for data mining. Nevertheless, mining concise crucial patterns is more promising than frequent patterns over data streams, since crucial patterns can avoid redundancy to reduce storage space and extract lossless information from frequent patterns. Nevertheless, mining crucial patterns from data streams which aggregate information from individuals is more likely to reveal privacy than static scenarios, because the background knowledge of the release at adjacent time instances can enhance the adversary's inferential ability. This study points out the problems and principles of privacy leakage over mining crucial patterns in data streams, and proposes a differentially private crucial patterns mining algorithm which designs a two-phase mechanism at every timestamp. Specifically, the two-phase mechanism includes the dissimilarity calculation phase and the noise-mining phase, which considers not only the tradeoff between privacy and utility but also the tradeoff between mining time and maintenance cost. To improve data utility over successive releases in streams, the dissimilarity is computed to decide to return either low noisy statistic or accurately approximated statistic in the first phase. When the low noisy statistic needs to be turned, the algorithm goes into the noise-mining phase. In the noise-mining phase, crucial pattern candidate set with a judgment query set is firstly identified, and then random noise drawn from the Laplace distribution to their supports are added to obtain the noisy supports. Finally, strict theoretical analysis and extensive experiments are provided to confirm the effectiveness and efficiency of our algorithm.