This questions has been debated, in one form or another, for some time as the "key escrow" problem. There are fundamental problems with the architecture of giving a third party access to secured data. These are invariant to how you implement the cryptography. See this article for example.
I am interpreting the question as how to provide third party access to secured data: the debate about whether this actually corresponds to the current situation with the French government I'm considering tangential; and there are unsolvable risks with doing this by the nature of the problem. So consider this answer as making the best of a bad situation.
A set of requirements could be:
- The server has access to all the records
- The government can be granted access, but only to specific records
- It should be fairly efficient to register a new user
- It should be very efficient to authenticate a user
- It doesn't necessarily have to be that efficient to recover a record
There is actually a very nice solution to this problem with very modern cryptographic techniques, called functional encryption, however it is not efficient. With these types of schemes, the server can hold a master private key that allows them to decrypt any record and they can create a new private key that can only be used to decrypt specific records. This solves (1), (2) and (5), conflicts with (3) and does not provide (4).
In order to provide (4), I'd suggest a hybrid system where whatever existing password-based authentication system is being used is continued to be used to do (4), and it is augmented with an encryption of the user's record (including the password). If the record is provided to the government, once it has recovered the password, it can compare ensure it is the same password being used to authenticate the user.
An alternative to using function encryption would be for the server to encrypt the record with an appropriate encryption scheme that allows them to generate a "zero-knowledge" proof of what the record is each time the government asks for a record (instead of giving the private key). The proof could be encrypted during transit to the government (and one could even use a "designated verifier" proof to stop the government from sharing the proof with others).
None of these solutions will ever solve the fact that the government needs to be trusted not to abuse its authority, since protecting against this conflicts with the definition of the problem we are trying to "solve."