On the Complexity of Blind Signatures

Blind signature schemes provide the functionality of a carbon copy envelope: The user (receiver) puts his message into this envelope and hands it over to the signer (sender). The signer in return signs the envelope and gives it back to the user who recovers the original signed message out of the envelope. Security says that the signer remains oblivious about the message (blindness), but at the same time the receiver cannot output any additional message/signature pair (unforgeability). Classical applications of blind signatures include e-cash and e-voting. Blind signature schemes are an important cryptographic primitive and many constructions have been proposed in the literature. These instantiations differ mainly in round complexity, underlying computational assumptions, and the model in which the proof of security is given. However, the minimal requirements for blind signatures in terms of round complexity and computational assumptions without assuming setup assumptions are unknown. This thesis addresses both of these questions. For the study of the round complexity, this thesis investigates the possibility of proving the security of a more general class of three-move blind signature schemes. We show that finding security proofs for these schemes via black-box reductions in the standard model is hard. Characteristic for this class is that it is publicly decidable from the transcript if the user can derive a valid signature, or not. Regarding the computational assumptions, this thesis first shows that the class of unique blind signature schemes can be used to build oblivious transfer protocols in a black- box way. These blind signature schemes have at most one signature per message and public key. It is well known that oblivious transfer cannot be constructed from one- way functions in a black-box fashion. Thus, this result also holds for (regular) blind signature schemes. Moreover, this thesis rules out black-box constructions of blind signature schemes from one-way functions. In fact, this thesis rules out constructions from a random permutation oracle. This separation holds even for schemes signing 1-bit messages that achieve security only against honest-but-curious behavior.

Blinde Signaturen ähneln einem Briefumschlag, der aus Kohlepapier besteht. Der Sig- nierer (Sender) unterschreibt dabei auf diesem Kohlepapier, ohne das im Briefumschlag liegende Dokument zu sehen. Danach erhält der Empfänger den Briefumschlag und somit die unterschriebene Nachricht. Interactive Signaturverfahren zwischen einem Sender und einem Empfänger nennt man blinde Signaturverfahren, wenn der Sender (Signierer) nicht “sieht”, welche Nachricht er unterschreibt (Blindheit). Gleichzeitig darf der Empfänger nicht in der Lage sein, mehr unterschriebene Nachrichten auszugeben, als Protokollausführungen stattfanden (Unfälschbarkeit). Typische Anwendungen dieser Signaturverfahren sind unter anderem e-cash oder e-voting. Blinde Signaturen stellen ein wichtiges Primitiv in der Kryptographie dar. Obwohl diese Signaturverfahren seit vielen Jahren breit erforscht wurden, beruhen die bekannten Lö- sungen entweder auf sehr starken Annahmen, oder weisen einen hohen Interaktions- aufwand auf. Aus diesem Grund befasst sich diese Dissertation sowohl mit dem Inter- aktionssaufwand, als auch mit den minimalen Annahmen von blinden Signaturen. Diese Arbeit beweist, dass es für eine große Klasse von blinden Signaturverfahren, bei denen höchstens drei Interaktionen zwischen dem Sender und dem Empfänger statt finden, keinen Black-Box Beweis im Standardmodell gibt. Charakteristisch für diese Klasse ist, dass man von der öffentlichen Kommunikation entscheiden kann, ob der Empfänger eine gültige Signatur erhält, oder nicht. Des Weiteren wird gezeigt, dass die Gruppe von eindeutigen blinden Signaturverfahren in Oblivious-Transfer-Protokolle überführt werden kann. Diese Gruppe zeichnet sich dadurch aus, dass jede Nachricht pro öffentlichem Schlüssel genau eine Signatur besitzt. Von Oblivious-Transfer-Verfahren ist bereits bekannt, dass diese nicht aus one-way Funktionen konstruiert (black-box) werden kann. Somit gillt dieses Resultat ebenfalls für blinde Signaturverfahren. Ferner wird bewiesen, dass es keine black-box Konstruktionen von blinden Signaturen basierend auf one-way Funktionen gibt. Dieses Ergebnis wird dahin gehend verall- gemeinert, dass nicht nur Ansätze basierend auf einer zufälligen Permutation aus- geschlossen werden können, sondern auch Protokolle, die einen 1-bit Nachrichtenraum besitzen und nur Sicherheit gegen honest-but-curious Angreifer garantieren.