To have something that is genuinely private and would qualify for listing in the app store, options are pretty limited. I don't think they allow developers to use onion services or anything like that. You could host the server in other countries, but even in hostile countries, it's not a leap of logic to assume the NSA would have an easy time getting in there all without the worry of that pesky "legal" thing.

Is there a reason why it can't be a PWA?