Return to Answer

This can be achieved in 13 moves (25 half-moves), and likely fewer:

[FEN ""]
1. d3 g6 2. c4 Bh6 3. f4 f6 (3... f5 4. Kd2 Bxf4+ 5. Kc2 Kf7 6. Na3 Kf6 7. Kb1 Kg5 8. Qc2 Bxc1 9. c5 Kf4 10. c6 Ke3 11. cxb7 Kf2 12. e4+ Ke1 13. h4 Bxb2 14. Kxb2#) 4. f5 Kf7 5. fxg6+ Kxg6 6. Na3 Bxc1 7. Qb3 (7. Qc2 Bxb2) 7... Bxb2 8. Kd2 Kg5 9. Kc2 Kf4 10. Kb1 Ke3 11. Qc2 Kf2 12. e4+ Ke1 13. Kxb2#

 [FEN ""]
 1. e4 Nf6 2. Qf3 g6 3. Na3 Bh6 4. b3 Kf8 5. Rb1 Nxe4 6. c4 Nxd2 7. Kd1 Nxb1 8. Kc2 f5 9. Bb2 e5 10. Ba1 e4 11. Kb2 Kg7 12. Qxf5 Qg8 13. Kxb1#
 
That's 13 moves, and definitely not optimal.

[FEN ""]
1. e4 Nf6 2. Qf3 g6 3. Na3 Bh6 4. b3 Kf8 5. Rb1 Nxe4 6. c4 Nxd2 7. Kd1 Nxb1 8. Kc2 f5 9. Bb2 e5 10. Ba1 e4 11. Kb2 Kg7 12. Qxf5 Qg8 13. Kxb1#

That's 13 moves, and definitely not optimal.

Kb1xb2

By having the king start on the first rank, we ensure the only discovered check is a rook along the same rank, so black's king must cover the whole board.

Along these lines:

rnbq2nr/pppppp1p/8/8/2P1P3/3P4/PbQ3PP/RK2kBNR w KQ - 0 1

White king has to move to an inconvenient square, moving several pieces out of the way. Black king has to move all the way from 8th rank to probably d2. White rook has to get to a2 most likely. Black and white also have to set up other pieces to enclose d2. And black also has to get some other piece all the way to b1 in order to be captured.

I'm picturing a final board something like this, where the black king captures the b knight, the black knight captures the a rook, and the pawn at e4 was previously at e2, allowing the king in past the bishop.

rnbq1b1r/pppp1ppp/4p3/8/2PBP3/6N1/QK1kBP1P/1n5R w - - 0 1

Absolute minimum moves required for:

• Black: 7 + 4 + 1 (king, knight, pawn) [maybe better with bishop instead of knight)
• White: 4 for king, 2 for queen, and who knows how many pawn and minor pieces :)

Although a very different way of achieving that same move might look like this:

rnq3bk/ppp4p/3p2p1/5p2/P3p3/1P6/RKPPPPPP/Bn1Q1BNR w q - 0 1

I now realise that Black's king could be mated by a bishop on a1, like this:

1. e4 Nf6 2. Qf3 g6 3. Na3 Bh6 4. b3 Kf8 5. Rb1 Nxe4 6. c4 Nxd2 7. Kd1 Nxb1 8. Kc2 f5 9. Bb2 e5 10. Ba1 e4 11. Kb2 Kg7 12. Qxf5 Qg8 13. Kxb1#

 [FEN ""]
 1. e4 Nf6 2. Qf3 g6 3. Na3 Bh6 4. b3 Kf8 5. Rb1 Nxe4 6. c4 Nxd2 7. Kd1 Nxb1 8. Kc2 f5 9. Bb2 e5 10. Ba1 e4 11. Kb2 Kg7 12. Qxf5 Qg8 13. Kxb1#

That's 13 moves, and definitely not optimal.