Can I store LEGO in negative (minus) Celsius? I've found this question: How can I store LEGO bricks to prevent damage? and the answers don't tell, what happens below 0°C.
Can I store unopened LEGO boxes where temperature can go down until even -15, -20°C?
Generally yes, as long as:


there are no electronics inside (like Power Functions, Mindstorms, etc.)
the temperature stays below freezing
you allow plenty of time in dry environment to thaw out


No, if the temperature rides up and down and you want to keep the box and paper booklet intact - it will draw moisture with each thaw cycle. 

No if electronics, especially with integrated lithium batteries, are involved (but even without batteries it's not good to freeze electronic components).

LEGO is made of ABS and sometimes some other general purpose plastics. They become brittle when cold, but go back to normal once temperature returns to room levels.