Papers available online
Also see my PhD thesis Data Structures and
Amortized Complexity in a Functional Setting.
- Revisiting the Karnin, Greene and Hellman Bounds
(Springer LINK)
Yvo Desmedt,
Brian King, and
Berry Schoenmakers
The algebraic setting for threshold secret sharing schemes can vary,
dependent on the application. This algebraic setting can limit the number
of participants of an ideal secret sharing scheme.
Thus it is important to know for which thresholds one could utilize
an ideal threshold sharing scheme and for which thresholds
one would have to use non-ideal schemes. The implication is that
more than one share may have to be dealt to some or all parties.
Karnin, Greene and Hellman constructed several bounds concerning
the maximal number of participants in threshold sharing schemes.
There has been a number of researchers who have noted
the relationship between k-arcs in projective spaces and ideal
linear threshold secret schemes, as well as between MDS codes and
ideal linear threshold secret sharing schemes.
Further, researchers have constructed optimal bounds concerning
the size of k-arcs in projective spaces, MDS codes, etc. for various finite fields.
Unfortunately, the application of these results on the Karnin, Greene and Hellman bounds has not been widely disseminated.
Our contribution in this paper is revisiting and updating the Karnin, Greene, and Hellman bounds,
providing optimal bounds on the number of participants in ideal linear threshold secret sharing schemes
for various finite fields, and
constructing these bounds using the same tools that
Karnin, Greene, and Hellman introduced in their seminal paper.
We provide optimal bounds for the maximal number of players for a t out of n ideal linear threshold scheme
when t=3, for all possible finite fields.
We also provide bounds for infinitely many t and infinitely many fields and
a unifying relationship between this problem and the MDS (maximum distance separable) codes
that shows that any improvement on
bounds for ideal linear threshold secret sharing scheme will
impact bounds on MDS codes, for which there is a number of conjectured (but open) problems.
In proceedings of Information Theoretic Security (ICITS'08), volume 5155 of Lecture Notes in Computer
Science, pages 183-198, Berlin, 2008. Springer-Verlag.
- An Efficient Protocol for Fair Secure Two-Party Computation
(Springer LINK)
Mehmet Kiraz and
Berry Schoenmakers
In the 1980s, Yao presented a very efficient constant-round secure two-party computation protocol withstanding semi-honest adversaries, which is based on so-called garbled circuits. Later, several protocols based on garbled circuits covering malicious adversaries have been proposed. Only a few papers, however, discuss the fundamental property of fairness for two-party computation. So far the protocol by Pinkas (Eurocrypt 2003) is the only one which deals with fairness for Yao's garbled circuit approach.
In this paper, we improve upon Pinkas' protocol by presenting a more efficient variant,
which includes several modifications including one that fixes a subtle security problem with the computation of the so-called majority circuit. We prove the security of our protocol according to the real/ideal simulation paradigm, as Lindell and Pinkas recently did for the malicious case (Eurocrypt 2007).
In proceedings of Cryptographers' Track-RSA Conference (CT-RSA 2008), volume 4964 of Lecture Notes in Computer
Science, pages 88-105, Berlin, 2008. Springer-Verlag.
- Efficient Committed Oblivious Transfer of Bit Strings
(Springer LINK)
Mehmet Kiraz,
Berry Schoenmakers and
José Villegas
Oblivious transfer (OT) is a powerful primitive in modern cryptography, often
used in a context of semi-honest adversaries.
Committed oblivious transfer (COT) is an
enhancement involving the use of commitments, which can be used in many applications
of OT covering particular malicious adversarial behavior. For OT, many protocols
are known that cover the transfer of bit strings
rather than just single bits.
For COT, though, the known protocols only cover the transfer of bits.
In this paper, we thus present efficient COT protocols for transferring (long)
bit strings, which perform quite well in
comparison to the most efficient COT protocols
for bits. We prove the security of our protocols following the simulation
paradigm in the cryptographic model, also assuming the random oracle model for efficient
non-interactive proofs.
Also, as a motivation for the use of COT instead of OT, we point out that a protocol which uses OT
as a subprotocol may have subtle security issues in the presence of malicious
adversaries.
In proceedings of Information Security (ISC 2007), volume 4779 of Lecture Notes in Computer
Science, pages 130-144, Berlin, 2007. Springer-Verlag.
- Smooth Rényi Entropy of Ergodic Quantum Information Sources
Berry Schoenmakers,
Jilles Tjoelker,
Pim Tuyls, and
Evgeny Verbitskiy
We investigate the recently introduced notion of smooth Rényi entropy
for the case of ergodic information sources,
thereby generalizing previous work which concentrated mainly
on i.i.d. information sources. We will actually consider ergodic
quantum information sources, of which ergodic classical information
sources are a special case. We prove that the average
smooth Rényie entropy rate will approach the entropy rate of a
stationary, ergodic source, which is equal to the Shannon entropy
rate for a classical source and the von Neumann entropy rate
for a quantum source.
In Proceedings of International Symposium on Information Theory-ISIT 2007, pages 256-260. IEEE.
- Practical and Secure Solutions for Integer Comparison
(Springer LINK)
Juan Garay,
Berry Schoenmakers and
José Villegas
Yao’s classical millionaires’ problem is about securely determining
whether x > y, given two input values x, y, which are held as
private inputs by two parties, respectively. The output x > y becomes
known to both parties.
In this paper, we consider a variant of Yao’s problem in which the inputs
x, y as well as the output bit x > y are encrypted. Referring to the
framework of secure n-party computation based on threshold homomorphic
cryptosystems as put forth by Cramer, Damgård, and Nielsen at
Eurocrypt 2001, we develop solutions for integer comparison, which take
as input two lists of encrypted bits representing x and y, respectively,
and produce an encrypted bit indicating whether x > y as output. Secure
integer comparison is an important building block for applications
such as secure auctions.
In this paper, our focus is on the two-party case, although most of our results
extend to the multi-party case. We propose new logarithmic-round
and constant-round protocols for this setting, which achieve simultaneously
very low communication and computational complexities. We
analyze the protocols in detail and show that our solutions compare favorably
to other known solutions.
In Public Key Cryptography—PKC ’07, volume 4450 of Lecture Notes in Computer
Science, pages 330-342, Berlin, 2007. Springer-Verlag.
- Efficient Pseudorandom Generators Based on the DDH Assumption
(Springer LINK)
Reza Rezaeian Farashahi,
Berry Schoenmakers and
Andrey Sidorenko
A family of pseudorandom generators based on the decisional
Diffie-Hellman assumption is proposed. The new construction is a modified
and generalized version of the Dual Elliptic Curve generator proposed
by Barker and Kelsey. Although the original Dual Elliptic Curve
generator is shown to be insecure, the modified version is provably secure
and very efficient in comparison with the other pseudorandom generators
based on discrete log assumptions.
Our generator can be based on any group of prime order provided that an
additional requirement is met (i.e., there exists an efficiently computable
function that in some sense enumerates the elements of the group). Two
specific instances are presented. The techniques used to design the instances,
for example, the new probabilistic randomness extractor are of
independent interest for other applications.
In Public Key Cryptography—PKC ’07, volume 4450 of Lecture Notes in Computer
Science, pages 426-441, Berlin, 2007. Springer-Verlag.
- Efficient Binary Conversion
for Paillier Encrypted Values
(Springer LINK)
Berry Schoenmakers and
Pim Tuyls
We consider the framework of secure n-party computation based on threshold
homomorphic cryptosystems as put forth by Cramer, Damgård, and
Nielsen at Eurocrypt 2001. When used with Paillier's cryptosystem,
this framework allows for efficient secure evaluation of any arithmetic
circuit defined over ZN, where N is the RSA modulus of the
underlying Paillier cryptosystem.
In this paper, we extend the scope of the framework by considering
the problem of converting a given Paillier encryption of a value
x ∈ ZN into Paillier encryptions of the bits of x. We present solutions
for the general case in which x can be any integer in {0,1,...,N},
and for the restricted case in which x < N/(n2κ) for a security parameter κ.
In the latter case, we show how to extract the l least significant bits of
x (in encrypted form) in time proportional to l, typically saving a
factor of (log2 N)/l compared to the general case.
Thus, intermediate computations that rely in an essential way on the binary representations
of their input values can be handled without enforcing that the entire
computation is done bitwise. Typical examples involve the relational operators such
as < and =. As a specific scenario we will consider the setting for (approximate)
matching of biometric templates, given as bit strings.
In Advances in Cryptology-EUROCRYPT'06, volume 4004 of Lecture Notes in Computer
Science, pages 522-537, Berlin, 2006. Springer-Verlag.
- A Protocol Issue
for the Malicious Case of Yao's Garbled Circuit Construction
Mehmet Kiraz and
Berry Schoenmakers
We present a protocol issue that arises with the use of oblivious transfer
in the malicious case of several two-party computation protocols based on Yao's
garbled circuit. We describe this issue for a protocol by Pinkas (Eurocrypt 2003)
and for the Fairplay protocol, and we discuss why this issue still persists for
a recently suggested modification of the Fairplay protocol. We propose a
solution using committed oblivious transfer instead of (plain) oblivious transfer.
We also introduce the notion of committing oblivious transfer, which
leads to an alternative, potentially more efficient solution.
In Proceedings of 27th Symposium on Information Theory in the Benelux (2006) 283-290.
- List Signature Schemes
(Elsevier Science Direct)
Sébastien Canard,
Berry Schoenmakers,
Martijn Stam, and
Jacques Traoré
A group signature scheme allows group members to issue signatures on
behalf of the group, while hiding for each signature which group
member actually issued it. Such scheme also involves a group manager,
who is able to open any group signature by showing which group member
issued it.
We introduce the concept of list signatures as a variant of group
signatures which sets a limit on the number of signatures each group
member may issue. These limits must be enforced without having
the group manager open signatures of honest group members--which
excludes the trivial solution in which the group manager opens every
signature to see whether some group members exceed their
limits. Furthermore, we consider the problem of publicly
identifying group members who exceed their limits, also without
involving the group manager.
In Discrete Applied Mathematics 154 (Feb. 2006) 189-201 (Special
issue on Coding and Cryptography).
- Concrete Security of the
Blum-Blum-Shub Pseudorandom Generator
(Springer LINK)
Andrey Sidorenko and
Berry Schoenmakers
The asymptotic security of the Blum-Blum-Shub (BBS) pseudorandom generator
has been studied by Alexi et al. and Vazirani and Vazirani, who proved
independently that O(log log N) bits can be extracted on each iteration,
where N is the modulus (a Blum integer). The concrete security of this
generator has been analyzed previously by Fischlin and Schnorr and by Knuth.
In this paper we continue to analyse the concrete security the BBS generator.
We show how to select both the size of the modulus and the number of bits extracted
on each iteration such that a desired level of security is reached, while
minimizing the computational effort per output bit.
We will assume a concrete lower bound on the hardness of integer factoring,
which is obtained by extrapolating the best factorization results to date.
While for asymptotic security it suffices to give a polynomial time reduction
a successful attack to factoring, we need for concrete security a reduction that
is as efficient as possible. Our reduction algorithm relies on the techniques
of Fischlin and Schnorr, as well as ideas of Vazirani and Vazirani,
but combining these in a novel way for the case that more than one bit
is output on each iteration.
In Cryptography and Coding: 10th IMA International Conference, volume 3796 of Lecture Notes in Computer
Science, pages 355-375, Berlin, 2005. Springer-Verlag.
- Quantum Information
Theoretical Analysis of Various Constructions for Quantum Secret Sharing
Karin Rietjens,
Berry Schoenmakers, and
Pim Tuyls
Recently, an information theoretical model for Quantum Secret Sharing (QSS)
schemes was introduced. By using this model, we prove that pure state Quantum
Threshold Schemes (QTS) can be constructed from quantum MDS codes and vice
versa. In particular, we consider stabilizer codes and give a constructive
proof of their relation with QTS. Furthermore, we reformulate the Monotone
Span Program construction according to the information theoretical
model and check the recoverability and secrecy requirement. Finally, we
consider QSS schemes which are based on quantum teleportation.
In Proceedings of International Symposium on Information Theory-ISIT 2005, pages 1598-1602. IEEE.
Preliminary version appeared in
Proceedings of 26th Symposium on Information Theory in the Benelux (2005) 181-188.
- Generic Security
Proof of Quantum Key Exchange using Squeezed States
Karin Poels,
Pim Tuyls, and
Berry Schoenmakers
Recently, a Quantum Key Exchange protocol that uses squeezed states was
presented by Gottesman and Preskill. In this paper we give a generic security
proof for this protocol. The method used for this generic security proof is
based on recent work by Christiandl, Renner and Ekert.
In Proceedings of International Symposium on Information Theory-ISIT 2005, pages 1612-1616. IEEE.
Preliminary version appeared in
Proceedings of 26th Symposium on Information Theory in the Benelux (2005) 189-196.
- Experiments With Queries Over Encrypted Data Using Secret Sharing
(Springer LINK)
Richard Brinkman,
Berry Schoenmakers,
Jeroen Doumen, and
Willem Jonker
To avoid insider attacks one cannot rely on access control to protect a
database scheme. Encrypting the database is a better option. This paper
describes a working prototype of an encrypted database system that allows
remote querying over the encrypted data. Experiments with the system show
the practical impact of our encoding scheme on storage space and CPU time.
Two algorithms, each with two different matching rules, are compared
to each other.
In Secure Data Management: Second VLDB Workshop-SDM 2005, volume 3674 of Lecture Notes in Computer
Science, pages 33-46, Berlin, 2005. Springer-Verlag.
- On Second-Order Differential Power Analysis
(Springer LINK)
Marc Joye,
Pascal Paillier, and
Berry Schoenmakers
Differential Power Analysis (DPA) is a powerful cryptanalytic technique
aiming at extracting secret data from a cryptographic
device by collecting power consumption traces and averaging over a series
of acquisitions. In order to prevent the leakage, hardware designers
and software programmers make use of masking techniques (a.k.a. data
whitening methods). However, the resulting implementations may still
succumb to second-order DPA. Several recent papers studied second-order
DPA but, although the conclusions that are drawn are correct, the
analysis is not.
This paper fills the gap by providing an exact analysis of second-order
DPA as introduced by Messerges. It also considers several generalizations,
including an extended analysis in the more general Hamming-distance model.
In Cryptographic Hardware and Embedded Systems-CHES 2005, volume 3659 of Lecture Notes in Computer
Science, pages 293-308, Berlin, 2005. Springer-Verlag.
References [1] Gandhi polynomials
and [2] their companions of the paper are from
Neil Sloane's On-Line Encyclopedia of Integer Sequences.
- State Recovery Attacks on Pseudorandom Generators
Andrey Sidorenko and
Berry Schoenmakers
State recovery attacks comprise an important class of attacks on pseudorandom generators. In this paper
we analyze resistance of pseudorandom generators against these attacks in terms of concrete security.
We show that security of the Blum-Micali pseudorandom generator against state recovery attacks is tightly
related to the security of the corresponding one-way function.
In WEWoRC 2005 - Western European Workshop on Research in Cryptology, volume P-74 of Lecture
Notes in Informatics (LNI), pages 53-63, 2005. Gesellschaft für Informatik.
- Practical Two-Party
Computation Based on the Conditional Gate
(Springer LINK)
Berry Schoenmakers and
Pim Tuyls
We present new results in the framework of secure multiparty computation based on homomorphic threshold
cryptosystems. We introduce the conditional gate as a special type of multiplication gate
that can be realized in a surprisingly simple and efficient way using just
standard homomorphic threshold ElGamal encryption. As addition gates are essentially
for free, the conditional gate not only allows for building a circuit for any function, but
actually yields efficient circuits for a wide range of tasks.
In Advances in Cryptology-ASIACRYPT'04, volume 3329 of Lecture Notes in Computer
Science, pages 119-136, Berlin, 2004. Springer-Verlag.
- A Fair and Efficient Solution to the Socialist Millionaires' Problem
Fabrice Boudot,
Berry Schoenmakers, and
Jacques Traoré
We present a solution to the Tierce problem, in which two
players want to know whether they have backed the same combination
(but neither player wants to disclose its combination to the other
one). The problem is also known as the socialist millionaires'
problem, in which two millionaires want to know whether they happen
to be equally rich. In our solution, both players will be convinced of
the correctness of the equality test between their combinations and
will get no additional information on the other player's combination.
Our solution is fair: one party cannot get the result of the
comparison while preventing the other one from getting it. The
protocol requires O(k) exponentiations only, where k is a security
parameter.
In Discrete Applied Mathematics 111 (July 2001) 23-36. (Special issue on Coding and
Cryptology)
- Compensating for a Lack of Transparency
Input for debate on Internet Voting: Spurring or Corrupting Democracy? at
CFP2000. See www.cfp2000.org.
In Proceedings of the 10th Conference on Computers, Freedom & Privacy, Toronto,
Canada, April 4-7, 2000, pages 231-233. ACM, New York. ISBN 1-58113-256-5.
- Optimally Efficient Accountable Time-Stamping
Ahto Buldas,
Helger Lipmaa, and
Berry Schoenmakers
Efficient secure time-stamping schemes employ a 2-level approach in
which the time-stamping service operates in rounds. We say that a
time-stamping service is accountable if if it makes the TSA
and other authorities accountable for their actions by enabling a
principal to detect and later prove to a judge any frauds, including
attempts to reorder time-stamps from the same round. We
investigate the paradigm of time-stamping services based on simply
connected graphs, and propose a simple, yet optimal, accountable
time-stamping service, using what we call threaded tree schemes. We
improve upon the previously best scheme by Buldas and Laud by
reducing the size of a time stamp by a factor of about 3.786 and
show that our construction is optimal in a strict sense. The new
protocols also increase the trustworthiness of the publication
process, which takes place at the end of each round.
In Proceedings of PKC2000, volume 1751 of Lecture Notes in Computer
Science, pages 293-305, Berlin, 2000. Springer-Verlag.
- A Simple Publicly Verifiable Secret
Sharing Scheme and its Application to Electronic Voting
A publicly verifiable secret sharing (PVSS) scheme is a verifiable secret sharing
scheme with the property that the validity of the shares distributed by the dealer
can be verified by any party; hence verification is not limited to the respective
participants receiving the shares. We present a new construction for
PVSS schemes, which compared to previous solutions by Stadler and later by Fujisaki
and Okamoto, achieves improvements both in efficiency and in the type of intractability assumptions.
The running time is O(nk), where k is a security parameter, and n is
the number of participants, hence essentially optimal.
The intractability assumptions are the standard Diffie-Hellman assumption
and its decisional variant.We present several applications of our PVSS scheme,
among which is a new type of universally verifiable election scheme based on PVSS.
The election scheme becomes quite practical and combines several advantages of related
electronic voting schemes, which makes it of interest in its own right.
In Advances in Cryptology-CRYPTO'99, volume 1666 of Lecture Notes in Computer
Science, pages 148-164, Berlin, 1999. Springer-Verlag.
- Basic Security of the eCash(tm) Payment System
eCash(tm) is a payment system designed and implemented by DigiCash for making purchases over open
networks such as the Internet. In this paper we review some of the main cryptographic techniques used
throughout the eCash system. We will focus on security aspects as well as some performance related issues.
The central notion of an electronic coin is treated in detail, and the basic protocols manipulating
coins are described.
In State of the Art in Applied Cryptography, Course on Computer Security and Industrial Cryptography,
Leuven, Belgium, June 3--6, 1997 Revised Lectures, B. Preneel, V. Rijmen (eds.), volume 1528
of Lecture Notes in Computer Science, Berlin, 1998. 16 pages.
- A Secure and Optimally Efficient Multi-Authority Election Scheme
Ronald Cramer,
Rosario Gennaro, and
Berry Schoenmakers
In this paper we present a new multi-authority secret-ballot election scheme that guarantees privacy,
universal verifiability, and robustness. It is the first scheme for which the performance is optimal
in the sense that time and communication complexity is minimal both for the individual voters and
the authorities. An interesting property of the scheme is that the time and communication complexity
for the voter is independent of the number of authorities. A voter simply posts a single
encrypted message accompanied with a compact proof that it contains a valid vote. Our result is
complementary to the result by Cramer, Franklin, Schoenmakers, and Yung in the sense that in their
scheme the work for voters is linear in the number of authorities but can be instantiated to yield
information-theoretic privacy, while in our scheme the voter's effort is independent of the number
of authorities but always provides computational privacy-protection. We will also point out that
the majority of proposed voting schemes provide computational privacy only (often without even
considering the lack of information-theoretic privacy), and that our new scheme is by far superior
to those schemes.
In Advances in Cryptology-EUROCRYPT'97, volume 1233 of Lecture Notes in Computer
Science, pages 103-118, Berlin, 1997. Springer-Verlag.
Journal version appears in European Transactions on Telecommunications 8
(September-October 1997) 481-490.
- A Tight Lower Bound for Top-Down Skew Heaps
Previously, it was shown in a paper by Kaldewaij and Schoenmakers that for top-down
skew heaps the amortized number of comparisons required for meld and delmin is upper
bounded by logφ n, where n is the total size of the inputs to these
operations and φ=(1+√5)/2 denotes the golden ratio. In this paper we present worst-case
sequences of operations on top-down skew heaps in which each application of meld and
delmin requires approximately logφ n comparisons. As the
remaining heap operations require no comparisons, it then follows that the set of bounds is tight.
The result relies on a particular class of self-recreating binary trees, which is related to a
sequence known as Hofstadter's G-sequence.
Information Processing Letters 61 (1997) 279-284.
Reference [10] of the paper is
also available as Neil Sloane's On-Line
Encyclopedia of Integer Sequences, through which I found out about Hofstadter's
G-sequence.
-
Multi-Authority Secret-Ballot Elections with Linear Work
Ronald Cramer,
Matthew Franklin,
Berry Schoenmakers, and
Moti Yung
We present new cryptographic protocols for multi-authority secret ballot elections that guarantee
privacy, robustness, and universal verifiability. Application of some novel techniques, in
particular the construction of witness hiding/indistinguishable protocols from Cramer, Damgård
and Schoenmakers, and the verifiable secret sharing scheme of Pedersen, reduce the work required
by the voter or an authority to a linear number of cryptographic operations in the population
size (compared to quadratic in previous schemes). Thus we get significantly closer to a practical
election scheme.
In Advances in Cryptology-EUROCRYPT'96, volume 1070
of Lecture Notes in Computer Science, pages 72-83, Berlin, 1996. Springer-Verlag.
Slightly different version: Report CS-R9571, Centrum voor Wiskunde en Informatica (CWI), November 1995.
- An Efficient Electronic Payment System Withstanding Parallel Attacks
A new blind signature protocol
based on Schnorr signatures is presented that can be used in payment systems. Apart from its
simplicity and efficiency, an important feature of the protocol is that it can be argued to
imply a withdrawal protocol that is resistant to parallel attacks by a collusion of users.
An essential property of the blind signature protocol is that the signer has complete knowledge
of the receiver's secret key. Consequently, there's no protection whatsoever against framing
by the bank in the proposed payment system. We therefore show how cryptographic protection
against framing can be added again at the cost of introducing another trusted party, which is
active during registration of the users only. A similar blind signature protocol can be based
on Okamoto's variation of Schnorr's identification scheme, which is provably witness hiding.
Report CS-R9522, Centrum voor Wiskunde en Informatica (CWI), March 1995.
- Systolic
Arrays for the Recognition of Permutation-Invariant Segments
Joost-Pieter Katoen and
Berry Schoenmakers
Let P be a permutation defined on sequences of length N.
A sequence of N values is said to be P-invariant when it does not change
when permuted according to P. A program is said to recognize P-invariant
segments when it determines for each segment of N successive input values whether
it is P-invariant.
In this paper we derive a program scheme that generates
efficient parallel programs for the recognition of P-invariant segments. The programs
consist of a chain of cells extended with a linear number of links between non-neighbouring
cells. Under reasonable conditions on P, these programs correspond to systolic
arrays with both constant response time and constant latency (independent of N).
Efficient systolic arrays for problems such as palindrome recognition or perfect shuffle
recognition can be constructed automatically in this way. This is illustrated for the
palindrome recognition problem.
Science of Computer
Programming 27 (1996) 119-137.
- A New Algorithm for the
Recognition of Series Parallel Graphs
In this paper we develop a
new linear-time algorithm for the recognition of series parallel graphs. The algorithm
is based on a succinct representation of series parallel graphs for which the presence
of an arc can be tested in constant time; space utilization is linear in the number of
vertices. We show how to compute such a representation in linear time from a
breadth-first spanning tree. Furthermore, we present a precise condition for the
existence of such succinct representations in general, which is, for instance,
satisfied by planar graphs.
Report CS-R9504, Centrum voor Wiskunde
en Informatica (CWI), January 1995.
- Proofs of
Partial Knowledge and Simplified Design of Witness Hiding Protocols
Ronald Cramer,
Ivan Damgård, and
Berry Schoenmakers
Suppose we are given a proof of knowledge P in which a prover demonstrates that he
knows a solution to a given problem instance. Suppose also that we have a secret sharing
scheme S on n participants. Then under certain assumptions on P
and S, we show how to transform P into a witness indistinguishable protocol,
in which the prover demonstrates knowledge of the solution to some subset of n
problem instances out of a collection of subsets defined by S. For example,
using a threshold scheme, the prover can show that he knows at least d out of
n solutions without revealing which d instances are involved. If the
instances are independently generated, we get a witness hiding protocol, even if P
did not have this property. Our results can be used to efficiently implement general forms
of group oriented identification and signatures. Our transformation produces a protocol
with the same number of rounds as P and communication complexity n times
that of P. Our results use no unproven complexity assumptions.
In Advances
in Cryptology-CRYPTO'94, volume 839 of Lecture Notes in Computer Science,
pages 174-187, Berlin, 1994. Springer-Verlag.
Version with more examples:
Report CS-R9413,
CWI, February 1994. This version is published in CWI Quarterly,
volume 8(2) 1995, pp. 111-127.
- The ESPRIT Project CAFE: High
Security Digital Payment Systems
Jean-Paul Boly,
Antoon Bosselaers,
Ronald Cramer,
Rolf Michelsen, Stig Mjolsnes, Frank Muller,
Torben Pedersen,
Birgit Pfitzmann,
Peter de Rooij, Berry Schoenmakers,
Matthias Schunter,
Luc Vallee, and Michael Waidner
CAFE ("Conditional Access for Europe") is an ongoing project in the European Community's
ESPRIT program. The goal of CAFE is to develop innovative systems for conditional access,
and in particular, digital payment systems. An important aspect of CAFE is high security
of all parties concerned, with the least possible requirements that they are forced to
trust other parties (so-called multi-party security). This should give legal certainty to
everybody at all times. Moreover, both the electronic money issuer and the individual users
are less dependent on the tamper-resistance of devices than in usual digital payment systems.
Since CAFE aims at the market of small everyday payments that is currently dominated by cash,
payments are offline, and privacy is an important issue.
In ESORICS 94
(Third European Symposium on Research in Computer Security), volume 875 of Lecture
Notes in Computer Science, pages 217-230, Berlin, 1994. Springer-Verlag.
See also CAFE project Final report volume II: Secure
Protocols and Architecture, Report MAS-E0303, Centrum voor Wiskunde en
Informatica (CWI), February 2003.
- A Systematic Analysis of Splaying
In this paper we perform an amortized analysis
of a functional program for splaying. We construct a potential function that yields the
same bound for the amortized cost of splaying as given by D.D. Sleator and R.E. Tarjan---the
inventors of splay trees. In addition, we show that this bound is minimal for the class
of "sum of logs" potentials. Our approach also applies to the analysis of path reversal
and pairing heaps.
Information Processing Letters 45 (1993) 41-50.
- Inorder Traversal
of a Binary Heap and its Inversion in Optimal Time and Space
In this
paper we derive a linear-time, constant-space algorithm to construct a binary heap whose
inorder traversal equals a given sequence. We do so in two steps. First, we invert a
program that computes the inorder traversal of a binary heap, using the proof rules for
program inversion by W. Chen and J.T. Udding. This results in a linear-time solution in
terms of binary trees. Subsequently, we data-refine this program to a constant-space
solution in terms of linked structures.
In Mathematics of Program
Construction-MPC'92, volume 669 of Lecture Notes in Computer Science,
pages 291-301, Berlin, 1993. Springer-Verlag.
- The Derivation
of a Tighter Bound for Top-Down Skew Heaps
Anne Kaldewaij and
Berry Schoenmakers
In this paper we present and analyze functional programs for a number of priority queue
operations. These programs are based upon the top-down skew heaps---a truly elegant data
structure---designed by D.D. Sleator and R.E. Tarjan. We show how their potential
technique can be used to determine the time complexity of functional programs. This
functional approach enables us to derive a potential function leading to tighter
bounds for the amortized costs of the priority queue operations. From the improved
bounds it follows, for instance, that Skewsort, a simple sorting program using these
operations, requires only about N log N comparisons to sort N
numbers (in the worst case), where the base of the logarithm is equal to the golden
ratio.
Information Processing Letters 37 (1991) 265-271.
- Searching by
Elimination
Anne Kaldewaij and
Berry Schoenmakers
In this paper we derive three program schemes which are applicable to a wide class of
searching problems. The first scheme, which is called Searching by Elimination, solves
a rather general searching problem. The two other schemes, Symmetric Linear Search and
Left-to-right Linear Search, are refinements of this general scheme. For a specific
problem, these schemes may be refined---using mathematical properties of the objects
involved---to a program. We shall illustrate this by some examples, ranging from
elementary problems to more advanced problems. It turns out that the Symmetric Linear
Search scheme yields---compared to the conventional Left-to-right Linear Search
scheme---more elegant programs.
Science of Computer
Programming 14 (1990) 243-254.
- Recognizing
Perfect-Shuffles
Joost-Pieter Katoen and
Berry Schoenmakers
In the series ``Recognizing ...'' we present two fine-grained parallel programs dealing
with the recognition of perfect-shuffles. A segment a[m..m+2n), m≥0 and
n≥0, of an infinite sequence a is called perfect-shuffle invariant (or, a
perfect-shuffle, for short) if a(m+j) = a(m+2(j mod n) + j div n)),
for all j, 0≤j<2n.
Return to ~berry.