IACR News item: 26 March 2013
Daniel Kraschewski
ePrint ReportWe 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.
Additional news items may be found on the IACR news page.