Is there a solution to the trust problem when installing apps?

Depends on your threat model. If you are concerned about nation state interference, no there's no solution. The power disparity is just too great. Render unto Caesar, etc.

My solution is to try to spread my exposure between a small number of uncorrelated entities that are as trustworthy as possible. For example, here's an app I publish: https://akkartik.itch.io/carousel

It depends on an app published by https://love2d.org (not the Android app store), which in turn depends on Lua. Both stages are independent reputable projects publishing fairly parsimonious source code anyone can look at.

This is likely still exposed to nation states. But it feels as good as things can get.

I'm not sure I understand the Google Play store argument. If you're running on Android,Google already supplied you the OS, which would be a better target than some app.

So given that you are using Google code already, the "most trustworthy" source becomes the Play Store.

But Google does not write that code, and frankly given the volume of submissions (and obvious problems) by "most trustworth" I don't mean you should trust it.

Or to put it another way, once you start using code, written by someone else, the -source- of the code is irrelevant. It should not be trusted.

Which is true for your phone in general. It is not a "trustworthy" device.and you should treat it as such.

I'm an old man, here's an old man answer, that might seem silly, but gives you a direction you might be able to pursue with more modern hardware, let's say a USB bootable computer. (It's too bad you can't truly write-protect a USB drive, though)

== old man answer begins ==

The most secure model of computing, that I'm aware of, is to use a non-networked computer without any permanent mass storage, booting off of "trusted" read-only media. Such as an IBM PC/XT with dual Floppy disks.

We used to buy software on "Shareware" diskettes at user groups, coming home with dozens of disks of totally untrusted software, then spend the next month trying things out, and repeating this every month, for years.

We did it in almost perfect safety, because we had a simple way to copy our boot disks, and our data disks, that was proven and reliable, and easy to grok.

You ALWAYS knew what disks were at risk, because they were the ones without write-protect tabs on them in the floppy drive.

If you had any sense at all, you had multiple copies of your critical data and boot disks. You could always recover to a known state in a few minutes time, no matter what. The hardware didn't have any place large enough to store virii, etc.

== old man answer ends ==

If you have to be super-paranoid, get a stack of USB disks, and a "known good" boot disk (thumbdrive), and a computer that can boot from USB with no persistent storage. Make a stack of copies of your boot media when you get your configuration settled. Use them only once, like pens used in public during Covid.

Use a second disk for your data.

Treat them all like we used to treat floppy disks, but with the additional caveat that you CAN NOT EVER trust any "write protection" of USB sticks.

As for OS choice, Edward Snowden used to recommend Tails[1] as an OS boot choice, I'm not sure if that's still the case.

[1] https://tails.net/about/index.en.html

IMO this isn't a real problem most users face. As developers we can be hypersensitive about permissions and such, but most regular people... just don't care. They value convenience over security. Apple's solution for this was to better vet incoming apps. Google's OEM business model meant that wasn't practical, so we just saw a lot of malware instead, but nonetheless Android is everywhere and popular across the world.

Eventually we got fine-grained permissions on both systems, but it's still just popups that users click through unthinkingly.

I don't know that there is a magical solution to this. As with most of human interaction and commerce, the solution isn't perfect transparency and trust, it's the threat of later retribution -- by chargeback, by lawsuit, by intimidation, whatever -- that really keeps bad actors in check.

When you download a Meta app, there's no way to audit its entire source code. The deal with the devil you make there is that Meta is going to be somewhat responsible with your stuff. Of course, they're not. And when they're caught, they pay some minor fine and move on. And yet billions of people still use their apps. It's just not a big deal to most people.

And developers aren't magically immune to this either. NPM is wildly popular and utterly insecure. Most of the web is built on someone else's unvetted source code, itself built on ten other organizations' unvetted source code, all the way down.

The trust systems we have are more marketing devices than protective. They give users the illusion of security without sacrificing these companies' profit. The most simple fix to most of this is to simply disable internet access for apps by default, and then optionally let users examine plaintext packets prior to transmission (with the OS encrypting that same packet before sending it out, if needed). But they don't want that because that'd be the end of ad dollars and tracking.

No part of your system is secure or private. They're designed in huge profit-seeking corporations with embedded government agents. They're manufactured with parts from fifty different countries, each with its own levels of corruption and government interference. They're made by engineers who mostly just focus on their little spheres of concern and go home afterward. These systems are too big, too complex, for anyone to fully secure, so it's always a losing arms race against orgs like the NSO Group.

So, given that these aren't really secure to begin with, can't really be secured even with extensive effort and billions of dollars, and can't be proven secure even if they were, and is actively made less secure because the companies that make them have a vested interest in lowering your privacy and security for ad dollars... there's no way to win. You just decide it's not a big enough deal, accept it, and use it anyway. Or don't, and become one of those people who insist on using third-party hardware and your own Signal build that none of your friends bother texting anymore. But most people just don't care, and never will...