1992 | OriginalPaper | Chapter
The Use of Interaction in Public Cryptosystems.
extended abstract
Author : Steven Rudich
Published in: Advances in Cryptology — CRYPTO ’91
Publisher: Springer Berlin Heidelberg
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
For every k, we construct an oraclc relative to which secret agreement can be done in k passes, but not in k-1. In particular, for k=3, we get an oracle relative to which secret agreement is possible, but relative to which trapdoor functions do not exist. Thus, unlike the case of private cryptosystems, there is no black box reduction from a k-pass system to a k-1 pass system. Our construction is natural— suggesting that real-world protocols could trade higher interaction costs for an assumption strictly weaker than the existence of trapdoor functions. Finding a complexity theoretic assumption necessary and sufficient for public cryptosystems to exist is one of the important open questions of cryptography. Our results make clear the possibility that this question is impossible to answer because it contains a false hidden assumption: the existence of a 2-pass public cryptosystem follows from the existence of a k-pass system. The question should really be a family of questions: given k find an assumption equivalent to the existence of a k-pass public cryptosystem.