## CryptoDB

### Ivan Damgård

#### Publications

**Year**

**Venue**

**Title**

2021

PKC

Two-round n-out-of-n and Multi-Signatures and Trapdoor Commitment from Lattice
📺
Abstract

Although they have been studied for a long time, distributed signature
protocols have garnered renewed interest in recent years in view of novel
applications to topics like blockchains. Most recent works have focused
on distributed versions of ECDSA or variants of Schnorr signatures,
however, and in particular, little attention has been given to
constructions based on post-quantum secure assumptions like the hardness
of lattice problems. A few lattice-based threshold signature and
multi-signature schemes have been proposed in the literature, but they
either rely on hash-and-sign lattice signatures (which tend to be
comparatively inefficient), use expensive generic transformations, or
only come with incomplete security proofs.
In this paper, we construct several lattice-based distributed signing
protocols with low round complexity following the Fiat--Shamir with
Aborts (FSwA) paradigm of Lyubashevsky (Asiacrypt 2009). Our protocols can be seen as distributed
variants of the fast Dilithium-G signature scheme and the full security proof can
be made assuming the hardness of module SIS and LWE problems. A key step to achieving
security (unexplained in some earlier papers) is to prevent the leakage
that can occur when parties abort after their first message---which can
inevitably happen in the Fiat--Shamir with Aborts setting. We manage to
do so using homomorphic commitments.
Exploiting the similarities between FSwA and Schnorr-style signatures,
our approach makes the most of observations from recent advancements in the
discrete log setting, such as Drijvers et al.'s seminal work on two-round multi-signatures (S&P 2019).
In particular, we observe that the use of commitment not only resolves the
subtle issue with aborts, but also makes it possible to realize secure two-round
n-out-of-n distributed signing and multi-signature
in the plain public key model, by equipping the commitment with a trapdoor feature.
The construction of suitable trapdoor commitment from
lattices is a side contribution of this paper.

2021

CRYPTO

Broadcast-Optimal Two Round MPC with an Honest Majority
📺
Abstract

This paper closes the question of the possibility of two-round MPC protocols achieving different security guarantees with and without the availability of broadcast in any given round. Cohen et al. (Eurocrypt 2020) study this question in the dishonest majority setting; we complete the picture by studying the honest majority setting.
In the honest majority setting, given broadcast in both rounds, it is known that the strongest guarantee — guaranteed output delivery — is achievable (Gordon et al. Crypto 2015). We show that, given broadcast in the first round only, guaranteed output delivery is still achievable. Given broadcast in the second round only, we give a new construction that achieves identifiable abort, and we show that fairness — and thus guaranteed output delivery — are not achievable in this setting. Finally, if only peer-to-peer channels are available, we show that the weakest guarantee — selective abort — is the only one achievable for corruption thresholds t > 1 and for t = 1 and n = 3. On the other hand, it is already known that selective abort can be achieved in these cases. In the remaining cases, i.e., t = 1 and n > 3, it is known (from the work of Ishai et al. at Crypto 2010, and Ishai et al. at Crypto 2015) that guaranteed output delivery (and thus all weaker guarantees) are possible.

2021

ASIACRYPT

Improved single-round secure multiplication using regenerating codes
Abstract

In 2016, Guruswami and Wootters showed Shamir's secret-sharing scheme defined over an extension field has a regenerating property.
Namely, we can compress each share to an element of the base field by applying a linear form, such that the secret is determined by a linear combination of the compressed shares.
Immediately it seemed like an application to improve the complexity of unconditionally secure multiparty computation must be imminent; however, thus far, no result has been published.
We present the first application of regenerating codes to MPC, and show that its utility lies in reducing the number of rounds.
Concretely, we present a protocol that obliviously evaluates a depth-$d$ arithmetic circuit in $d + O(1)$ rounds, in the amortized setting of parallel evaluations, with $o(n^2)$ ring elements communicated per multiplication.
Our protocol makes use of function-dependent preprocessing, and is secure against the maximal adversary corrupting $t < n/2$ parties.
All existing approaches in this setting have complexity $\Omega(n^2)$.
Moreover, we extend some of the theory on regenerating codes to Galois rings.
It was already known that the repair property of MDS codes over fields can be fully characterized in terms of its dual code.
We show this characterization extends to linear codes over Galois rings, and use it to show the result of Guruswami and Wootters also holds true for Shamir's scheme over Galois rings.

2021

TCC

Information-Theoretically Secure MPC against Mixed Dynamic Adversaries
Abstract

In this work we consider information-theoretically secure MPC against an \emph{mixed} adversary who can corrupt $t_p$ parties passively, $t_a$ parties actively, and can make $t_f$ parties fail-stop.
With perfect security, it is known that every function can be computed securely if and only if $3t_a + 2t_p + t_f < n$,
for statistical security the bound is $2t_a + 2t_p + t_f < n$.
These results say that for each given set of parameters $(t_a, t_p, t_f)$ respecting the inequality, there exists a protocol secure against
this particular choice of corruption thresholds.
In this work we consider a \emph{dynamic} adversary. Here, the goal is a \emph{single} protocol that is secure, no matter which set of corruption thresholds $(t_a, t_p, t_f)$ from a certain class is chosen by the adversary. A dynamic adversary can choose a corruption strategy after seeing the protocol and so is much stronger than a standard adversary.
Dynamically secure protocols have been considered before for computational security. Also the information theoretic case has been studied, but only considering non-threshold adversaries, leading to inefficient protocols.
We consider threshold dynamic adversaries and information theoretic security.
For statistical security we show that efficient dynamic secure function evaluation (SFE) is possible if and only if $2t_a + 2t_p + t_f < n$, but any dynamically secure protocol must use
$\Omega(n)$ rounds, even if only fairness is required. Further, general reactive MPC is possible if we assume in addition that $2t_a+2t_f \leq n$,
but fair reactive MPC only requires $2t_a + 2t_p + t_f < n$.
For perfect security we show that both dynamic SFE and verifiable secret sharing (VSS) are impossible if we only assume
$3t_a + 2t_p + t_f < n$ and remain impossible even if we also assume $t_f=0$. In fact even SFE with security with abort is impossible in this case. On the other hand, perfect dynamic SFE with guaranteed output delivery (G.O.D.) is possible when either $t_p = 0$ or $t_a = 0$ i.e. if instead we assume $3t_a+t_f < n$ or $2t_p +t_f < n$. Further, perfect dynamic VSS with G.O.D. is possible under the stronger conditions
$3t_a + 3/2t_f \leq n$ or $2t_p + 2t_f \leq n$. These conditions are also sufficient for perfect reactive MPC. On the other hand, because perfect fair VSS only requires $3t_a+2t_p+t_f< n$, perfect reactive MPC is possible whenever perfect SFE is.

2020

CRYPTO

Black-Box Transformations from Passive to Covert Security with Public Verifiability
📺
Abstract

In the context of secure computation, protocols with security against covert adversaries ensure that any misbehavior by malicious parties will be detected by the honest parties with some constant probability.
As such, these protocols provide better security guarantees than passively secure protocols and, moreover, are easier to construct than protocols with full security against active adversaries.
Protocols that, upon detecting a cheating attempt, allow the honest parties to compute a certificate that enables third parties to verify whether an accused party misbehaved or not are called publicly verifiable.
In this work, we present the first generic compilers for constructing two-party protocols with covert security and public verifiability from protocols with passive security.
We present two separate compilers, which are both fully blackbox in the underlying protocols they use.
Both of them only incur a constant multiplicative factor in terms of bandwidth overhead and a constant additive factor in terms of round complexity on top of the passively secure protocols they use.
The first compiler applies to all two-party protocols that have no private inputs.
This class of protocols covers the important class of preprocessing protocols that are used to setup correlated randomness among parties.
We use our compiler to obtain the first secret-sharing based two-party protocol with covert security and public verifiability.
Notably, the produced protocol achieves public verifiability essentially for free when compared with the best known previous solutions based on secret-sharing that did not provide public verifiability
Our second compiler constructs protocols with covert security and public verifiability for arbitrary functionalities from passively secure protocols.
It uses our first compiler to perform a setup phase, which is independent of the parties' inputs as well as the protocol they would like to execute.
Finally, we show how to extend our techniques to obtain multiparty computation protocols with covert security and public verifiability against arbitrary constant fractions of corruptions.

2020

TCC

Stronger Security and Constructions of Multi-Designated Verifier Signatures
📺
Abstract

Off-the-Record (OTR) messaging is a two-party message authentication protocol that also provides plausible deniability: there is no record that can later convince a third party what messages were actually sent. The challenge in group OTR, is to enable the sender to sign his messages so that group members can verify who sent a message (signatures should be unforgeable, even by group members). Also, we want the off-the-record property: even if some verifiers are corrupt and collude, they should not be able to prove the authenticity of a message to any outsider. Finally, we need consistency, meaning that if any group member accepts a signature, then all of them do.
To achieve these properties it is natural to consider Multi-Designated Verifier Signatures (MDVS). However, existing literature defines and builds only limited notions of MDVS, where (a) the off-the-record property (source hiding) only holds when all verifiers could conceivably collude, and (b) the consistency property is not considered.
The contributions of this paper are two-fold: stronger definitions for MDVS, and new constructions meeting those definitions. We strengthen source-hiding to support any subset of corrupt verifiers, and give the first formal definition of consistency. We build three new MDVS: one from generic standard primitives (PRF, key agreement, NIZK), one with concrete efficiency and one from functional encryption.

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

CRYPTO

Proofs of Replicated Storage Without Timing Assumptions
📺
Abstract

In this paper we provide a formal treatment of proof of replicated storage, a novel cryptographic primitive recently proposed in the context of a novel cryptocurrency, namely Filecoin.In a nutshell, proofs of replicated storage is a solution to the following problem: A user stores a file m on n different servers to ensure that the file will be available even if some of the servers fail. Using proof of retrievability, the user could check that every server is indeed storing the file. However, what if the servers collude and, in order to save on resources, decide to only store one copy of the file? A proof of replicated storage guarantees that, unless the (potentially colluding) servers are indeed reserving the space necessary to store n copies of the file, the user will not accept the proofs. While some candidate proofs of replicated storage have already been proposed, their soundness relies on timing assumptions i.e., the user must reject the proof if the prover does not reply within a certain time-bound.In this paper we provide the first construction of a proof of replication which does not rely on any timing assumptions.

2019

CRYPTO

Communication Lower Bounds for Statistically Secure MPC, With or Without Preprocessing
📺
Abstract

We prove a lower bound on the communication complexity of unconditionally secure multiparty computation, both in the standard model with
$$n=2t+1$$
parties of which t are corrupted, and in the preprocessing model with
$$n=t+1$$
. In both cases, we show that for any
$$g \in \mathbb {N}$$
there exists a Boolean circuit C with g gates, where any secure protocol implementing C must communicate
$$\varOmega (n g)$$
bits, even if only passive and statistical security is required. The results easily extends to constructing similar circuits over any fixed finite field. This shows that for all sizes of circuits, the O(n) overhead of all known protocols when t is maximal is inherent. It also shows that security comes at a price: the circuit we consider could namely be computed among n parties with communication only O(g) bits if no security was required. Our results extend to the case where the threshold t is suboptimal. For the honest majority case, this shows that the known optimizations via packed secret-sharing can only be obtained if one accepts that the threshold is
$$t= (1/2 - c)n$$
for a constant c. For the honest majority case, we also show an upper bound that matches the lower bound up to a constant factor (existing upper bounds are a factor
$$\lg n$$
off for Boolean circuits).

2019

CRYPTO

Stronger Leakage-Resilient and Non-Malleable Secret Sharing Schemes for General Access Structures
📺
Abstract

In this work we present a collection of compilers that take secret sharing schemes for an arbitrary access structure as input and produce either leakage-resilient or non-malleable secret sharing schemes for the same access structure. A leakage-resilient secret sharing scheme hides the secret from an adversary, who has access to an unqualified set of shares, even if the adversary additionally obtains some size-bounded leakage from all other secret shares. A non-malleable secret sharing scheme guarantees that a secret that is reconstructed from a set of tampered shares is either equal to the original secret or completely unrelated. To the best of our knowledge we present the first generic compiler for leakage-resilient secret sharing for general access structures. In the case of non-malleable secret sharing, we strengthen previous definitions, provide separations between them, and construct a non-malleable secret sharing scheme for general access structures that fulfills the strongest definition with respect to independent share tampering functions. More precisely, our scheme is secure against concurrent tampering: The adversary is allowed to (non-adaptively) tamper the shares multiple times, and in each tampering attempt can freely choose the qualified set of shares to be used by the reconstruction algorithm to reconstruct the tampered secret. This is a strong analogue of the multiple-tampering setting for split-state non-malleable codes and extractors.We show how to use leakage-resilient and non-malleable secret sharing schemes to construct leakage-resilient and non-malleable threshold signatures. Classical threshold signatures allow to distribute the secret key of a signature scheme among a set of parties, such that certain qualified subsets can sign messages. We construct threshold signature schemes that remain secure even if an adversary leaks from or tampers with all secret shares.

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.

2019

ASIACRYPT

Efficient UC Commitment Extension with Homomorphism for Free (and Applications)
Abstract

Homomorphic universally composable (UC) commitments allow for the sender to reveal the result of additions and multiplications of values contained in commitments without revealing the values themselves while assuring the receiver of the correctness of such computation on committed values. In this work, we construct essentially optimal additively homomorphic UC commitments from any (not necessarily UC or homomorphic) extractable commitment, while the previous best constructions require oblivious transfer. We obtain amortized linear computational complexity in the length of the input messages and rate 1. Next, we show how to extend our scheme to also obtain multiplicative homomorphism at the cost of asymptotic optimality but retaining low concrete complexity for practical parameters. Moreover, our techniques yield public coin protocols, which are compatible with the Fiat-Shamir heuristic. These results come at the cost of realizing a restricted version of the homomorphic commitment functionality where the sender is allowed to perform any number of commitments and operations on committed messages but is only allowed to perform a single batch opening of a number of commitments. Although this functionality seems restrictive, we show that it can be used as a building block for more efficient instantiations of recent protocols for secure multiparty computation and zero knowledge non-interactive arguments of knowledge.

2018

CRYPTO

Yet Another Compiler for Active Security or: Efficient MPC Over Arbitrary Rings
📺
Abstract

We present a very simple yet very powerful idea for turning any passively secure MPC protocol into an actively secure one, at the price of reducing the threshold of tolerated corruptions.Our compiler leads to a very efficient MPC protocols for the important case of secure evaluation of arithmetic circuits over arbitrary rings (e.g., the natural case of $${\mathbb {Z}}_{2^{\ell }}\!$$) for a small number of parties. We show this by giving a concrete protocol in the preprocessing model for the popular setting with three parties and one corruption. This is the first protocol for secure computation over rings that achieves active security with constant overhead.

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.

2018

PKC

Compact Zero-Knowledge Proofs of Small Hamming Weight
Abstract

We introduce a new technique that allows to give a zero-knowledge proof that a committed vector has Hamming weight bounded by a given constant. The proof has unconditional soundness and is very compact: It has size independent of the length of the committed string, and for large fields, it has size corresponding to a constant number of commitments. We show five applications of the technique that play on a common theme, namely that our proof allows us to get malicious security at small overhead compared to semi-honest security: (1) actively secure k-out-of-n OT from black-box use of 1-out-of-2 OT, (2) separable accountable ring signatures, (3) more efficient preprocessing for the TinyTable secure two-party computation protocol, (4) mixing with public verifiability, and (5) PIR with security against a malicious client.

2018

TCC

Continuous NMC Secure Against Permutations and Overwrites, with Applications to CCA Secure Commitments
Abstract

Non-Malleable Codes (NMC) were introduced by Dziembowski, Pietrzak and Wichs in ICS 2010 as a relaxation of error correcting codes and error detecting codes. Faust, Mukherjee, Nielsen, and Venturi in TCC 2014 introduced an even stronger notion of non-malleable codes called continuous non-malleable codes where security is achieved against continuous tampering of a single codeword without re-encoding.We construct information theoretically secure CNMC resilient to bit permutations and overwrites, this is the first Continuous NMC constructed outside of the split-state model.In this work we also study relations between the CNMC and parallel CCA commitments. We show that the CNMC can be used to bootstrap a Self-destruct parallel CCA bit commitment to a Self-destruct parallel CCA string commitment, where Self-destruct parallel CCA is a weak form of parallel CCA security. Then we can get rid of the Self-destruct limitation obtaining a parallel CCA commitment, requiring only one-way functions.

2017

EUROCRYPT

2015

EUROCRYPT

2014

EUROCRYPT

2014

EPRINT

2013

ASIACRYPT

2010

EPRINT

Perfectly Secure Oblivious RAM Without Random Oracles
Abstract

We present an algorithm for implementing a secure oblivious
RAM where the access pattern is perfectly hidden in the information
theoretic sense, without assuming that the CPU has access to a random
oracle. In addition we prove a lover bound on the amount of randomness
needed for information theoretically secure oblivious RAM.

2010

CRYPTO

2010

EUROCRYPT

2010

EPRINT

Perfectly Secure Multiparty Computation and the Computational Overhead of Cryptography
Abstract

We study the following two related questions:
- What are the minimal computational resources required for general secure multiparty computation in the presence of an honest majority?
- What are the minimal resources required for two-party primitives such as zero-knowledge proofs and general secure two-party computation?
We obtain a nearly tight answer to the first question by presenting a perfectly secure protocol which allows $n$ players to evaluate an arithmetic circuit of size $s$ by performing a total of $\O(s\log s\log^2 n)$ arithmetic operations, plus an additive term which depends (polynomially) on $n$ and the circuit depth, but only logarithmically on $s$. Thus, for typical large-scale computations whose circuit width is much bigger than their depth and the number of players, the amortized overhead is just polylogarithmic in $n$ and $s$. The protocol provides perfect security with guaranteed output delivery in the presence of an active, adaptive adversary corrupting a $(1/3-\epsilon)$ fraction of the players, for an arbitrary constant $\epsilon>0$ and sufficiently large $n$. The best previous protocols in this setting could only offer computational security with a computational overhead of $\poly(k,\log n,\log s)$, where $k$ is a computational security parameter, or perfect security with a computational overhead of $\O(n\log n)$.
We then apply the above result towards making progress on the second question. Concretely, under standard cryptographic assumptions, we obtain zero-knowledge proofs for circuit satisfiability with $2^{-k}$ soundness error in which the amortized computational overhead per gate is only {\em polylogarithmic} in $k$, improving over the $\omega(k)$ overhead of the best previous protocols. Under stronger cryptographic assumptions, we obtain similar results for general secure two-party computation.

2010

EPRINT

Multiparty Computation for Dishonest Majority: from Passive to Active Security at Low Cost
Abstract

Multiparty computation protocols have been known for more than twenty years now, but due to their lack of efficiency their use is still limited in real-world applications: the goal of this paper is the design of efficient two and multi party computation protocols aimed to fill the gap between theory and practice. We propose a new protocol to securely evaluate reactive arithmetic circuits, that offers security against an active adversary in the universally composable security framework. Instead of the ``do-and-compile'' approach (where the parties use zero-knowledge proofs to show that they are following the protocol) our key ingredient is an efficient version of the ``cut-and-choose'' technique, that allow us to achieve active security for just a (small) constant amount of work more than for passive security.

2008

EPRINT

Multiparty Computation Goes Live
Abstract

In this note, we briefly report on the first large-scale and practical application of multiparty computation, which took place in January 2008.

2008

EPRINT

Efficient Conversion of Secret-shared Values Between Different Fields
Abstract

We show how to effectively convert a secret-shared bit $b$ over a
prime field to another field. If initially given a random replicated
secret share this conversion can be done by the cost of revealing
one secret shared value. By using a pseudo-random function it is
possible to convert arbitrary many bit values from one initial
random replicated share. Furthermore, we generalize the conversion to
handle general values of a bounded size.

2008

EPRINT

A correction to ``Efficient and Secure Comparison for On-Line Auctions''
Abstract

In this note, we describe a correction to the cryptosystem proposed by the authors in "Efficient and Secure Comparison for On-Line Auctions". Although the correction is small and does not affect the performance of
the protocols proposed in that paper, it is necessary as the cryptosystem is not secure without it.

2008

EPRINT

Essentially Optimal Universally Composable Oblivious Transfer
Abstract

Oblivious transfer is one of the most important cryptographic primitives, both for theoretical and practical reasons and several protocols were proposed during the years. We provide the first oblivious transfer protocol which is simultaneously optimal on the following list of parameters:
Security: it has universal composition.
Trust in setup assumptions: only one of the parties needs to trust the setup and some setup is needed for UC security.
Trust in computational assumptions: only one of the parties needs to trust a computational assumption.
Round complexity: it uses only two rounds.
Communication complexity: it communicates O(1) group elements to transfer one out of two group elements.
The Big-O notation hides 32, meaning that the communication is probably not optimal, but is essentially optimal in that the overhead is at least constant.
Our construction is based on pairings, and we assume the presence of a key registration authority.

2007

EPRINT

Non-Interactive Proofs for Integer Multiplication
Abstract

We present two universally composable and practical
protocols by which a dealer can, verifiably and
non-interactively, secret-share an integer among a set of players.
Moreover, at small extra cost and using a distributed verifier proof,
it can be shown in zero-knowledge
that three shared integers $a,b,c$ satisfy $ab =c$. This implies by
known reductions non-interactive zero-knowledge proofs that a shared
integer is in a given interval, or that one secret integer is larger
than another. Such primitives are useful, e.g., for supplying
inputs to a multiparty computation protocol, such as an auction or
an election. The protocols use various set-up assumptions, but do
not require the random oracle model.

2007

EPRINT

Secure Identification and QKD in the Bounded-Quantum-Storage Model
Abstract

We consider the problem of secure identification: user U proves to server S that he knows an agreed (possibly low-entropy) password w, while giving away as little information on w as possible, namely the adversary can exclude at most one possible password for each execution of the scheme. We propose a solution in the bounded-quantum-storage model, where U and S may exchange qubits, and a dishonest party is assumed to have limited quantum memory. No other restriction is posed upon the adversary.
An improved version of the proposed identification scheme is also secure against a man-in-the-middle attack, but requires U and S to additionally share a high-entropy key k. However, security is still guaranteed if one party loses k to the attacker but notices the loss. In both versions of the scheme, the honest participants need no quantum memory, and noise and imperfect quantum sources can be tolerated. The schemes compose sequentially, and w and k can securely be re-used.
A small modification to the identification scheme results in a quantum-key-distribution (QKD) scheme, secure in the bounded-quantum-storage model, with the same re-usability properties of the keys, and without assuming authenticated channels. This is in sharp contrast to known QKD schemes (with unbounded adversary) without authenticated channels, where authentication keys must be updated, and unsuccessful executions can cause the parties to run out of keys.

2007

EPRINT

A Tight High-Order Entropic Quantum Uncertainty Relation With Applications
Abstract

We derive a new entropic quantum uncertainty relation involving min-entropy. The relation is tight and can be applied in various quantum-cryptographic settings.
Protocols for quantum 1-out-of-2 Oblivious Transfer and quantum Bit Commitment are presented and the uncertainty relation is used to prove the security of these protocols in the bounded-quantum-storage model according to new strong security definitions.
As another application, we consider the realistic setting of Quantum Key Distribution (QKD) against quantum-memory-bounded eavesdroppers. The uncertainty relation allows to prove the security of QKD protocols in this setting while tolerating considerably higher error rates compared to the standard model with unbounded adversaries. For instance, for the six-state protocol with one-way communication, a bit-flip error rate of up to 17% can be tolerated (compared to 13% in the standard model).
Our uncertainty relation also yields a lower bound on the min-entropy key uncertainty against known-plaintext attacks when quantum ciphers are composed. Previously, the key uncertainty of these ciphers was only known with respect to Shannon entropy.

2007

EPRINT

Isolated Proofs of Knowledge and Isolated Zero Knowledge
Abstract

We introduce a new notion called $\ell$-isolated proofs of knowledge
($\ell$-IPoK). These are proofs of knowledge where a cheating prover
is allowed to exchange up to $\ell$ bits of communication with some
external adversarial environment during the run of the proof.
Without any additional setup assumptions, no witness hiding protocol can be an $\ell$-IPoK for \emph{unbounded} values of $\ell$.
However, for any \emph{pre-defined} threshold $\ell$, and any relation in NP and we construct
an $\ell$-IPoK protocol for that relation. The resulting protocols
are zero knowledge (ZK) in the standard sense, i.e.,
w.r.t. a verifier that communicates only with the prover during the proof.
The cost of having a large threshold $\ell$ is a large communication complexity of the constructed protocol.
We analyze these costs and present a solution that is asymptotically optimal.
If a cheating verifier is allowed to communicate arbitrarily with an
external environment, it is not possible to construct an $\ell$-IPoK that
is also ZK with respect to such a verifier. As another new notion,
we define $\ell$-isolated zero knowledge ($\ell$-IZK) where the
verifier is $\ell$-isolated. For every relation in NP and
every $\ell$, we construct an $\ell$-IPoK protocol that is
also $\ell$-IZK.
We describe several applications of $\ell$-IPoK protocols
under the physical assumption that one can $\ell$-isolate a prover for
the duration of the proof phase. Firstly, we can use a witness
indistinguishable (WI) $\ell$-IPoK to prevent ``man-in-the-middle''
attacks on identification schemes. Prior results for this scenario
required all verifiers to register keys under a PKI, or the ability to fully
isolate the prover. Secondly, a partially isolated prover can register a public key and use a WI $\ell$-IPoK to prove knowledge of the corresponding secret key to another party acting as a verifier. This allows us to set up a PKI where the key registrant does not need to trust the Certificate Authority. The PKI is not perfect since the proof is only witness indistinguishable and not zero knowledge. In a companion paper, we show how to set up such a PKI and use it to implement arbitrary multiparty computation securely in the UC framework without relying on any trusted third parties.

2007

EPRINT

Universally Composable Multiparty Computation with Partially Isolated Parties
Abstract

It is well known that universally composable multiparty computation
cannot, in general, be achieved in the standard model without setup
assumptions when the adversary can corrupt an arbitrary number of
players. One way to get around this problem is by having a trusted
third party generate some global setup such as a common reference
string (CRS) or a public key infrastructure (PKI). Recently, an
alternative solution was proposed by Katz in \cite{Katz}, suggesting
that one may rely on physical assumptions rather than trusted third
parties. Concretely, the solution assumed it physically possible to
construct tamper proof hardware tokens which can be run in complete
isolation from the surrounding environment. Here we improve upon the
work of \cite{Katz} by constructing a scheme in which the tokens
only need to be partially isolated and may have some {\em limited
communication with the environment}. In addition we improve on
Katz's work by presenting a scheme which is secure against
\emph{adaptive adversaries} and is based on \emph{general
cryptographic assumptions}. We also consider an alternative
scenario, in which there are some trusted third parties but no
single such party is trusted by all of the players. This compromise
allows us to limit the use of the physical set-up and hence might be
preferred in practice.

2006

JOFC

2006

EPRINT

Linear Integer Secret Sharing and Distributed Exponentiation
Abstract

We introduce the notion of Linear Integer Secret-Sharing (LISS) schemes, and show constructions of such schemes for any access structure. We show that any LISS scheme can be used to build a secure distributed protocol for exponentiation in any group. This implies, for instance, distributed RSA protocols for arbitrary access structures and with arbitrary public exponents.

2006

EPRINT

RFID Security: Tradeoffs between Security and Efficiency
Abstract

Recently, Juels and Weis defined strong privacy for RFID tags. We add to this definition a completeness and a soundness requirement, i.e., a reader should accept valid tags and only such tags. For the case where tags hold independent keys, we prove a conjecture by Juels and Weis, namely in a strongly private and sound RFID system using only symmetric cryptography, a reader must access virtually all keys in the system when reading a tag.
It was already known from work by Molnar et al. that when keys are dependent,
the reader only needs to access a logarithmic number of keys, but at a cost in terms of privacy: for that system, strong privacy is lost if an adversary corrupts only a single tag. We propose protocols offering a new range of tradeoffs between security and efficiency. For instance the number of keys accessed by a reader to read a tag can be significantly smaller than the number of tags while retaining security, as long as we assume suitable limitations on the adversary.

2005

EPRINT

Unclonable Group Identification
Abstract

We introduce and motivate the concept of unclonable group identification, that provides maximal protection against sharing of identities while still protecting the anonymity of users. We prove that the notion can be realized from any one-way function and suggest a more efficient implementation based on specific assumptions.

2005

EPRINT

Constant-Round Multiparty Computation Using a Black-Box Pseudorandom Generator
Abstract

We present a constant-round protocol for general secure multiparty
computation which makes a {\em black-box} use of a pseudorandom
generator. In particular, the protocol does not require expensive
zero-knowledge proofs and its communication complexity does not
depend on the computational complexity of the underlying
cryptographic primitive. Our protocol withstands an active, adaptive
adversary corrupting a minority of the parties. Previous
constant-round protocols of this type were only known in the
semi-honest model or for restricted classes of functionlities.

2005

EPRINT

Universally Composable Disk Encryption Schemes
Abstract

We propose a formalization of the security of transparent harddisk-encryption using the universal composability framework. We point out that several commercially available schemes for transparent hard disk encryption are built on principles that limit security, and we propose schemes for disk encryption with passive and active security, respectively. As for the efficiency of the schemes, security against active attacks can be obtained with a constant factor overhead in space and a logarithmic overhead in time. Finally, we also also sketch an actively secure scheme that provides some amount of security, even if the adversary is given temporary access to the internal state of the encryption device used.

2005

EPRINT

How to Split a Shared Secret into Shared Bits in Constant-Round
Abstract

We show that if a set of players hold shares of a value $a\in Z_p$
for some prime $p$ (where the set of shares is written $[a]_p$), it
is possible to compute, in constant round and with unconditional
security, sharings of the bits of $a$, i.e.~compute sharings
$[a_0]_p, \ldots, [a_{l-1}]_p$ such that $l = \lceil \log_2(p)
\rceil$, $a_0, \ldots, a_{l-1} \in \{0,1\}$ and $a =
\sum_{i=0}^{l-1} a_i 2^i$. Our protocol is secure against active
adversaries and works for any linear secret sharing scheme with a
multiplication protocol.
This result immediately implies solutions to other long-standing
open problems, such as constant-round and unconditionally secure
protocols for comparing shared numbers and deciding whether a shared
number is zero.
The complexity of our protocol is $O(l \log(l))$
invocations of the multiplication protocol for the underlying secret
sharing scheme, carried out in $O(1)$.

2005

EPRINT

Cryptography In the Bounded Quantum-Storage Model
Abstract

We initiate the study of two-party cryptographic primitives with unconditional security, assuming that the adversary's {\em quantum}memory is of bounded size. We show that oblivious transfer and bit
commitment can be implemented in this model using protocols where honest parties need no quantum memory, whereas an adversarial player needs quantum memory of size at least $n/2$ in order to break the protocol, where $n$ is the number of qubits transmitted. This is in sharp contrast to the classical bounded-memory model, where we can only tolerate adversaries with memory of size quadratic in honest players' memory size. Our protocols are efficient, non-interactive and can be implemented using today's technology. On the technical side, a new entropic uncertainty relation involving min-entropy is established.

2005

EPRINT

Oblivious Transfer and Linear Functions
Abstract

We study unconditionally secure 1-out-of-2 Oblivious Transfer (1-2 OT). We first point out that a standard security requirement for 1-2 OT of bits, namely that the receiver only learns one of the bits sent, holds if and only if the receiver has no information on the XOR of the two bits. We then generalize this to 1-2 OT of strings and show that the security can be characterized in terms of binary linear functions. More precisely, we show that the receiver learns only one of the two strings sent if and only if he has no information on the result of
applying any binary linear function (which non-trivially depends on both inputs) to the two strings.
We then argue that this result not only gives new insight into the nature of 1-2 OT, but it in particular provides a very powerful tool for analyzing 1-2 OT protocols. We demonstrate this by showing that with our characterization at hand, the reduceability of 1-2 OT (of strings) to a wide range of weaker primitives follows by a very simple argument. This is in sharp contrast to previous literature, where reductions of 1-2 OT to weaker flavors have rather complicated and sometimes even incorrect proofs.

2004

EUROCRYPT

2004

EPRINT

On the Key-Uncertainty of Quantum Ciphers and the Computational Security of One-way Quantum Transmission
Abstract

We consider the scenario where Alice wants to send a secret(classical) $n$-bit message to Bob using a classical key, and where
only one-way transmission from Alice to Bob is possible. In this
case, quantum communication cannot help to obtain perfect secrecy
with key length smaller then $n$. We study the question of whether
there might still be fundamental differences between the case where
quantum as opposed to classical communication is used. In this
direction, we show that there exist ciphers with perfect security producing quantum ciphertext where, even if an adversary knows the
plaintext and applies an optimal measurement on the ciphertext, his
Shannon uncertainty about the key used is almost maximal. This is in
contrast to the classical case where the adversary always learns $n$
bits of information on the key in a known plaintext attack. We also
show that there is a limit to how different the classical and
quantum cases can be: the most probable key, given matching plain-
and ciphertexts, has the same probability in both the quantum and
the classical cases. We suggest an application of our results in
the case where only a short secret key is available and the message
is much longer.

2003

CRYPTO

2003

EPRINT

Non-interactive and Reusable Non-malleable Commitment Schemes
Abstract

We consider non-malleable (NM) and universally composable (UC)
commitmentschemes in the common reference string (CRS) model.
We show how to construct non-interac\-tive NM commitments that
remain non-malleable even if the adversary has access to an
arbitrary number of commitments from honest players - rather than
one, as in several previous schemes. We show this is a strictly
stronger security notion. Our construction is the first
non-interactive scheme achieving this that can be based
on the minimal assumption of existence of one-way
functions. But it can also be instantiated in a very efficient
version based on the strong RSA assumption. For UC commitments,
we show that existence of a UC commitment scheme in the CRS model
(interactive or not) implies key exchange and - for a uniform
reference string - even implies oblivious transfer. This indicates
that UC commitment is a strictly stronger primitive than NM. Finally,
we show that our strong RSA based construction can be used to improve
the most efficient known UC commitment scheme so it can work with
a CRS of size independent of the number of players, without loss of
efficiency.

2002

CRYPTO

2002

CRYPTO

2002

EPRINT

Generic Lower Bounds for Root Extraction and Signature Schemes in General Groups
Abstract

We study the problem of root extraction in finite Abelian groups, where the
group order is unknown. This is a
natural generalization of the problem of decrypting RSA ciphertexts.
We study the complexity of this problem for generic algorithms, that is,
algorithms that work for any group and do not use any special properties
of the group at hand.
We prove an exponential lower bound on the generic
complexity of root extraction, even if the algorithm can choose the
"public exponent"
itself. In other words, both the standard and the strong RSA assumption
are provably true w.r.t. generic algorithms.
The results hold for arbitrary groups, so security w.r.t. generic attacks
follows for any cryptographic construction based on root extracting.
As an example of this, we revisit Cramer-Shoup signature scheme.
We modify the scheme such that it becomes a generic
algorithm. This allows us to
implement it in RSA groups without the original restriction that the
modulus must be a product
of safe primes. It can also be implemented in class groups.
In all cases, security follows from a
well defined complexity assumption (the strong root assumption),
without relying on random
oracles, and the assumption is shown to be true w.r.t. generic attacks.

2001

EPRINT

On adaptive vs. non-adaptive security of multiparty protocols
Abstract

Security analysis of multiparty cryptographic protocols distinguishes
between two types of adversarial settings: In the non-adaptive
setting, the set of corrupted parties is chosen in advance, before the
interaction begins. In the adaptive setting, the adversary chooses
who to corrupt during the course of the computation. We study the
relations between adaptive security (i.e., security in the adaptive
setting) and non-adaptive security, according to two definitions and
in several models of computation. While affirming some prevailing
beliefs, we also obtain some unexpected results. Some highlights of
our results are:
o According to the definition of Dodis-Micali-Rogaway (which is set in
the information-theoretic model), adaptive and non-adaptive security
are equivalent. This holds for both honest-but-curious and Byzantine
adversaries, and for any number of parties.
o According to the definition of Canetti, for honest-but-curious
adversaries, adaptive security is equivalent to non-adaptive
security when the number of parties is logarithmic, and is strictly
stronger than non-adaptive security when the number of parties is
super-logarithmic. For Byzantine adversaries, adaptive security is
strictly stronger than non-adaptive security, for any number of
parties.

2001

EPRINT

An Integer Commitment Scheme based on Groups with Hidden Order
Abstract

We present a commitment scheme allowing commitment to arbitrary size integers, based on any Abelian group with certain properties, most importantly that it is hard for the committer to compute its order. Potential examples include RSA and class groups. We also give efficient zero-knowledge protocols for proving knowledge of the contents of a commitment and for verifying multiplicative relations over the integers on committed values. This means that our scheme can support, for instance, the efficent interval proofs of Boudot. The scheme can be seen as a modification and a generalization of an earlier scheme of Fujisaki and Okamoto(FO), and in particular our results show that we can use a much larger class of RSA moduli than the safe prime products proposed by FO. Also, we correct some mistakes in the proofs of FO and give what appears to be the first multiplication protocol for a Fujisaki/Okamoto-like scheme with a complete proof of soundness.

2001

EPRINT

Perfect Hiding and Perfect Binding Universally Composable Commitment Schemes with Constant Expansion Factor
Abstract

Canetti and Fischlin have recently proposed the security notion {\em
universal composability} for commitment schemes and provided two
examples. This new notion is very strong. It guarantees that security
is maintained even when an unbounded number of copies of the scheme
are running concurrently, also it guarantees non-malleability,
resilience to selective decommitment, and security against adaptive
adversaries. Both of their schemes uses $\Theta(k)$ bits to commit to
one bit and can be based on the existence of trapdoor commitments and
non-malleable encryption.
We present new universally composable commitment schemes based on the
Paillier cryptosystem and the Okamoto-Uchiyama cryptosystem. The
schemes are efficient: to commit to $k$ bits, they use a constant
number of modular exponentiations and communicates $O(k)$
bits. Further more the scheme can be instantiated in either perfectly
hiding or perfectly binding versions. These are the first schemes to
show that constant expansion factor, perfect hiding, and perfect
binding can be obtained for universally composable commitments.
We also show how the schemes can be applied to do efficient
zero-knowledge proofs of knowledge that are universally composable.

2001

EPRINT

An Extended Quadratic Frobenius Primality Test with Average Case Error Estimates
Abstract

We present an Extended Quadratic Frobenius Primality Test (EQFT), which is related to the Miller-Rabin test and the Quadratic Frobenius test (QFT) by Grantham. EQFT is well-suited for generating large, random prime numbers since on a random input number, it takes time about equivalent to 2 Miller-Rabin tests, but has much smaller error probability. EQFT extends QFT by verifying additional algebraic properties related to the existence of elements of order 3 and 4. We obtain a simple closed expression that upper bounds the probability of acceptance for any input number. This in turn allows us to give strong bounds on the average-case behaviour of the test: consider the algorithm that repeatedly chooses random odd $k$ bit numbers, subjects them to $t$ iterations of our test and outputs the first one found that passes all tests. We obtain numeric upper bounds for the error probability of this algorithm as well as a general closed expression bounding the error. For instance, it is at most $2^{-143}$ for $k=500, t=2$. Compared to earlier similar results for the Miller-Rabin test, the results indicates that our test in the average case has the effect of 9 Miller-Rabin tests, while only taking time equivalent to about 2 such tests. We also give bounds for the error in case a prime is sought by incremental search from a random starting point. While EQFT is slower than the average case on a small set of inputs, we present a variant that is always fast, i.e.takes time about 2 Miller-Rabin tests. The variant has slightly larger worst case error probability than EQFT, but still improves on previous proposed tests.

2000

ASIACRYPT

2000

EPRINT

Efficient Protocols based on Probabilistic Encryption using Composite Degree Residue Classes
Abstract

We study various applications and variants of Paillier's probabilistic
encryption scheme. First, we propose a threshold variant of the scheme,
and also zero-knowledge protocols for proving that a given ciphertext
encodes a given plaintext, and for verifying multiplication of encrypted values.
We then show how these building blocks can be used for applying the
scheme to efficient electronic voting. This reduces dramatically the work needed to compute the final result of an election, compared to the previously best known schemes. We show how the
basic scheme for a yes/no vote can be easily adapted to casting a
vote for up to $t$ out of $L$ candidates. The same basic building blocks can also be adapted to provide receipt-free elections, under appropriate physical assumptions. The scheme for 1 out of $L$ elections can be optimised such that for a certain range of parameter values, a ballot has size only $O(\log L)$ bits.
Finally, we propose a variant of the encryption scheme, that allows
reducing the expansion factor of Paillier's scheme from 2 to almost 1.

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

EUROCRYPT

1999

EPRINT

An error in the mixed adversary protocol by Fitzi, Hirt and Maurer
Abstract

We point out an error in the multiparty computation protocol for mixed
adversaries and zero error from the Crypto 98 paper by Fitzi, Hirt and
Maurer. We show that the protocol only works under a stronger
requirement on the adversary than the one claimed. Hence the bound on
the adversary's corruption capability given there is not tight.
Subsequent work has shown, however, a new bound which is indeed tight.

1999

EPRINT

Verifiable Encryption and Applications to Group Signatures and Signature Sharing
Abstract

We generalize and improve the security and efficiency of the
verifiable encryption scheme of Asokan et al., such that it can rely
on more general assumptions, and can be proven secure without
assuming random oracles. We show a new application of verifiable
encryption to group signatures with separability, these schemes do
not need special purpose keys but can work with a wide range of
signature, identification, and encryption schemes already in use.
Finally, we extend our basic primitive to verifiable threshold and
group encryption. By encrypting digital signatures this way, one
gets new solutions to the verifiable signature sharing problem.

1999

EPRINT

Concurrent Zero-Knowledge is Easy in Practice
Abstract

We show that if any one-way function exists, then 3-round concurrent
zero-knowledge arguments for all NP problems can be built in a model
where a short auxiliary string with a prescribed distribution is
available to the players. We also show that all known efficient
identification schemes using specialized assumptions can be modified
to work in this model with no essential loss of efficiency. We argue
that the assumptions of the model will be satisfied in most practical
scenarios where public key cryptography is used, in particular our
construction works given any secure public key
infrastructure. Finally, we point out that in a model with
preprocessing (and no auxiliary string) proposed earlier, concurrent
zero-knowledge for NP can be based on any one-way function.

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

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.

1993

CRYPTO

1992

EUROCRYPT

1992

EUROCRYPT

1988

CRYPTO

1987

CRYPTO

#### Program Committees

- Eurocrypt 2019
- Crypto 2017
- TCC 2013
- Crypto 2012
- Eurocrypt 2010
- TCC 2009
- TCC 2007
- Crypto 2006
- Eurocrypt 2004
- Asiacrypt 2003
- Eurocrypt 2002
- Asiacrypt 2000
- Crypto 1999
- Crypto 1997
- Eurocrypt 1996
- Eurocrypt 1993
- Crypto 1992
- Eurocrypt 1990 (Program chair)
- Eurocrypt 1988

#### Coauthors

- Mark Abspoel (3)
- Divesh Aggarwal (1)
- Jesús F. Almansa (1)
- Benny Applebaum (1)
- Carsten Baum (2)
- Eli Ben-Sasson (2)
- Iddo Ben-Tov (1)
- Rikke Bendlin (2)
- Iddo Bentov (1)
- Peter Bogetoft (1)
- Joan Boyar (2)
- Jørgen Brandt (5)
- Gilles Brassard (1)
- Ernest F. Brickell (1)
- Jan Camenisch (2)
- Ran Canetti (3)
- Ignacio Cascudo (5)
- David Chaum (4)
- Lidong Chen (2)
- Dan Lund Christensen (1)
- Gil Cohen (1)
- Ronald Cramer (30)
- Claude Crépeau (1)
- Morten Dahl (1)
- Kasper Damgård (1)
- Bernardo Machado David (2)
- Bernardo David (3)
- Yvo Desmedt (1)
- Nico Döttling (3)
- Rafael Dowsley (1)
- Kasper Dupont (4)
- Frédéric Dupuis (1)
- Stefan Dziembowski (5)
- Daniel Escudero (5)
- Oriol Farràs (1)
- Sebastian Faust (3)
- Nelly Fazio (1)
- Serge Fehr (12)
- Matthias Fitzi (3)
- Gudmund Skovbjerg Frandsen (2)
- Eiichiro Fujisaki (2)
- Chaya Ganesh (1)
- Martin Geisler (4)
- Irene Giacomelli (4)
- Oded Goldreich (1)
- Jeroen van de Graaf (2)
- Jens Groth (1)
- Helene Haagh (2)
- Robbert de Haan (1)
- Carmit Hazay (1)
- Martin Hirt (1)
- Yuval Ishai (14)
- Thomas Jakobsen (1)
- Mads Jurik (3)
- Tomasz Kazana (1)
- Marcel Keller (2)
- Joe Kilian (1)
- Eike Kiltz (2)
- Lars R. Knudsen (2)
- Jonas Kölker (1)
- Maciej Koprowski (3)
- Mikkel Krøigaard (5)
- Mikkel Krøigaard (1)
- Felipe Lacerda (1)
- Peter Landrock (4)
- Kasper Green Larsen (2)
- Rasmus Lauritsen (1)
- Carolin Lunemann (2)
- Ji Luo (1)
- Philip D. MacKenzie (2)
- Bernardo Magri (1)
- Tal Malkin (3)
- Ueli Maurer (2)
- Sigurd Meldgaard (2)
- Rebekah Mercer (1)
- Gert Læssøe Mikkelsen (2)
- Peter Bro Miltersen (1)
- Kirill Morozov (1)
- Pratyay Mukherjee (2)
- David Naccache (1)
- Antonio Nicolosi (1)
- Janus Dam Nielsen (1)
- Michael Nielsen (3)
- Kurt Nielsen (2)
- Jesper Buus Nielsen (37)
- Anca Nitulescu (1)
- Peter Sebastian Nordholt (1)
- Maciej Obremski (2)
- Sabine Oechsner (1)
- Tatsuaki Okamoto (1)
- Claudio Orlandi (12)
- Rafail Ostrovsky (1)
- Jakob Pagter (1)
- Sunoo Park (1)
- Valerio Pastro (1)
- Thomas Brochmann Pedersen (3)
- Michael Østergaard Pedersen (3)
- Torben P. Pedersen (7)
- René Peralta (1)
- Birgit Pfitzmann (2)
- Antigoni Polychroniadou (2)
- Erick Purwanto (1)
- Tal Rabin (1)
- Varun Raj (1)
- Matthieu Rambaud (1)
- Samuel Ranellucci (3)
- Vanishree Rao (1)
- Michael Raskin (1)
- Divya Ravi (2)
- Ran Raz (1)
- Renato Renner (2)
- João Ribeiro (1)
- Noga Ron-Zewi (2)
- Adi Rosén (1)
- Ron D. Rothblum (1)
- Louis Salvail (14)
- Alessandra Scafuro (1)
- Christian Schaffner (8)
- Berry Schoenmakers (1)
- Peter Scholl (2)
- Michael Schwartzbach (1)
- Mark Simkin (4)
- Luisa Siniscalchi (2)
- Nigel P. Smart (1)
- Adam Smith (1)
- Gabriele Spini (1)
- Akira Takahashi (1)
- Rune Thorbek (5)
- Mehdi Tibouchi (1)
- Tomas Toft (5)
- Roberto Trifiletti (1)
- Daniele Venturi (2)
- Daniel Wichs (4)
- Avi Wigderson (1)
- Chaoping Xing (4)
- Sophia Yakoubov (2)
- Chen Yuan (3)
- Sarah Zakarias (5)
- Rasmus Winther Zakarias (1)
- Lior Zichron (1)
- Angela Zottarel (1)