=Michael B Greenwald Drawing names from two hats?
Interesting approach! Of course one glitch is that there must be as many reds as greens, so this only works for even N (and, unfortunately, my motivating application has N=5...<;-).
...that doesn't seem so terrible.
Agreed, in practice. But still, from a theoretical, esthetic, point of view, it's unfortunate that it doesn't generate all derangements with equal probability (eg all the cycles are even). It seems strange that random secret derangements would be so much harder to generate than random secret permutations. Perhaps this multi-hat idea can be modified to work uniformly somehow? Or, perhaps there's some kind of cryptographic protocol, using sealed envelopes or the like? (avoiding the omniscient computer smells like eliminating key escrow...)