Yes, and that is the part that does not work when two devices with different app sets share the same account.
One way to reduce that is to split it in two parts: 1) names and versions, 2) dependencies. That way, the difficult part (parsing the dependencies) would be done only for the specific package the user selects for installation or upgrade and only when he choses to do so.
Please note that there is still an information leakage ("Johny is installing package X"), but only to the repository that provides that package and that is unavoidable anyway.