(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.