Catálogo de publicaciones - libros

Feistel Network, consisting of a repeated application of the Feistel Transform, gives a very convenient and popular method for designing “cryptographically strong” permutations from corresponding “cryptographically strong” functions. Up to now, all usages of the Feistel Network, including the celebrated Luby-Rackoff’s result, critically rely on (a) ; and (b) appearing during the Feistel computation. Moreover, a small constant number of Feistel rounds was typically sufficient to guarantee security under assumptions (a) and (b). In this work we consider several natural scenarios where at least one of the above assumptions does not hold, and show that a constant, or even logarithmic number of rounds is to handle such applications, implying that a new method of analysis is needed.

On a positive side, we develop a new combinatorial understanding of Feistel networks, which makes them applicable to situations when the round functions are merely rather than (pseudo)random and/or when the intermediate round values may be leaked to the adversary (either through an attack or because the application it). In essence, our results show that in any such scenario a super-logarithmic number of Feistel rounds is to guarantee security.

Of independent interest, our technique yields a novel domain extension method for messages authentication codes and other related primitives, settling a question studied by An and Bellare in CRYPTO 1999.

Oblivious transfer (OT) is a primitive of paramount importance in cryptography or, more precisely, two- and multi-party computation due to its universality. Unfortunately, OT cannot be achieved in an unconditionally secure way for both parties from scratch. Therefore, it is a natural question what information-theoretic primitives or computational assumptions OT be based on.

The results in our paper are threefold. First, we give an optimal proof for the standard protocol to realize unconditionally secure OT from a weak variant of OT called , for which a malicious receiver can virtually obtain any possible information he wants, as long as he does not get all the information. This result is based on a novel distributed leftover hash lemma which is of independent interest.

Second, we give conditions for when OT can be obtained from a faulty variant of OT called , for which it can occur that any of the parties obtains too much information, or the result is incorrect. These bounds and protocols, which correct on previous results by Damgård , are of central interest since in most known realizations of OT from weak primitives, such as noisy channels, a weak OT is constructed first.

Finally, we carry over our results to the computational setting and show how a weak OT that is sometimes incorrect and is only mildly secure against computationally bounded adversaries can be strengthened.

We study an variant of oblivious transfer in which a sender has messages, of which a receiver can adaptively choose to receive one-after-the-other, in such a way that (a) the sender learns nothing about the receiver’s selections, and (b) the receiver only learns about the requested messages. We propose two practical protocols for this primitive that achieve a stronger security notion than previous schemes with comparable efficiency. In particular, by requiring full simulatability for both sender and receiver security, our notion prohibits a subtle selective-failure attack not addressed by the security notions achieved by previous practical schemes.

Our first protocol is a very efficient generic construction from unique blind signatures in the random oracle model. The second construction does not assume random oracles, but achieves remarkable efficiency with only a constant number of group elements sent during each transfer. This second construction uses novel techniques for building efficient simulatable protocols.