You can't get there from here

Secrets

T needs to prepare the encrypted list of air routes
He has essentially two choices

He can make up an alias list and encrypt the correct route information
If V flips heads, T reveals all the encryption keys

Aix ai500 Brussels br558

Cannes ca426 Dayton da573

Erie er054 Panang pa910

Peoria pe379 Perth pe442

Philadelphia ph160 Portland po839

ai500 br558 ai500 po839 ai500 er054

br558 ca426 br558 da573 br558 ph160

ca426 da573 ca426 pa910 da573 er054

da573 pe379 er054 pe442 pa910 po839

pe379 po839 pe379 ph160 pe442 ph160

Everything looks good
- V is fooled!

But if V flips tails, T must reveal an itinerary of the right length
He can't do this, because he doesn't know one
- And he can't find one because the problem is NP-complete