Proof of the security of the modified sphinx mixnet header format in the SPORES protocol : A verifiably secure onion routing protocol with indistinguishable replies

Sammanfattning: The internet inherently makes secret communication difficult, the entire basis of the IP-protocol is that the routers handling the packets need to know who is receiving the packet. However, there are many reasons why someone would want to communicate in secret. One possible solution is that of onion-routing. Onion routing has however been difficult to formalise, and even the most promising model from Camenisch and Lysyanskaya had issues with regards to their sufficient properties. They are now believed to have been fixed, but no protocol (at the time of writing) has been proven to fulfil these properties while also allowing for responses, since the model does not require that one allows responses. This means that most existing onion-routing protocols either does not have proper mathematical security guarantees, or can not be used for anonymous two way communication. This work presents a protocol which satisfies the model, providing mathematical guarantees to the security of the protocol, and allows for indistinguishable replies. This is achieved by adapting the header format Sphinx with an idea from Sphinxes to split each onion into two. However I also find that indistinguishable replies are not enough to protect against certain adversaries.