polygraph APK is much easier
An app (e.g. APK file download) is the only way. (The other way would be a built-in feature in the OS, but that doesn't exist (yet?). (You could try posting a feature suggestion in the Google issue tracker if it hasn't been posted there by someone else already.))
polygraph it seems RethinkDNS might indeed be the way.
I think this app is a specific service rather than letting you use any server you want, so that's why I didn't suggest it above. But it might be worth to try.
polygraph But if one is compelled to return to Google in order to use certain apps, how does the deliberately ungoogled Graphene protect from that?
Firstly, GrapheneOS makes it so the OS never tries to use Google services for any OS functionality even when Google Play is installed. It's really decoupled from the OS on GrapheneOS. There's many people I've seen on this forum who claim they don't have Google Play and they're doing okay without it.
Secondly, I don't recommend this option but you can always try installing Google Play in a separate user profile or inside Private Space. GrapheneOS makes improvements to user profiles:
https://grapheneos.org/features#improved-user-profiles
Apps are sandboxed, but visibility and communication between apps is still permitted. User profiles and Private Space (which is a special user profile) are the current way to segregate apps so they shouldn't be able to communicate with each other. There's still some leaks acknowledged (e.g. the loopback interface) allowing for apps to speak across user profiles, and GrapheneOS is planning both to fix all leaks and to somehow address the segregation problem without requiring use of different user profiles; they've termed this future feature App Communication Scopes but have paused work on this feature temporarily due to various issues related to this feature and because of the mountains of work they have due to external factors like Google and the French law enforcement. App Communication Scopes is one of the most commonly requested feature. Feel free to look it up.
Multiple user profiles have various non-obvious oddities. I recommend having only a single user profile.
Thirdly, in the recent versions, GrapheneOS made it possible to use certain Google-dependent apps without Google Play. They also said they intend to expand this practice. See for example:
https://grapheneos.org/releases#:~:text=2025102300%20release:-,Sandboxed,integration
https://grapheneos.org/releases#:~:text=we%20want%20to%20expand,without%20Play%20services%20installed
polygraph Please correct me, if I am wrong, but I think using Google Play Store requires to register a Google account, i.e. sharing one's personal data with Google. I am reading some people recommend using a "fake account" but registering with Google is not possible without a mobile phone number, which is not anonymous.
This is one of the most commonly repeated complaints on this forum, and people commonly say it's not true and that you can use a public cafe's Wi-Fi or something. Look it up.
polygraph I read about that in the other thread you linked but their page says "Currently in alpha", which doesn't sound "well-tested and secure", right? In that sense, it is not a solution (yet), so what should one do?
This is a healthy practice to beware of alpha software. With that said, Accrescent is already recommended for use and is already working. Due to being small and lacking resources, they've had a few weeks recently where updates were blocked through the app store, but they fixed it. For now, I can recommend Accrescent.
Note that the labeling of versions as “alpha” or whatever is subjective and up to the software author to decide. Nothing prevents them from claiming their solid software is in alpha state. I've seen some software authors doing that, actually. I avoid any other kind of alpha or beta software because I want a bug-free experience; Accrescent is the only exception I can think of.
polygraph When you write "ADB is incredibly insecure and unsafe", I read: the ADB software itself is insecure and unsafe.
USB debugging can be dangerouns - of course, that's not news. It still doesn't mean ADB itself is what you say it is.
The linked post talked about attack surface. (Edit: actually not, my bad, but the GrapheneOS team has warned about the attack surface of ADB being huge in other places.) Do you know what attack surface is?
Furthermore, ADB allows immense control over the device, control that can do things that shouldn't be possible on a normal device and aren't tested for. If you want security or stability, avoid it.