Is there no way to codify a negative right, like “The right of the European people to privacy in their communications and security in their records through encryption shall not be infringed?” Negative rights reserved to the people should be more important than positive laws granting power to the government.
In some ways yes but we've already seen with covid that governments are happy to behave unconstitutionally even when it's clear they will eventually lose in court - by then their targets have already been dragged through the mud.
Yes; they could amend the definitely-not-a-constitution (for branding/eurosceptic-appeasement reasons, the EU constitution was rebranded as the Lisbon treaty before adoption). Arguably such a right may exist already and this legislation might find itself on a collision course with the ECJ if it passed (notably the ECJ nuked _another_ intrusive law, back in the day: https://en.wikipedia.org/wiki/Data_Retention_Directive).