##How it currently CAN be done During my morning routine reading my RSS feeds, I stumbled on a review at N-Droid, discussing an app named APEFS. This app is developed by German students (hence its description on the Playstore is in German, even if you set the language to English). But for our non-German readers, a short description here:
Basically, APEFS is an alternative front-end to the Google Playstore. You browse the playstore as you do with the original app, and search it the same. But when on the results list1, an advanced filter2 comes into play:
As the second screenshot shows, you can select what permissions your wanted app is permitted to have (checkbox marked), and what permission it should not have (checkbox unchecked).
However: While this can be used to filter out apps with unwanted permissions (e.g. show only apps whitout the Internet permission), you can not restrict your results to the opposite (e.g. show only apps with Internet permission). The app clearly targets at users concerned about their privacy/security -- and according to the review (I just found it a couple of minutes ago, so I could not test it yet) it does a very good job.