Black-box limitations in cryptography.
Published: 2005
Language: eng
Number of pages: 131
Description: In trying to provide formal evidence that composition has a security increasing property, we ask if the composition of non-adaptively secure permutation generators necessarily produces adaptively secure generators. We show the existence of oracles relative to which there are non-adaptively secure permutation generators, but where the composition of such generators fail to achieve security against adaptive adversaries. Thus, any proof of security for such a construction would need to be non-relativizing. This result can be used to partially justify the lack of formal evidence we have that composition increases security, even though it is a belief shared by many cryptographers.In an attempt to understand the relationships between different cryptographic assumptions, a large amount of research has been done to prove certain primitives imply the others. Of these proofs, the vast majority are "black-box": the security arguments treat the assumed primitive as an oracle with the required security properties---and thus can be thought of as a black-box---relative to which the new primitive is constructed. Due to the limited number of known non "black-box" tools and their relative inefficiency, an inability to give a black-box construction of one primitive from another provides strong evidence that such a construction will be difficult to find, or will be too inefficient to implement. In this thesis two results showing the limitations of black-box proofs are given.Next, we show the existence of oracles relative to which semantically secure public-key encryption primitives (PKEP) exist, but relative to which a large class of black-box constructions are not secure against chosen-ciphertext attacks. The class of constructions has the natural property that the constructed decryption algorithm does not need to query the encryption algorithm of the semantically secure system. This provides the first evidence that there may be no black-box constructions of PKEP secure against chosen ciphertext attacks from semantically secure PKEP. This second result is in a model where all parties are computationally unlimited, but limited in their queries to oracles. As a result, black-box constructions are not strictly ruled out, but have strong complexity theoretic implications (  P&ne;NP ).
Notes: Source: Dissertation Abstracts International, Volume: 66-10, Section: B, page: 5505.

Advisor: C. Rackoff.

Thesis (Ph.D.)--University of Toronto, 2005.

Electronic version licensed for access by U. of T. users.