A Cryptographic Moving-Knife Cake-Cutting Protocol

Yoshifumi Manabe
(NTT)
Tatsuaki Okamoto
(NTT)

This paper proposes a cake-cutting protocol using cryptography when the cake is a heterogeneous good that is represented by an interval on a real line. Although the Dubins-Spanier moving-knife protocol with one knife achieves simple fairness, all players must execute the protocol synchronously. Thus, the protocol cannot be executed on asynchronous networks such as the Internet. We show that the moving-knife protocol can be executed asynchronously by a discrete protocol using a secure auction protocol. The number of cuts is n-1 where n is the number of players, which is the minimum.

In Johannes Reich and Bernd Finkbeiner: Proceedings Second International Workshop on Interactions, Games and Protocols (IWIGP 2012), Tallinn, Estonia, 25th March 2012, Electronic Proceedings in Theoretical Computer Science 78, pp. 15–23.
Published: 20th February 2012.

ArXived at: http://dx.doi.org/10.4204/EPTCS.78.2 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org