We can easily see that the signature must be at least as large as the message. Otherwise, it would be impossible to verify any arbitrary single bit. Signing a message with
n bits must necessarily must involve a signature that can validate
n unrelated 1 bit message subsets.
However, if we assume Bob and Mallory are given copies of the message, there may be opportunities where computations are done over the entire message, but not transmitting the entire message. This could help reduce the signature size.
You may be interested in Merkle Trees. I don't know if they are exactly what you are looking for, but they provide some interesting approaches for proving things about contiguous subsets of messages. In a worst case scenario, you would have to send Victor effectively the entire Merkle tree. However, for revealing small fractions of the tree, you may be able to keep a large portion of the information out of the message. You only have to reveal the sibling leaves for every bit you send, which would not reveal the whole message, while still authenticating it as a subset.
There are a few cryptocurrency algorithms out there which leverage this for micropayments. Alice generates a list of coins, puts them in a Merkle tree, and then gets the top of the tree signed by Victor. She then gives this signed top to Bob, who authenticates it with Victor (online or offline). After this point, Alice can send Bob a coin simply by revealing it, and all of the sibling internal nodes required to prove it was part of her list of coins. These algorithms, of course, strive to be efficient. They expose the coins in order, so they only ever have to reveal contiguous subsets, not the arbitrary ones you might need. This keeps the message traffic down to
O(n log m) for
n coins transferred out of
m coins minted.
Another approach would be to carefully select the message that Alice constructs to have the properties you desire, rather than being an arbitrary message. Zero Knowledge Proofs are full of clever situations where Bob has to demonstrate information about a message while carefully controlling how much information is transmitted.
One thing you should definitely watch out for is whether there is any issue with Eve computing the message from just
S and the message traffic between Bob and Victor. The content of the message could start getting leaked. If you know the internal node over a group of
n bytes, you can brute force those
n bytes, recovering a part of the message that hadn't been revealed by Bob. But if the goal is simply to provide subsets of a verified message to Victor, that may be acceptable.