- Revisiting the Karnin, Greene and Hellman Bounds
- An Efficient Protocol for Fair Secure Two-Party Computation
- Efficient Committed Oblivious Transfer of Bit Strings
- Smooth Rényi Entropy of Ergodic Quantum Information Sources
- Practical and Secure Solutions for Integer Comparison
- Efficient Pseudorandom Generators Based on the DDH Assumption
- Efficient Binary Conversion for Paillier Encrypted Values
- A Protocol Issue for the Malicious Case of Yao's Garbled Circuit Construction
- List Signature Schemes
- Concrete Security of the Blum-Blum-Shub Pseudorandom Generator
- Quantum Information Theoretical Analysis of Various Constructions for Quantum Secret Sharing
- Generic Security Proof of Quantum Key Exchange using Squeezed States
- Experiments With Queries Over Encrypted Data Using Secret Sharing
- On Second-Order Differential Power Analysis
- State Recovery Attacks on Pseudorandom Generators
- Practical Two-Party Computation Based on the Conditional Gate
- A Fair and Efficient Solution to the Socialist Millionaires' Problem
- Compensating for a Lack of Transparency
- Optimally Efficient Accountable Time-Stamping
- A Simple Publicly Verifiable Secret Sharing Scheme and its Application to Electronic Voting
- Basic Security of the eCash(tm); Payment System
- A Secure and Optimally Efficient Multi-Authority Election Scheme
- A Tight Lower Bound for Top-Down Skew Heaps
- Multi-Authority Secret-Ballot Elections with Linear Work
- An Efficient Electronic Payment System Withstanding Parallel Attacks
- Systolic Arrays for the Recognition of Permutation-Invariant Segments
- A New Algorithm for the Recognition of Series Parallel Graphs
- Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols
- The ESPRIT Project CAFE: High Security Digital Payment Systems
- A Systematic Analysis of Splaying
- Inorder Traversal of a Binary Heap and its Inversion in Optimal Time and Space
- The Derivation of a Tighter Bound for Top-Down Skew Heaps
- Searching by Elimination
- Recognizing Perfect-Shuffles

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*Z*, where_{N}*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*∈*Z*into Paillier encryptions of the bits of_{N}*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*/(*n*2^{κ}) 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 (log_{2}*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*+2*n*),*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.