A New Family of Practical Non-Malleable Protocols.

Giovanni Di Crescenzo, Jonathan I. Katz, Rafail Ostrovsky +1 more

Silas Richelson

The idea of protocol security is fundamental in cryptography, and the cryptographic literature is full of different notions of security and different models in which these notions can be achieved. This thesis contains three distinct lines of work, connected by the commonality that the security that they achieve is relevant in today's world of highly interconnected and parallelized networking. Wemake advancements to the well-studied non-malleable and concurrent security models, and in addition we formulate a new security notion of our own called ``topology hiding security.'' Specifically, we give a new protocol for non-malleable commitment, a new model for constant roundconcurrent zero knowledge, and a new multi-party computation protocol which achieves topology hiding security for a large family of underlying network graphs.

Mark M. Wilde

Mark M. Wilde

Shashank Agrawal, Divya Gupta, Hemanta K. Maji +2 more

The notion of non-malleable codes was introduced as a relaxation of standard error-correction and error-detection. Informally, a code is non-malleable if the message contained in a modified codeword is either the original message, or a completely unrelated value. In the information theoretic setting, although existence of such codes for various rich classes of tampering functions is known, explicit constructions exist only for highly structured family of tampering functions. Prior explicit constructions of non-malleable codes rely on the “compartmentalized” structure of the tampering function, i.e. the codeword is partitioned into a priori fixed blocks and each block can only be tampered independently. The prominent examples of this model are the family of bit-wise independent tampering functions and the split-state model. We consider an infinitely large natural class of non-compartmentalized tampering functions. In our model, the tampering function can permute the bits of the encoding and (optionally) perturb them. In the information theoretic setting, we provide an explicit and efficient, rate-1 non-malleable code for multi-bit messages. Lack of explicit constructions of non-malleable codes for non-compartmentalized tampering functions severely inhibits their utility in cryptographic protocols. As a motivation for our construction, we show an application of non-malleable codes to cryptographic protocols. In an idealized setting, we show how string commitments can be based on one-bit commitments, if non-malleable codes exist. Further, as an example of a non-trivial use of non-malleable codes in standard cryptographic protocols (not in an idealized model), we show that if explicit nonmalleable codes are obtained for a slightly larger class of tampering functions than we currently handle, one can obtain a very simple non-malleable commitment scheme, under somewhat strong assumptions.

Rafael Pass, Alon Rosen

We present a new constant round protocol for non-malleable zero-knowledge. Using this protocol as a subroutine, we obtain a new constant-round protocol for non-malleable commitments. Our constructions rely on the existence of (standard) collision resistant hash functions. Previous constructions either relied on the existence of trapdoor permutations and hash functions that are collision resistant against sub-exponential sized circuits, or required a super-constant number of rounds.Additional results are the first construction of a non-malleable commitment scheme that is statistically hiding (with respect to opening), and the first non-malleable protocols that satisfy a strict polynomial-time simulation requirement. The latter are constructed by additionally assuming the existence of trapdoor permutations.Our approach differs from the approaches taken in previous works in that we view non-malleable zero-knowledge as a building-block rather than an end goal. This gives rise to a modular construction of non-malleable commitments and results in a somewhat simpler analysis.The techniques that we use to construct our zero-knowl-edge protocol are non black-box, but are different than the non black-box techniques previously used in the context of non-malleable coin-tossing.