When people who distrust each other want to securely cooperate, they can do so with the help of cryptographic 'commitment schemes'. PhD student Max Fillinger from CWI studied a specific kind of such schemes whose security is based on the laws of physics and the speed of light, so-called relativistic commitment schemes. He presents new methods for designing and analyzing them in his PhD thesis 'Bit-Commitments: Classical, Quantum and Non-Signaling', which he defends at the Mathematical Institute of Leiden University on 19 March.
Fillinger explains: "A commitment scheme is a cryptographic protocol that can solve dilemmas like the following one. Suppose Alice wants to convince Bob of her ability to predict the stock market. She does not want to give him free advice by revealing her predictions ahead of time, but making her predictions known after they came true is clearly unconvincing. If there is a third party, Charlie, that both Alice and Bob trust, Alice can give the message to Charlie for safekeeping. Commitment schemes remove the need for such a third party".
The PhD student continues: "Relativistic commitment schemes do not rely on computational hardness assumptions but on the fact that information does not travel faster than the speed of light. A shortcoming, though, is that they only remain secure for a limited amount of time. One of the main results of my thesis is a composition theorem that gives rise to a new design principle, showing that multiple schemes can be chained together in a particular way to create a new scheme that remains secure for a much longer time".
As a side-result, he proved that a specific relativistic commitment scheme that was proposed in 2015 offers much stronger security than was originally thought: rather than offering security for only a few milliseconds, Fillinger's works shows that it remains secure for a practically unlimited time. Fillinger’s promotor Serge Fehr (CWI and UL) says: "The results give new insight into an area of theoretical cryptography that links information security with physics". Fillinger adds: "And, next to this, they help with proof-of-concept implementations that could move the theory closer to practice".
This research was carried out at the Cryptology research group of Centrum Wiskunde & Informatica (CWI) in collaboration with Serge Fehr (CWI and UL) and supported by a NWO Free Competition grant. Some of the results presented in the thesis were published at CRYPTO 2015 and EUROCRYPT 2016.
More information:
- CWI’s Cryptology research group
- Promotor Prof. Serge Fehr at CWI
- Personal homepage of Max Fillinger (who is now working at Fox-IT)
- The PhD defence takes place at 19 March 2019 from 10-11 AM in the Academy Building of Leiden University, Rapenburg 73, Leiden
