Poker is arguably one of the most popular card games in the world, both in casinos and on the internet. Online poker has become increasingly popular after a boom in the early 2000s, fueling a growing market with revenues estimated in the tens of billions of dollars. However, the current model of online gambling forces users to blindly trust the online casinos, who could easily rig games or suffer attacks from disgruntled employees who aim to make easy money. In fact, this state of affairs not only represents a threat but has resulted in real-world attacks. A clear alternative to using online casinos consists of using cryptographic protocols for securely playing poker over a network without trusting any third party. In fact, constructing such protocols has been a research topic since the early days of modern cryptography. Shamir, Rivest and Adleman proposed the first candidate protocol to this end only a few years after publishing the famous RSA public key encryption scheme. Their seminal effort initiated a long line of research that has produced countless results over the years. However, no cryptographic poker protocol has ever been adopted for real applications, mainly due to the following issues:

1 - Security: The security guarantees of existing poker protocols are not clearly defined, so it is hard to understand the level of security that these protocols actually provide and how reliable they are.

2 - Efficiency: Most of the existing poker protocols rely on costly cryptographic techniques that incur high computational and communication overheads, which in the real world result in boring games with long delays.

3 - Financial considerations: Previous poker protocols could not ensure that winners received their financial rewards, even though classic cryptographic techniques could ensure that a game of poker was played honestly (i.e. without allowing players to cheat or learn each other’s private data).

In a recent paper to be presented at the Financial Cryptography 2018 conference, we construct Kaleidoscope, the first cryptographic poker protocol to address all three issues above. Kaleidoscope is the first protocol to be proven secure according to a comprehensive security model that formally and clearly captures all the properties and guarantees commonly required from a poker protocol. Moreover, Kaleidoscope employs blockchain techniques to ensure that winners receive their rewards and that cheaters are financially penalized. Even though it is mathematically proven to achieve security while providing financial rewards and penalty enforcements, Kaleidoscope achieves very high efficiency in comparison to existing solutions (which have not been formally proven secure).

The first step in designing Kaleidoscope was formally defining the security guarantees that a poker protocol should achieve. Since such formal definitions are missing from current literature, we provide the first security definitions for poker in the so-called simulation paradigm, which is the gold standard for cryptographic protocol security. Our security definitions take into consideration all phases of a poker game, modeling the security guarantees obtained for each of them and the conditions under which they hold. Namely, we model security against very powerful adversaries who can attack all but one player. This worst case scenario also captures the case where many players in a game collude in order to cheat against one single player.

With a proper formal model in place, we developed Kaleidoscope, a highly efficient protocol that can be proven to realize our security definitions. Our protocol builds on cutting-edge zero knowledge proofs of shuffle correctness and is carefully crafted to achieve the best possible efficiency in terms of computation and communication. In fact, as shown in an upcoming work, Kaleidoscope achieves high security guarantees while requiring three times less computation and eight times less communication than the best previous protocols (without formal security guarantees).

Another important feature of Kaleidoscope is that it ensures that winners will receive their rewards, and that cheaters will be financially penalized as well as kicked out of the game. The basic idea is that, before a game starts all players send to a smart contract the funds they will be using for betting and an amount of "collateral" funds. At the end of the game, the smart contract ensures that the betting funds are distributed to the players according to the outcome of the game and that the collateral funds are returned. In case a player is caught cheating (which is ensured by our protocol), the smart contract confiscates the cheater’s collateral funds and distributes those among the honest players as compensation. Moreover, we show that the communication with the smart contract and the on-chain storage requirements are minimal.

Although Kaleidoscope successfully addresses the three issues described above in the context of poker protocols, it can only be used to play poker games. There is a false common sense notion that poker protocols can be used for playing any other card games, which would actually lead to serious security issues. However, in the case of Kaleidoscope we were able to extend our formal security model, protocol and proofs to general card games. In doing so, we have obtained Royale, a protocol that can be securely used to play any card game with the same efficiency as Kaleidoscope. We will be describing Royale’s features and techniques in an upcoming series of videos and blog posts.

It is well known that randomness is a fundamental resource for secure cryptographic schemes. All common encryption and authentication schemes are only as secure as their randomness sources are good. Using a poor randomness source can basically render insecure every cryptographic scheme that would otherwise be secure. In many cases, it is sufficient to have a trustworthy local source of fresh randomness (e.g. your operating system’s randomness pool or a Random Number Generator (RNG) embedded in your CPU). However, in many distributed applications, it is necessary to use a publicly accessible source of randomness that allows users (and external observers) to make sure they are all getting the same random values. With such applications in mind, in 1983 Michael Rabin introduced the concept of a randomness beacon, a publicly accessible entity that provides a periodically refreshed random value to its clients. More recently, NIST, the National Institute of Standards and Technology in the United States, started offering a randomness beacon service that derives its randomness from quantum physical processes.

When users are willing to trust a centralised randomness beacon they can simply choose one of them to perform this role or use a publicly available beacon, such as the one from NIST. However, standard randomness beacons provide no means for users to verify that the output values are indeed random and not skewed in a way that gives an advantage to an attacker.

As we know, cryptographic schemes have suffered both from poor implementations and from governmental agencies (e.g. the NSA) that actively work to undermine existing and future standards. In this context, a centralised randomness beacon could be providing bad randomness because of simple implementation mistake or in order to do the bidding of third party attacker who has undermined the central randomness generator or simply presented the people running the service with a subpoena that compels them to do so.

Using a coin tossing protocol (a concept also introduced by Rabin in 1981) is an obvious approach to (partially) solve this problem. Coin tossing allows several users to come together and generate an output that is guaranteed to be uniformly random without having to trust each other or any third party.

In a coin tossing protocol, good randomness is obtained if at least one of the parties is honest. If you run a coin tossing among many servers, somebody who trusts at least one of the servers can be assured that the output is truly random. In many applications (such as cryptocurrencies) we assume that at least half of all parties are honest by design.

Even though using coin tossing protocols solves the trust problem, it still does not make it any easier to ensure that all users will receive the random output. For example, a user with a faulty internet connection or an attacker who wants to mount a Denial-of-Service attack against the protocol (and consequently the application using the final randomness) can simply abort (i.e. stop sending protocol messages) before the output is obtained, keeping all the other users from receiving randomness. In fact, a malicious user can do even worse, he can execute the protocol up to the point where he learns the random output but still not send the final message that would enable the other users to also learn this output.

Tal Rabin and Ben-Or introduced a classical method for making sure all users receive the proper protocol output – assuming at least a majority of them is honest – in a seminal paper in 1989. The main idea is to use "secret sharing" to split each user’s input into "shares" that do not reveal any information about the input by themselves but allow for total recovery of the input if a sufficient number of them are put together. If each user is given a share of every other user’s input – such that the inputs can be recovered if more than 50% of the shares are pooled – malicious users still cannot learn anything because we assume that more than 50% of the users are honest. However, if a malicious user aborts the protocol at some point, the honest users can pool their shares to recover the malicious user’s input and finish the protocol by themselves.

This general approach can be used to make sure that all the users running a coin tossing protocol will receive the final random value. However, this still does not allow users and external observers to make sure that the output is being generated correctly. In order to do that, the users must use a kind of secret sharing that is publicly verifiable, meaning that anyone can make sure that the shares of inputs are correctly generated. This prevents malicious users from posting invalid shares and then aborting in such a way that the honest users cannot reconstruct their inputs. This approach has been used for generating publicly verifiable randomness in the Ouroboros Proof-of-Stake based, permissionless consensus protocol and for constructing a stand-alone randomness beacon in a paper by Syta et al. that will be presented at the IEEE Symposium on Security and Privacy 2017.

The main ingredient in building randomness beacons through this approach is Publicly Verifiable Secret Sharing (PVSS), a type of secret sharing scheme introduced by Stadler that allows users to split their inputs in shares whose validity can be promptly verified by any third party. Using such schemes, it is possible to construct coin tossing protocols with Guaranteed Output Delivery through the approach of Rabin and Ben-or, meaning that every user is guaranteed to receive the final randomness produced by the protocol. However, the PVSS scheme from Schoenmakers, which until recently was the most efficient PVSS scheme, still requires a number of modular exponentiations that is quadratic in the number of users, meaning that if there are n users running the protocol, verifying the n shares produced by one of them requires O(n^2) exponentiations. Note that this poses serious scalability issues since this quadratic overhead means that the number of expensive modular exponentiations required for verifying n shares grows quite a lot given even a small increase in the number of users.

In a recent joint paper with Ignacio Cascudo, SCRAPE: Scalable Randomness Attested by Public Entities that will presented at ACNS 2017 in Japan this July, we have solved this scalability problem by introducing a PVSS scheme that only requires O(n) modular exponentiations to verify n shares (5n modular exponentiations to be precise) while maintaining efficiency of all other protocol components. The main idea behind our protocol is to use a cheap information theoretical trick to verify the validity of shares instead of performing expensive modular exponentiations. As a result, our protocol requires only 5n modular exponentiations in the verification phase and 4n modular exponentiations in the distribution phase (where shares are generated), while the protocol by Schoenmakers requires 4n+(n^2)/2 exponentiations for verification and 4n+t exponentiations for distribution, where n is the number of users/shares and when n/2 shares are required for reconstructing the secret. Our efficient PVSS protocol can be used to improve the randomness generation component of Ouroboros and the recent result by Syta et al.

Bernardo, the presenter, divided the talk in two parts: the first reviews main topics in Cryptography which would help the viewer to understand the presentation and the protocol itself. Whereas the second is about the protocol itself.

First Part - Cryptography background

• Commitments
• Coin Tossing/Guaranteed Output Delivery
• Verifiable Secret Sharing

Second Part - Proof-of-Stake Protocol

• Comparison Proof-of-Work (PoW) and Proof-of-Stake (PoS)
• Follow the Satoshi technique
• The protocol

The paper is