Information-Theoretic Interactive Hashing and Oblivious Transfer to a Storage-Bounded Receiver
Authors:
- Christian CachinCCChristian Cachin
- Claude CrepeauCCClaude Crepeau
- Julien MarcilJMJulien Marcil
- George SavvidesGSGeorge Savvides
- 11 September 2015
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 61 (10) , 5623-5635
Abstract
Interactive hashing has featured as an essential ingredient in protocols realizing a large variety of cryptographic tasks, notably oblivious transfer in the bounded storage model. In interactive hashing, a sender transfers a bit string to a receiver such that two strings are received, the original string and a second string that appear to be chosen at random. This paper presents a self-contained, information theoretic study of interactive hashing. We start by formalizing the notion of interactive hashing as a cryptographic primitive, disentangling it from the specifics of its various implementations. To this end, we present an application-independent set of information theoretic conditions that all interactive hashing protocols must ideally satisfy. We then provide a detailed analysis of a standard implementation of interactive hashing which is shown to satisfy all the conditions of our definition. Our analysis represents a significant improvement over previous attempts in more restricted contexts. Despite its generality, it offers a considerably simpler proof of security. Moreover, it establishes a tighter upper bound on the cheating probability of a dishonest sender, who wishes to manipulate the protocol so that both output strings have some rare desirable property. In particular, we prove that if the set of desirable strings for the dishonest sender represents a fraction f of all strings, then the probability that both outputs will be from this set is no larger than 15.6805 · f. This upper bound is valid for any f and is tight up to a small constant, since a sender acting honestly would get two outputs from this set with probability very close to f. We illustrate the power of interactive hashing as a cryptographic tool by surveying protocols achieving oblivious transfer in the bounded storage model, which typically rely heavily on interactive hashing.Keywords
This publication has 28 references indexed in Scilit:
- Statistically Hiding Commitments and Statistical Zero-Knowledge Arguments from Any One-Way FunctionSIAM Journal on Computing, 2009
- A New Interactive Hashing Theorem2007
- Constant-Round Oblivious Transfer in the Bounded Storage ModelJournal of Cryptology, 2007
- Information-Theoretic Conditions for Two-Party Secure Function EvaluationLecture Notes in Computer Science, 2006
- Foundations of Cryptography2004
- Constructing Locally Computable Extractors and Cryptosystems in the Bounded-Storage ModelJournal of Cryptology, 2003
- Oblivious Transfer in the Bounded Storage Model2001
- How to generate and exchange secrets1986
- A randomized protocol for signing contractsCommunications of the ACM, 1985
- Conjugate codingACM SIGACT News, 1983