Diese Dissertation befasst sich mit zwei der wichtigsten Aspekte beim Entwurf von Public-Key Kryptosystemen: Beweisbare Sicherheit und Effizienz. Es steht außer Frage, dass Sicherheit eine unverzichtbare Eigenschaft jeder kryptographischen Anwendung ist. Nichtsdestotrotz vertrauten die Entwickler kryptographischer Verfahren lange Zeit der Methode von Versuch-und-Irrtum, d.h. ein Verfahren galt so lange als sicher, bis erfolgreiche Kryptanalyse eine Schwäche offenbarte. Im Gegensatz dazu bedient sich der Ansatz beweisbarer Sicherheit strenger mathematischer Beweise in wohldefinierten Sicherheitsmodellen. Heutzutage gilt beweisbare Sicherheit in vielen Bereichen als eine Standardforderung an ein Kryptosystem. Den Hauptbeitrag des ersten Teils dieser Arbeit bildet die Entwicklung und Analyse von neuen beweisbar sicheren Falltür-Einweg-Permutationen. (Falltür-)Einweg-Funktionen sind das wichtigste Primitiv in der Public-Key-Kryptographie, denn sie bilden den Hauptbaustein für zahlreiche kryptographische Anwendungen. Aus diesem Grunde, und nicht zuletzt weil nur äußerst wenige geeignete Kandidaten bekannt sind, ist die Entwicklung neuer (Falltür-)Einweg-Funktionen bereits für sich genommen von größtem Interesse. Um jedoch auch den praktischen Nutzen der vorgeschlagenen Konstruktionen unter Beweis zu stellen, werden beweisbar sichere Anwendungen aus den Bereichen homomorphe Verschlüsselung, Fail-Stop Signaturen, hybride Verschlüsselung und Falltür-Hinterlegungsverfahren vorgestellt und analysiert. Der zweite Teil dieser Arbeit widmet sich der effizienten Implementierung von Algorithmen der Public-Key-Kryptographie. Neben der Sicherheit ist die Effizienz das Hauptbewertungsmerkmal kryptographischer Verfahren, denn ineffiziente Algorithmen sind unbrauchbar für praktische Anwendungen. In den heute weit verbreiteten mobilen Endgeräten mit beschränktem Speicherplatz sind Elliptische-Kurven-Kryptosysteme aufgrund ihrer moderaten Schlüssellängen die erste Wahl. Die häufigste Operation dieser Kryptosysteme ist die Skalarmultiplikation, daher ist die Entwicklung von Verfahren zu deren Beschleunigung ein vielbeachtetes Forschungsgebiet. Die vorliegende Arbeit beschäftigt sich speziell mit Multiplikations-Algorithmen, die geringe Anforderungen an den Speicherplatz stellen. Es wird ein neuer Algorithms entworfen, der ebenso effizient ist wie die "state-of-the-art" Lösung, allerdings bei signifikant geringerem Speicherbedarf. Desweiteren wird eine Variante dieses Algorithmus entwickelt, die exakt an den zur Verfügung stehenden Speicherplatz angepasst werden kann, so dass keine wertvollen Ressourcen verschwendet werden müssen. Die vorgestellten Verfahren erweisen sich also als besonders nützlich für die Implementierung auf speicherbeschränkten Medien wie Smart-Cards.