(1) Non-Malleability Amplification

by Huijia Lin and Rafael Pass

(2) A Unified Framework for Concurrent Security: Universal Composability from Stand-alone Non-malleability

by Huijia Lin and Rafael Pass and Muthuramakrishnan Venkitasubramaniam

Oded's comments

The key definition is of a $c$-robust NMC, which is a commitment scheme that remains non-malleabily secure also when run in parallel to a single (execution of) an arbitrary $c$-round protocol, where $c$ is a constant (e.g., $c=4$ will do). (In the papers, $c$-robust protocols are called "natural", because it is quite easy to obtain it from the basic case (of $c=0$).)
The first work present several interesting techniques for the construction on NMC, including a transformation of any $k$-round $c$-robust NMC into a $O(k)$-round NMC that is both $c$-robust and maintains security under concurrent self-composition. This transformation applies also in the case that security holds only wrt $t$-bit long IDs (where standard NMC essentially corresponds to IDs of linear length). Another crucial ingrediant is a transformation of any ($c$-robust) protocol that is secure under self-composition wrt $t$-bit long IDs into a ($c$-robust) protocol that is secure wrt $2^{t-1}$-bit long IDs, where the latter protocol is no longer secure under self-composition but maintains the round complexity of the original protocol. Iterating these two steps for $log^*$ times, we obtain a $log^*$-round NMC that (is $c$-robust and) maintains security under concurrent self-composition. Indeed, this is another incarnation of the amplification approach (i.e., obtaining a remarkable result by starting from a known result and applying a sequence of iterartions such that each iteration improves the construct in a relatively moderate manner).
The second work present a unified framework for constructing environmentally-secure (aka UC-secure) two-party protocols in various models (including various set-up assumptions and weak notions of security such as quasi-PPT simulation). The framework uses a $c$-robust NMC and refers to a rather generic gadget, called a "UC-puzzle", that provides (execution) "soundness" w.r.t environments and (statistical) stand-alone "secrecy" (via simulation). Intuitively, environmental-"secrecy" is obtained via the NMC, which allows for simple instantiations of the UC-puzzle.
Taken together, these works provide a host of techniques for the construction of NMC and a very important application of NMC, which may view as no less than a justification for the large effort invested in the construction of NMC.

The original abstract of (1)

We show a technique for amplifying commitment schemes that are non-malleable with respect to identities of length t, into ones that are non-malleable with respect to identities of length $\Omega(2^t)$, while only incurring a constant overhead in round-complexity. As a result we obtain a construction of $O(1)^{log^* n}$-round (i.e., "essentially" constant-round) non-malleable commitments from any one-way function, and using a black-box proof of security.

The original abstract of (2)

We present a unified framework for obtaining Universally Composable (UC) protocols by relying on stand-alone secure non-malleable commitments. Essentially all results on concurrent secure computation---both in relaxed models (e.g., quasi-polynomial time simulation), or with trusted set-up assumptions (e.g., the CRS model, the imperfect CRS model, or the timing model)---are obtained as special cases of our framework. This not only leads to conceptually simpler solutions, but also to improved set-up assumptions, round-complexity, and computational assumptions. Additionally, this framework allows us to consider new relaxed models of security: we show that UC security where the adversary is a uniform PPT but the simulator is allowed to be a non-uniform PPT (i.e., essentially, traditional UC security, but with a non-uniform reduction) is possible without any trusted set-up. This gives the first results on concurrent secure computation without set-up, which can be used for securely computing ``computationally-sensitive'' functionalities (e.g., data-base queries, ``proof of work''-protocols, or playing bridge on the Internet).

Back to list of Oded's choices.