## CryptoDB

### Ronald Cramer

#### Affiliation: CWI & Leiden University

#### Publications

**Year**

**Venue**

**Title**

2020

EUROCRYPT

Blackbox Secret Sharing Revisited: A Coding-Theoretic Approach with Application to Expansionless Near-Threshold Schemes
📺
Abstract

A {\em blackbox} secret sharing (BBSS) scheme works
in exactly the same way for all finite Abelian groups $G$; it can be instantiated for any such group $G$ and {\em only} black-box access to its group operations and to random group elements is required. A secret is a single group element and each of the $n$ players' shares is a vector of such elements. Share-computation and secret-reconstruction is by integer linear combinations. These do not depend on $G$, and neither do the privacy and reconstruction parameters $t,r$. This classical, fundamental primitive was introduced by Desmedt and Frankel (CRYPTO 1989) in their context of ``threshold cryptography.'' The expansion factor is the total number of group elements in a full sharing divided by $n$. For threshold BBSS with $t$-privacy ($1\leq t \leq n-1$), $t+1$-reconstruction and arbitrary $n$, constructions with minimal expansion $O(\log n)$ exist
(CRYPTO 2002, 2005).
These results are firmly rooted in number theory; each makes
(different) judicious choices of orders in number fields admitting
a vector of elements of very large length (in the number field degree) whose corresponding Vandermonde-determinant is sufficiently controlled
so as to enable BBSS by a suitable adaptation of Shamir's scheme.
Alternative approaches generally lead to very large expansion.
The state of the art of BBSS has not changed for the last 15 years.
Our contributions are two-fold.
(1) We introduce a novel, nontrivial, effective construction of BBSS based on {\em coding theory}
instead of number theory.
For threshold-BBSS we also achieve minimal expansion factor $O(\log n)$.
(2) Our method is more versatile. Namely, we show, for the first time, BBSS that is {\em near-threshold}, i.e.,
$r-t$ is an arbitrarily small
constant fraction of $n$, {\em and} that has expansion factor~$O(1)$, i.e.,
individual share-vectors of {\em constant} length (``asymptotically expansionless''). Threshold can be concentrated essentially freely
across full range. We also show expansion is minimal for near-threshold and that such BBSS cannot be attained by previous methods.
Our general construction is based on a well-known mathematical principle, the local-global principle. More precisely, we first construct BBSS over local rings through either Reed-Solomon or algebraic geometry codes. We then ``glue'' these schemes together in a dedicated manner to obtain a global secret sharing scheme, i.e., defined over the integers, which, as we finally prove using novel insights, has the desired BBSS properties. Though our main purpose here is advancing BBSS for its own sake, we also briefly address possible protocol applications.

2020

CRYPTO

Compressed Sigma-Protocol Theory and Practical Application to Plug & Play Secure Algorithmics
📺
Abstract

Sigma-Protocols provide a well-understood basis for secure algorithmics. Recently, Bulletproofs (Bootle et al., EUROCRYPT 2016, and Bünz et al., S&P 2018) have been proposed as a drop-in replacement in case of zero-knowledge (ZK) for arithmetic circuits, achieving logarithmic communication instead of linear. Its pivot is an ingenious, logarithmic-size proof of knowledge BP for certain quadratic relations. However, reducing ZK for general relations to it forces a somewhat cumbersome ``reinvention'' of cryptographic protocol theory.
We take a rather different viewpoint and reconcile Bulletproofs with Sigma-Protocol Theory such that (a) simpler circuit ZK is developed within established theory, while (b) achieving exactly the same logarithmic communication.
The natural key here is linearization. First, we repurpose BPs as a blackbox compression mechanism for standard Sigma-Protocols handling ZK proofs of general linear relations (on compactly committed secret vectors); our pivot. Second, we reduce the case of general nonlinear relations to blackbox applications of our pivot via a novel variation on arithmetic secret sharing based techniques for Sigma-Protocols (Cramer et al., ICITS 2012). Orthogonally, we enhance versatility by enabling scenarios not previously addressed, e.g., when a secret input is dispersed across several commitments. Standard implementation platforms leading to logarithmic communication follow from a Discrete-Log assumption or a generalized Strong-RSA assumption. Also, under a Knowledge-of-Exponent Assumption (KEA) communication drops to constant, as in ZK-SNARKS.
All in all, our theory should more generally be useful for modular (``plug & play'') design of practical cryptographic protocols; this is further evidenced by our separate work (2020) on proofs of partial knowledge.

2020

TCC

On the Complexity of Arithmetic Secret Sharing
📺
Abstract

Since the mid 2000s, asymptotically-good strongly-multiplicative linear (ramp) secret
sharing schemes over a fixed finite field have turned out as a
central theoretical primitive in numerous
constant-communication-rate results in multi-party cryptographic scenarios,
and, surprisingly, in two-party cryptography as well.
Known constructions of this most powerful class of arithmetic secret sharing schemes all rely heavily on algebraic geometry (AG), i.e., on dedicated AG codes based on asymptotically good towers of algebraic function fields defined over finite fields. It is a well-known open question since the first (explicit) constructions of such schemes
appeared in CRYPTO 2006 whether the use of ``heavy machinery'' can be avoided here. i.e.,
the question is whether the mere existence of such schemes can also be proved by ``elementary''
techniques only (say, from classical algebraic coding theory), even disregarding effective construction. So far, there is no progress.
In this paper we show the theoretical result
that, (1) {\em no matter whether this open question has an affirmative answer or not},
these schemes {\em can} be constructed explicitly by {\em elementary algorithms} defined
in terms of basic algebraic coding theory.
This pertains to all relevant operations
associated to such schemes, including, notably,
the generation of an instance for a given number of players $n$, as well as
error correction in the presence of corrupt shares.
We further show that (2) the algorithms are {\em quasi-linear time} (in $n$);
this is (asymptotically) significantly more efficient than the known constructions.
That said, the {\em analysis} of the mere termination of these algorithms {\em does} still rely
on algebraic geometry, in the sense that it requires ``blackbox application'' of suitable {\em existence}
results for these schemes.
Our method employs a nontrivial, novel adaptation of a classical (and ubiquitous) paradigm
from coding theory that enables transformation of {\em existence} results
on asymptotically good codes into {\em explicit construction} of such codes via {\em concatenation}, at some constant loss in parameters achieved. In a nutshell, our generating idea is to
combine a cascade of explicit but ``asymptotically-bad-yet-good-enough schemes'' with an asymptotically good one in such a judicious way that the latter can be selected with exponentially small number of players
in that of the compound scheme. This opens the door to efficient, elementary exhaustive search.
In order to make this work, we overcome
a number of nontrivial technical hurdles. Our main handles include a novel application of the recently introduced
notion of Reverse Multiplication-Friendly Embeddings (RMFE) from CRYPTO 2018,
as well as a novel application of a natural variant in arithmetic secret sharing from EUROCRYPT 2008.

2020

ASIACRYPT

Asymptotically Good Multiplicative LSSS over Galois Rings and Applications to MPC over Z/p^k Z
📺
Abstract

We study information-theoretic multiparty computation (MPC) protocols over rings Z/p^k Z that have good asymptotic communication complexity for a large number of players. An important ingredient for such protocols is arithmetic secret sharing, i.e., linear secret-sharing schemes with multiplicative properties. The standard way to obtain these over fields is with a family of linear codes C, such that C, $C^\perp$ and C^2 are asymptotically good (strongly multiplicative). For our purposes here it suffices if the square code C^2 is not the whole space, i.e., has codimension at least 1 (multiplicative).
Our approach is to lift such a family of codes defined over a finite field F to a Galois ring, which is a local ring that has F as its residue field and that contains Z/p^k Z as a subring, and thus enables arithmetic that is compatible with both structures. Although arbitrary lifts preserve the distance and dual distance of a code, as we demonstrate with a counterexample, the multiplicative property is not preserved. We work around this issue by showing a dedicated lift that preserves \emph{self-orthogonality} (as well as distance and dual distance), for p > 2. Self-orthogonal codes are multiplicative, therefore we can use existing results of asymptotically good self-dual codes over fields to obtain arithmetic secret sharing over Galois rings. For p = 2 we obtain multiplicativity by using existing techniques of secret-sharing using both C and $C^\perp$, incurring a constant overhead. As a result, we obtain asymptotically good arithmetic secret-sharing schemes over Galois rings.
With these schemes in hand, we extend existing field-based MPC protocols to obtain MPC over Z/p^k Z, in the setting of a submaximal adversary corrupting less than a fraction 1/2 - \varepsilon of the players, where \varepsilon > 0 is arbitrarily small. We consider 3 different corruption models, and obtain O(n) bits communicated per multiplication for both passive security and active security with abort. For full security with guaranteed output delivery we use a preprocessing model and get O(n) bits per multiplication in the online phase and O(n log n) bits per multiplication in the offline phase.
Thus, we obtain true linear bit complexities, without the common assumption that the ring size depends on the number of players.

2019

TCC

Efficient Information-Theoretic Secure Multiparty Computation over $\mathbb {Z}/p^k\mathbb {Z}$ via Galois Rings
Abstract

At CRYPTO 2018, Cramer et al. introduced a secret-sharing based protocol called SPD$$\mathbb {Z}_{2^k}$$ that allows for secure multiparty computation (MPC) in the dishonest majority setting over the ring of integers modulo $$2^k$$, thus solving a long-standing open question in MPC about secure computation over rings in this setting. In this paper we study this problem in the information-theoretic scenario. More specifically, we ask the following question: Can we obtain information-theoretic MPC protocols that work over rings with comparable efficiency to corresponding protocols over fields? We answer this question in the affirmative by presenting an efficient protocol for robust Secure Multiparty Computation over $$\mathbb {Z}/p^{k}\mathbb {Z}$$ (for any prime p and positive integer k) that is perfectly secure against active adversaries corrupting a fraction of at most 1/3 players, and a robust protocol that is statistically secure against an active adversary corrupting a fraction of at most 1/2 players.

2018

CRYPTO

Amortized Complexity of Information-Theoretically Secure MPC Revisited
📺
Abstract

A fundamental and widely-applied paradigm due to Franklin and Yung (STOC 1992) on Shamir-secret-sharing based general n-player MPC shows how one may trade the adversary thresholdt against amortized communication complexity, by using a so-called packed version of Shamir’s scheme. For e.g. the BGW-protocol (with active security), this trade-off means that if
$$t + 2k -2 < n/3$$
t+2k-2<n/3, then kparallel evaluations of the same arithmetic circuit on different inputs can be performed at the overall cost corresponding to a single BGW-execution.In this paper we propose a novel paradigm for amortized MPC that offers a different trade-off, namely with the size of the field of the circuit which is securely computed, instead of the adversary threshold. Thus, unlike the Franklin-Yung paradigm, this leaves the adversary threshold unchanged. Therefore, for instance, this paradigm may yield constructions enjoying the maximal adversary threshold
$$\lfloor (n-1)/3 \rfloor $$
⌊(n-1)/3⌋ in the BGW-model (secure channels, perfect security, active adversary, synchronous communication).Our idea is to compile an MPC for a circuit over an extension field to a parallel MPC of the same circuit but with inputs defined over its base field and with the same adversary threshold. Key technical handles are our notion of reverse multiplication-friendly embeddings (RMFE) and our proof, by algebraic-geometric means, that these are constant-rate, as well as efficient auxiliary protocols for creating “subspace-randomness” with good amortized complexity. In the BGW-model, we show that the latter can be constructed by combining our tensored-up linear secret sharing with protocols based on hyper-invertible matrices á la Beerliova-Hirt (or variations thereof). Along the way, we suggest alternatives for hyper-invertible matrices with the same functionality but which can be defined over a large enough constant size field, which we believe is of independent interest.As a demonstration of the merits of the novel paradigm, we show that, in the BGW-model and with an optimal adversary threshold
$$\lfloor (n-1)/3 \rfloor $$
⌊(n-1)/3⌋, it is possible to securely compute a binary circuit with amortized complexity O(n) of bits per gate per instance. Known results would give
$$n \log n$$
nlogn bits instead. By combining our result with the Franklin-Yung paradigm, and assuming a sub-optimal adversary (i.e., an arbitrarily small
$$\epsilon >0$$
ϵ>0 fraction below 1/3), this is improved to O(1) bits instead of O(n).

2018

CRYPTO

SPD$\mathbb {Z}_{2^k}$: Efficient MPC mod $2^k$ for Dishonest Majority
📺
Abstract

Most multi-party computation protocols allow secure computation of arithmetic circuits over a finite field, such as the integers modulo a prime. In the more natural setting of integer computations modulo $$2^{k}$$, which are useful for simplifying implementations and applications, no solutions with active security are known unless the majority of the participants are honest.We present a new scheme for information-theoretic MACs that are homomorphic modulo $$2^k$$, and are as efficient as the well-known standard solutions that are homomorphic over fields. We apply this to construct an MPC protocol for dishonest majority in the preprocessing model that has efficiency comparable to the well-known SPDZ protocol (Damgård et al., CRYPTO 2012), with operations modulo $$2^k$$ instead of over a field. We also construct a matching preprocessing protocol based on oblivious transfer, which is in the style of the MASCOT protocol (Keller et al., CCS 2016) and almost as efficient.

2017

EUROCRYPT

2015

EUROCRYPT

2011

CRYPTO

2008

EUROCRYPT

2008

EPRINT

Detection of Algebraic Manipulation with Applications to Robust Secret Sharing and Fuzzy Extractors
Abstract

Consider an abstract storage device $\Sigma(\G)$ that can hold a
single element $x$ from a fixed, publicly known finite group $\G$.
Storage is private in the sense that an adversary does not have read
access to $\Sigma(\G)$ at all. However, $\Sigma(\G)$ is non-robust in the sense
that the adversary can modify its contents by adding some offset $\Delta \in \G$.
Due to the privacy of the storage device, the value $\Delta$ can only depend on an adversary's {\em a priori} knowledge of $x$. We introduce a new primitive called an {\em
algebraic manipulation detection} (AMD) code, which encodes a source $s$ into a value $x$ stored on $\Sigma(\G)$ so that any tampering
by an adversary will be detected, except with a small error probability $\delta$. We give a nearly optimal construction of AMD codes,
which can flexibly accommodate arbitrary choices for the length of the source $s$ and security level $\delta$. We use this construction in two applications:
\begin{itemize}
\item We show how to efficiently convert any linear secret sharing
scheme into a {\em robust secret sharing scheme}, which ensures that
no \emph{unqualified subset} of players can modify their shares and cause
the reconstruction of some value $s'\neq s$.
\item
We show how how to build nearly optimal {\em robust fuzzy
extractors} for several natural metrics. Robust fuzzy extractors enable one to reliably extract and later recover random keys from noisy and non-uniform secrets,
such as biometrics, by relying only on {\em non-robust public storage}. In the past, such constructions were known only in the random oracle model, or required the entropy rate of the secret to be greater than half. Our construction relies on a randomly chosen common reference string (CRS) available to all parties.
\end{itemize}

2007

CRYPTO

2006

CRYPTO

2006

EPRINT

A Note on Bounded Chosen Ciphertext Security from Black-box Semantical Security
Abstract

Designing public key encryption schemes withstanding chosen
ciphertext attacks, which is the highest security level for such
schemes, is generally perceived as a delicate and intricate task,
and for good reason. In the standard model, there are essentially
three well-known but quite involved approaches.
This state of affairs is to be contrasted with the situation for
semantically secure encryption schemes, a much weaker security
notion that only guarantees security in the absence of active
attack but that appears to be much easier to fulfill,
both conceptually and practically. Thus, the boundary
between passive attack and active attack seems to make up the
dividing line between which security levels are relatively easily
achieved and which are not. Our contributions are two-fold.
First, we show a simple, efficient black-box construction of a
public key encryption scheme withstanding chosen ciphertext attack
from any given semantically secure one. Our scheme is $q$-bounded in
the sense that security is only guaranteed if the adversary makes at
most $q$ adaptive chosen ciphertext queries. Here, $q$ is an
arbitrary polynomial that is fixed in advance in the key-generation.
Our work thus shows that whether or not the number of active,
adversarial queries is known in advance is the dividing line, and
not passive versus active attack. In recent work, Gertner, Malkin
and Myers show that such black-box reductions are impossible if
instead $q$ is a polynomial that only depends on the adversary.
Thus, in a sense, our result appears to be the best black-box result
one can hope for. Second, we give a non-blackbox reduction from bounded chosen ciphertext security to semantic security where the length of the public/secret keys and ciphertexts drops from quadratic to linear in $q$, compared to our black-box construction. This latter scheme, however, is only of theoretical interest as it uses general NP-reductions, and our blackbox construction is in fact much more practical.

2005

CRYPTO

2004

EPRINT

On codes, matroids and secure multi-party computation from linear secret sharing schemes
Abstract

Error correcting codes and matroids have been widely used in the study of ordinary secret sharing schemes. In this paper, we study the connections between codes, matroids, and a special class of secret sharing schemes: multiplicative linear secret sharing schemes. Such schemes are known to enable multi-party computation protocols secure against general (non-threshold) adversaries.
Two open problems related to the complexity of multiplicative LSSSs are considered in this paper.
The first one deals with strongly multiplicative LSSSs. As opposed to the case of multiplicative LSSSs, it is not known whether there is an efficient method to transform an LSSS into a strongly multiplicative LSSS for the same access structure with a polynomial increase of the complexity. We prove a property of strongly multiplicative LSSSs that could be useful in solving this problem. Namely, using a suitable generalization of the well-known Berlekamp-Welch decoder, we show that all strongly multiplicative LSSSs enable efficient reconstruction of a shared secret in the presence of malicious faults.
The second one is to characterize the access structures of ideal multiplicative LSSSs. Specifically, we wonder whether all self-dual vector space access structures are in this situation. By the aforementioned connection, this in fact constitutes an open problem about matroid theory, since it can be re-stated in terms of representability of identically self-dual matroids by self-dual codes. We introduce a new concept, the flat-partition, that provides a useful classification of identically self-dual matroids. Uniform identically self-dual matroids, which are known to be representable by self-dual codes, form one of the classes. We prove that this property also holds for the family of matroids that, in a natural way, is the next class in the above classification: the identically self-dual bipartite matroids.

2003

EPRINT

Efficient Multi-Party Computation over Rings
Abstract

Secure multi-party computation (MPC) is an active research area, and a wide range of literature can be found nowadays suggesting improvements and generalizations of existing protocols in various directions. However, all current techniques for secure MPC apply to functions that are represented by (boolean or arithmetic) circuits over finite {\em fields}. We are motivated by two limitations of these techniques:
{\sc Generality.} Existing protocols do not apply to computation over more general algebraic structures (except via a brute-force simulation of computation in these structures).
{\sc Efficiency.} The best known {\em constant-round} protocols do not efficiently scale even to the case of large finite fields.
Our contribution goes in these two directions. First, we propose a basis for unconditionally secure MPC over an arbitrary finite {\em ring}, an algebraic object with a much less nice structure than a field, and obtain efficient MPC protocols requiring only a {\em black-box access} to the ring operations and to random ring elements. Second, we extend these results to the constant-round setting, and suggest efficiency improvements that are relevant also for the important special case of fields. We demonstrate the usefulness of the above results by presenting a novel application of MPC over (non-field) rings to the round-efficient secure computation of the maximum function.

2002

EUROCRYPT

2002

EPRINT

Optimal Black-Box Secret Sharing over Arbitrary Abelian Groups
Abstract

A {\em black-box} secret sharing scheme for the threshold
access structure $T_{t,n}$ is one which works over any finite Abelian group $G$.
Briefly, such a scheme differs from an ordinary linear secret sharing
scheme (over, say, a given finite field) in that distribution matrix
and reconstruction vectors are defined over the integers and are designed {\em
independently} of the group $G$ from which the secret and the shares
are sampled. This means that perfect completeness and perfect
privacy are guaranteed {\em regardless} of which group $G$ is chosen. We define
the black-box secret sharing problem as the problem of devising, for
an arbitrary given $T_{t,n}$, a scheme with minimal expansion factor,
i.e., where the length of the full vector of shares divided by the
number of players $n$ is minimal.
Such schemes are relevant for instance in the context of distributed
cryptosystems based on groups with secret or hard to compute group
order. A recent example is secure general multi-party computation over
black-box rings.
In 1994 Desmedt and Frankel have proposed an
elegant approach to the black-box secret sharing problem
based in part on polynomial interpolation over
cyclotomic number fields. For arbitrary given $T_{t,n}$ with
$0<t<n-1$, the expansion factor of their scheme is $O(n)$. This is
the best previous general approach to the problem.
Using low degree integral extensions of the integers over which there exists a
pair of sufficiently large Vandermonde matrices with co-prime
determinants, we construct, for arbitrary given $T_{t,n}$ with
$0<t<n-1$ , a black-box secret sharing scheme with expansion factor
$O(\log n)$, which we show is minimal.

2001

EPRINT

Design and Analysis of Practical Public-Key Encryption Schemes Secure against Adaptive Chosen Ciphertext Attack
Abstract

A new public key encryption scheme, along with several variants,
is proposed and analyzed.
The scheme and its variants are quite practical, and are proved
secure
against adaptive chosen ciphertext attack under standard
intractability assumptions.
These appear to be the first public-key encryption schemes
in the literature that are simultaneously practical and provably secure.

2001

EPRINT

Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption
Abstract

We present several new and fairly practical public-key
encryption schemes and prove them secure against adaptive
chosen ciphertext attack. One scheme is based on
Paillier's Decision Composite Residuosity (DCR)
assumption, while another is based in the classical
Quadratic Residuosity (QR) assumption. The analysis is in
the standard cryptographic model, i.e., the security of
our schemes does not rely on the Random Oracle model.
We also introduce the notion of a universal hash
proof system. Essentially, this is a special kind of
non-interactive zero-knowledge proof system for an NP
language. We do not show that universal hash
proof systems exist for all NP languages, but we do
show how to construct very efficient universal hash
proof systems for a general class of group-theoretic
language membership problems.
Given an efficient universal hash proof system for a
language with certain natural cryptographic
indistinguishability properties, we show
how to construct an efficient public-key encryption
schemes secure against adaptive chosen ciphertext attack
in the standard model. Our construction only uses the
universal hash proof systemas a primitive: no other
primitives are required, although even more efficient
encryption schemes can be obtained by using hash
functions with appropriate collision-resistance
properties.
We show how to construct efficient universal hash proof
systems for languages related to the DCR and QR
assumptions. From these we get corresponding public-key
encryption schemes that are secure under these assumptions.
We also show that the Cramer-Shoup encryption scheme
(which up until now was the only practical
encryption scheme that could be proved secure against
adaptive chosen ciphertext attack under a reasonable
assumption, namely, the Decision Diffie-Hellman assumption)
is also a special case of our general theory.

2000

EPRINT

General Secure Multi-Party Computation from any Linear Secret Sharing Scheme
Abstract

We show that verifiable secret sharing (VSS) and secure multi-party
computation (MPC) among a set of $n$ players can efficiently be based
on {\em any} linear secret sharing scheme (LSSS) for the players,
provided that the access structure of the LSSS allows MPC or VSS at
all. Because an LSSS neither guarantees reconstructability when some
shares are false, nor verifiability of a shared value, nor allows for
the multiplication of shared values, an LSSS is an apparently much weaker
primitive than VSS or MPC.
Our approach to secure MPC is generic and applies to both the
in\-for\-ma\-tion-theoretic and the cryptographic setting. The
construction is based on 1) a formalization of the special
multiplicative property of an LSSS that is needed to perform a
multiplication on shared values, 2) an efficient generic construction
to obtain from any LSSS a multiplicative LSSS for the same access
structure, and 3) an efficient generic construction to build
verifiability into every LSSS (always assuming that the adversary
structure allows for MPC or VSS at all).
The protocols are efficient. In contrast to all previous
information-theo\-re\-ti\-cal\-ly secure protocols, the field size is not
restricted (e.g, to be greater than $n$). Moreover, we exhibit
adversary structures for which our protocols are polynomial in $n$
while all previous approaches to MPC for non-threshold adversaries
provably have super-polynomial complexity.

2000

EPRINT

On the Complexity of Verifiable Secret Sharing and Multi-Party Computation
Abstract

We first study the problem of doing Verifiable Secret Sharing (VSS)
information theoretically secure for a general access structure. We
do it in the model where private channels between players and a
broadcast channel is given, and where an active, adaptive adversary
can corrupt any set of players not in the access structure. In
particular, we consider the complexity of protocols for this
problem, as a function of the access structure and the number of
players. For all access structures where VSS is possible at all, we
show that, up to a polynomial time black-box reduction, the
complexity of adaptively secure VSS is the same as that of ordinary
secret sharing (SS), where security is only required against a
passive, static adversary. Previously, such a connection was only
known for linear secret sharing and VSS schemes.
We then show an impossibility result indicating that a similar
equivalence does not hold for Multiparty Computation (MPC): we show
that even if protocols are given black-box access for free to an
idealized secret sharing scheme secure for the access structure in
question, it is not possible to handle all relevant access
structures efficiently, not even if the adversary is passive and
static. In other words, general MPC can only be black-box reduced
efficiently to secret sharing if extra properties of the secret
sharing scheme used (such as linearity) are assumed.

2000

EPRINT

Efficient Zero-Knowledge Proofs of Knowledge Without Intractability Assumptions
Abstract

We initiate the investigation of the class of relations
that admit extremely efficient perfect zero knowledge
proofs of knowledge: constant number of rounds, communication
linear in the length of the statement and the witness, and
negligible knowledge error. In its most general incarnation,
our result says that for relations that have a particular
three-move honest-verifier zero-knowledge (HVZK) proof of knowledge,
and which admit a particular three-move HVZK proof of knowledge for
an associated commitment relation, perfect zero knowledge
(against a general verifier) can be achieved essentially for free,
even when proving statements on several instances combined
under under monotone function composition. In addition,
perfect zero-knowledge is achieved with an optimal 4-moves.
Instantiations of our main protocol lead to efficient perfect
ZK proofs of knowledge of discrete logarithms and RSA-roots,
or more generally, $q$-one-way group homomorphisms.
None of our results rely on intractability assumptions.

2000

EPRINT

Multiparty Computation from Threshold Homomorphic Encryption
Abstract

We introduce a new approach to multiparty computation (MPC)
basing it on homomorphic
threshold crypto-systems. We show that given keys for any
sufficiently efficient
system of this type, general MPC protocols for $n$ players can be
devised which are
secure against an active adversary that corrupts any minority of the
players.
The total number of bits sent is $O(nk|C|)$, where $k$ is the
security parameter and $|C|$ is
the size of a (Boolean) circuit computing the function to be
securely evaluated.
An earlier proposal by Franklin and Haber with the same complexity
was only secure
for passive adversaries, while all earlier protocols with active
security had complexity at
least quadratic in $n$. We give two examples of threshold
cryptosystems that can support our
construction and lead to the claimed complexities.

1999

EPRINT

Signature Schemes Based on the Strong RSA Assumption
Abstract

We describe and analyze a new digital signature scheme.
The new scheme is quite efficient, does not require the the signer
to maintain any state, and can be proven secure against adaptive
chosen message attack under a reasonable intractability assumption,
the so-called Strong RSA Assumption.
Moreover, a hash function can be incorporated into the scheme
in such a way that it is also secure in the random oracle model
under the standard RSA Assumption.

1998

CRYPTO

1998

EPRINT

A Practical Public Key Cryptosystem Provably Secure against Adaptive Chosen Ciphertext Attack
Abstract

A new public key cryptosystem is presented that is provably secure
against adaptive chosen ciphertext attack.
The scheme is quite practical, and the proof of security relies
only on standard intractability assumptions.

1996

EPRINT

On Monotone Function Closure of Statistical Zero-Knowledge
Abstract

Assume we are given a language L with an honest verifier
perfect zero-knowledge proof system. Assume also that the proof system is an
Arthur-Merlin game with at most 3 moves. The class of such languages
includes all random self-reducible language, and also any language with a
perfect zero-knowledge non-interactive proof.
We show that such a language satisfies a certain closure property, namely
that languages constructed from L by applying certain monotone functions to
statements on membership in L have perfect zero-knowledge proof systems.
The new set of languages we can build includes L itself, but also for
example languages consisting of n words of which at least t are in L.
A similar closure property is shown to hold for the complement of L and for
statistical zero-knowledge. The property we need for the monotone functions used
to build the new languages is that there are efficient secret sharing schemes
for their associated access structures. This includes (but is not necessarily
limited to) all monotone functions with polynomial size monotone formulas.

1996

EPRINT

Linear Zero-Knowledge - A note on Efficient Zero-Knowledge Proofs and Arguments
Abstract

We present a zero-knowledge proof system for any NP language L, which
allows showing that x is in L using communication corresponding
to $O(|x| sup c)+k$ bit commitments, with error probability $2 sup -k$,
and where c is a constant depending only on L.
The proof can be based on any bit
commitment scheme with a particular set of properties. We suggest an
efficient implementation based on factoring. The protocol allows showing
that a Boolean formula of size n is satisfiable,
with error probability $2 sup -n$, using O(n) commitments.
This is the first protocol for SAT that is linear in this sense.<br>
[The rest of the abstract was truncated and appears below -- the library.]

#### Program Committees

- TCC 2012
- TCC 2011
- PKC 2008
- Eurocrypt 2005
- Crypto 2004
- TCC 2004
- Crypto 2003
- Eurocrypt 2003
- Asiacrypt 2001
- Eurocrypt 2000
- Crypto 2000
- Crypto 1999

#### Coauthors

- Masayuki Abe (1)
- Mark Abspoel (2)
- Saurabh Agarwal (1)
- Thomas Attema (1)
- Ignacio Cascudo (6)
- Hao Chen (4)
- Ivan Damgård (29)
- Vanesa Daza (2)
- Yevgeniy Dodis (2)
- Nico Döttling (1)
- Léo Ducas (3)
- Stefan Dziembowski (2)
- Daniel Escudero (3)
- Serge Fehr (10)
- Matthew K. Franklin (1)
- Rosario Gennaro (1)
- Shafi Goldwasser (1)
- Ignacio Gracia (2)
- Robbert de Haan (4)
- Goichiro Hanaoka (1)
- Martin Hirt (1)
- Dennis Hofheinz (3)
- Hideki Imai (1)
- Yuval Ishai (3)
- Marcel Keller (2)
- Eike Kiltz (5)
- Eyal Kushilevitz (2)
- Gregor Leander (2)
- Philip D. MacKenzie (2)
- Jaume Martí-Farré (2)
- Ueli Maurer (2)
- Diego Mirandola (1)
- Jesper Buus Nielsen (2)
- Carles Padró (7)
- Rafael Pass (1)
- Torben P. Pedersen (1)
- Chris Peikert (2)
- Tal Rabin (1)
- Matthieu Rambaud (1)
- Oded Regev (2)
- Berry Schoenmakers (3)
- Peter Scholl (1)
- Abhi Shelat (1)
- Victor Shoup (6)
- Gabriele Spini (1)
- Martijn Stam (1)
- Jorge Jiménez Urroz (2)
- Vinod Vaikuntanathan (2)
- Benjamin Wesolowski (1)
- Daniel Wichs (2)
- Chaoping Xing (11)
- Chen Yuan (5)
- Moti Yung (1)
- Sarah Zakarias (1)
- Gilles Zémor (1)
- Angela Zottarel (1)