For both Apple and Google's phones it wouldn't be hard to allow users to securely add keys of other stores or indivual software makers without requiring one to root his phone (aka destroy the security).

You'd just have to give several huge, clear warnings of what that means before allowing it.

And, by the way, security? Come on, if they really cared about the security/privacy of their users the permissions' systems would not be made of those huge blankets that are more like websites' cookie banners than real useable security controls.