Ivan B. Damgård
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Ivan B. Damgård has a total of 6 co-authors. Here are the top co-authors by number of shared publications:
Birgit Pfitzmann
2 shared publications- Birgit Pfitzmann
Institut für Informatik, Universität Hildesheim, Hildesheim, Germany
1 shared publication - Ronald Cramer
ETH Zurich
1 shared publication Torben P. Pedersen
1 shared publication- Torben P. Pedersen
Cryptomathic, Aarhus C, Denmark
1 shared publication - Ueli Maurer
ETH Zurich
1 shared publication
Latest Publications
- Open Access
- 20 June 1997
- Published by Det Kgl. Bibliotek/Royal Danish Library in BRICS Report Series
- Vol. 4 (50)
Sequential Iteration of Interactive Arguments and an Efficient Zero-Knowledge Argument for NP
We study the behavior of interactive arguments under sequential iteration, in particular how this affects the error probability. This problem turns out to be more complex than one might expect from the fact that for interactive proofs, the error trivially decreases exponentially in the number of iterations.In particular, we study the typical efficient case where the iterated protocol is based on a single instance of a computational problem. This is not a special case of independentiterations of an entire protocol, and real exponential decrease of the error cannot be expected, but nevertheless, for practical applications, one needs concrete relationsbetween the complexity and error probability of the underlying problem and that of the iterated protocol. We show how this problem can be formalized and solved using thetheory of proofs of knowledge. We also prove that in the non-uniform model of complexity the error probabilityof independent iterations of an argument does indeed decrease exponentially - to our knowledge this is the first result about a strictly exponentially small error probability in a computational cryptographic security property. As an illustration of our first result, we present a very efficient zero-knowledge argumentfor circuit satisfiability, and thus for any NP problem, based on any collision-intractable hash function. Our theory applies to show the soundness of this protocol. Using an efficient hash function such as SHA-1, the protocol can handle about 20000 binary gates per second at an error level of 2^−50.Keywords -- Interactive proofs, arguments, proofs of knowledge, computational security,efficient general primitives, multi-bit commitment, statistical zero-knowledge.
- 20 June 1997
- Published by Det Kgl. Bibliotek/Royal Danish Library in BRICS Report Series
- Vol. 4 (50)
Open AccessSequential Iteration of Interactive Arguments and an Efficient Zero-Knowledge Argument for NP
We study the behavior of interactive arguments under sequential iteration, in particular how this affects the error probability. This problem turns out to be more complex than one might expect from the fact that for interactive proofs, the error trivially decreases exponentially in the number of iterations.In particular, we study the typical efficient case where the iterated protocol is based on a single instance of a computational problem. This is not a special case of independentiterations of an entire protocol, and real exponential decrease of the error cannot be expected, but nevertheless, for practical applications, one needs concrete relationsbetween the complexity and error probability of the underlying problem and that of the iterated protocol. We show how this problem can be formalized and solved using thetheory of proofs of knowledge. We also prove that in the non-uniform model of complexity the error probabilityof independent iterations of an argument does indeed decrease exponentially - to our knowledge this is the first result about a strictly exponentially small error probability in a computational cryptographic security property. As an illustration of our first result, we present a very efficient zero-knowledge argumentfor circuit satisfiability, and thus for any NP problem, based on any collision-intractable hash function. Our theory applies to show the soundness of this protocol. Using an efficient hash function such as SHA-1, the protocol can handle about 20000 binary gates per second at an error level of 2^−50.Keywords -- Interactive proofs, arguments, proofs of knowledge, computational security,efficient general primitives, multi-bit commitment, statistical zero-knowledge.
- 1 June 1997
- Published by Springer Nature in Journal of Cryptology
- Vol. 10 (3) , 163-194
On the existence of statistically hiding bit commitment schemes and fail-stop signatures
- 1 June 1997
- Published by Springer Nature in Journal of Cryptology
- Vol. 10 (3) , 163-194
On the existence of statistically hiding bit commitment schemes and fail-stop signatures
- Open Access
- 28 January 1997
- Published by Det Kgl. Bibliotek/Royal Danish Library in BRICS Report Series
- Vol. 4 (28)
Span Programs and General Secure Multi-Party Computation
The contributions of this paper are three-fold. First, as an abstraction of previously proposed cryptographic protocols we propose two cryptographic primitives: homomorphicshared commitments and linear secret sharing schemes with an additional multiplication property. We describe new constructions for general secure multi-party computation protocols, both in the cryptographic and the information-theoretic (or securechannels) setting, based on any realizations of these primitives.Second, span programs, a model of computation introduced by Karchmer and Wigderson, are used as the basis for constructing new linear secret sharing schemes, from which the two above-mentioned primitives as well as a novel verifiable secret sharing scheme can efficiently be realized. Third, note that linear secret sharing schemes can have arbitrary (as opposed tothreshold) access structures. If used in our construction, this yields multi-party protocols secure against general sets of active adversaries, as long as in the cryptographic (information-theoretic) model no two (no three) of these potentially misbehaving player sets cover the full player set. This is a strict generalization of the threshold-type adversaries and results previously considered in the literature. While this result is new for the cryptographic model, the result for the information-theoretic model was previously proved by Hirt and Maurer. However, in addition to providing an independent proof, our protocols are not recursive and have the potential of being more efficient.
- 28 January 1997
- Published by Det Kgl. Bibliotek/Royal Danish Library in BRICS Report Series
- Vol. 4 (28)
Open AccessSpan Programs and General Secure Multi-Party Computation
The contributions of this paper are three-fold. First, as an abstraction of previously proposed cryptographic protocols we propose two cryptographic primitives: homomorphicshared commitments and linear secret sharing schemes with an additional multiplication property. We describe new constructions for general secure multi-party computation protocols, both in the cryptographic and the information-theoretic (or securechannels) setting, based on any realizations of these primitives.Second, span programs, a model of computation introduced by Karchmer and Wigderson, are used as the basis for constructing new linear secret sharing schemes, from which the two above-mentioned primitives as well as a novel verifiable secret sharing scheme can efficiently be realized. Third, note that linear secret sharing schemes can have arbitrary (as opposed tothreshold) access structures. If used in our construction, this yields multi-party protocols secure against general sets of active adversaries, as long as in the cryptographic (information-theoretic) model no two (no three) of these potentially misbehaving player sets cover the full player set. This is a strict generalization of the threshold-type adversaries and results previously considered in the literature. While this result is new for the cryptographic model, the result for the information-theoretic model was previously proved by Hirt and Maurer. However, in addition to providing an independent proof, our protocols are not recursive and have the potential of being more efficient.
- 15 June 1996
- Published by Det Kgl. Bibliotek/Royal Danish Library in BRICS Report Series
- Vol. 3 (45)
Statistical Secrecy and Multi-Bit Commitments
We present and compare definitions of the notion of "statisticallyhiding" protocols, and we propose a novel statistically hiding commitmentscheme. Informally, a protocol statistically hides a secret if acomputationally unlimited adversary who conducts the protocol withthe owner of the secret learns almost nothing about it. One definitionis based on the L1-norm distance between probability distributions,the other on information theory. We prove that the two definitions areessentially equivalent. For completeness, we also show that statisticalcounterparts of definitions of computational secrecy are essentiallyequivalent to our main definitions. Commitment schemes are an important cryptologic primitive. Their purpose is to commit one party to a certain value, while hiding this value from the other party until some later time. We present a statisticallyhiding commitment scheme allowing commitment to manybits. The commitment and reveal protocols of this scheme are constantround, and the size of a commitment is independent of the number ofbits committed to. This also holds for the total communication complexity,except of course for the bits needed to send the secret when itis revealed. The proof of the hiding property exploits the equivalenceof the two definitions.Index terms -- Cryptology, Shannon theory, unconditional security,statistically hiding, multi-bit commitment, similarity of ensemblesof distributions, zero-knowledge, protocols.
- 15 June 1996
- Published by Det Kgl. Bibliotek/Royal Danish Library in BRICS Report Series
- Vol. 3 (45)
Statistical Secrecy and Multi-Bit Commitments
We present and compare definitions of the notion of "statisticallyhiding" protocols, and we propose a novel statistically hiding commitmentscheme. Informally, a protocol statistically hides a secret if acomputationally unlimited adversary who conducts the protocol withthe owner of the secret learns almost nothing about it. One definitionis based on the L1-norm distance between probability distributions,the other on information theory. We prove that the two definitions areessentially equivalent. For completeness, we also show that statisticalcounterparts of definitions of computational secrecy are essentiallyequivalent to our main definitions. Commitment schemes are an important cryptologic primitive. Their purpose is to commit one party to a certain value, while hiding this value from the other party until some later time. We present a statisticallyhiding commitment scheme allowing commitment to manybits. The commitment and reveal protocols of this scheme are constantround, and the size of a commitment is independent of the number ofbits committed to. This also holds for the total communication complexity,except of course for the bits needed to send the secret when itis revealed. The proof of the hiding property exploits the equivalenceof the two definitions.Index terms -- Cryptology, Shannon theory, unconditional security,statistically hiding, multi-bit commitment, similarity of ensemblesof distributions, zero-knowledge, protocols.