Best alien communication protocol?
Your first question is the topic of Brendan Juba's PhD thesis on Universal Semantic Communication. You should take a look at it, as well as some of the papers on his website.

As for your second question, you might want to read about zero-knowledge proofs.