We complete this line of research by providing simple but comprehensive combinatorial completeness criteria for ALL finite stateless 2-party primitives. I.e., for the first time there are completeness criteria for randomized primitives that are neither symmetric nor asymmetric (but give different outputs to the querying parties), and we overcome the limitation that previous results for randomized primitives with input from BOTH parties only regarded passive adversaries. A fundamental tool of our approach is a powerful lemma from real algebraic geometry, which allows us to base a cryptographic security proof on a rather "game-theoretic" approach.
As a corollary of our work, every non-complete example of a finite stateless 2-party primitive is essentially symmetric. This relationship between non-completeness and symmetric output behavior was previously only known for deterministic cryptogates.Category / Keywords: foundations / oblivious transfer, complete primitives, information-theoretic security, universal composability, secure function evaluation Date: received 19 Mar 2013, last revised 8 May 2013 Contact author: kraschewski at kit edu Available format(s): PDF | BibTeX Citation Version: 20130508:172401 (All versions of this report) Short URL: ia.cr/2013/161 Discussion forum: Show discussion | Start new discussion