Previous: Terminology, Up: Preliminaries



1.3.2 Security

“Mental Poker” solutions cannot prevent that malicious players exchange private information, for example, by telephone or Internet chat. Cryptographic protocols can only minimize the effect of such colluding parties and should try to protect the confidentiality for honest players. But even this small protection often relies on number-theoretical assumptions which are only believed to be true, i.e. problems like factoring products of large primes or computing discrete logarithms are only believed to be hard. That means, strict mathematical proofs1 for the hardness of these problems are not known, and it is not very likely that such proofs will ever be found. However, almost all public key cryptosystems rely on such assumptions and therefore you should not worry about this issue, as long as reasonable security parameters are chosen.

LibTMCG was designed to provide security in the “honest-but-curious” (aka semi-honest) adversary model. That means, all participants follow the protocol instructions properly but they may gather information and share them within a coalition to obtain a game advantage. Thus we are not concerned with robustness and availability issues which are hard to solve in asynchronous environments like the Internet. However, the most operations are verifiable such that cheating can be detected. To obtain this verifiability, the protocols deploy so-called zero-knowledge proofs which yield no further knowledge but the validity of a statement. The soundness error of these proofs is bounded by a security parameter t. Depending on your application scenario this parameter should be chosen such that there is a reasonable tradeoff between the cheating probability (which is less or equal than 2^-t) and the produced computational and communication complexity.

Unfortunately, in practice there is a substantial problem with the detection of cheaters. Reliable cheater detection requires that an authenticated broadcast channel has been established, where all players have read/write access. LibTMCG does not yet contain the necessary protocols (reliable broadcast) for creating such a channel. Thus you should take into account that not necessarily the prover is the source of all evil, if a verification procedure fails. This level of uncertainty is also a reason for our restricted adversary model.

Note that it is not known, whether the used protocols retain their zero-knowledge property, when they are composed and executed in a concurrent setting. Thus the application programmer should be careful and avoid parallel protocol sessions. It is an open research project to create a protocol suite whose security can be proven in the UC-framework of Canetti (see Universally Composable Security: A New Paradigm for Cryptographic Protocols, Cryptology ePrint Archive: Report 2000/067). Furthermore, the protocols should employ concurrent zero-knowledge proofs (see Dwork, Naor, Sahai: Concurrent Zero-Knowledge, Journal of the ACM 51(6):851–898, 2004).

LibTMCG was carefully implemented with respect to timing attacks (see Kocher: Cryptanalysis of Diffie-Hellman, RSA, DSS, and other cryptosystems using timing attacks, CRYPTO '95, LNCS 963, 1995). Therefore we loose some efficiency, e.g., during modular exponentiations. However, it is strongly recommended to leave the timing attack protection turned on, unless you know exactly where it is really not needed.

Security Advice: We have implemented all cryptographic primitives according to the cited research papers and to the best of our knowledge. However, we can not eliminate any possibility of contained flaws or insecurity, because the implementation of such complex protocols is always an error-prone process. Thus we encourage readers with advanced cryptographic background to review the source code of LibTMCG. Please report any complaint or correction proposal.

Footnotes

[1] For instance, a “tight reduction” to a known hard problem in the sense of complexity theory.