You could also apply the voting construction to create a threshold signature. I think that would result in a smaller k (mainly because it avoids sampling negatives) - though the maths would have to be done to be sure.
Edit: apologies, I was mistaken about the branch encoding. Perhaps a trie construct or a mapping between addresses and numbers could improve efficiency.