Kryptografische Protokolle

Teilnehmer-Authentifizierung mit Zero-Knowledge-Protokoll

 aufwärts

Graph-Isomorphismus-Protokoll

Das Bit-Commitment-Protokoll aus dem letzten Abschnitt basiert auf der Isormorphie von Graphen. Es kann von zwei Teilnehmern A und B verwendet werden, um eine Münze zu werfen. A legt sich auf i fest, B wählt j, A deckt i auf und hat gewonnen, wenn i = j ist.

Was ist, wenn dieses Protokoll n-mal wiederholt wird und A jedes Mal gewinnt? Es könnte Zufall sein – die Wahrscheinlichkeit dafür ist allerdings gering, nämlich 1 : 2n. Oder aber A ist in der Lage zu täuschen. Dann aber kennt er einen Isomorphismus zwischen den zugrunde liegenden Graphen G0 und G1.

Je öfter also das Protokoll wiederholt wird, wobei jedes Mal A gewinnt, desto sicherer ist sich B, dass A einen Isomorphismus zwischen G0 und G1 kennt.

Das Protokoll kann somit von Teilnehmer A verwendet werden, um sich zu authentifizieren. Er kann beweisen, dass er einen Isomorphismus zwischen den beiden Graphen kennt; dies ist sein Identitätsmerkmal.

Beim Bit-Commitment erzeugt Teilnehmer B die beiden Graphen, um sicherzustellen, dass niemand anderer den Isomorphismus kennt (und dadurch täuschen kann). Bei der Teilnehmer-Authentifizierung erzeugt A die beiden Graphen, um sicherzustellen, dass niemand anderer den Isomorphismus kennt (und dadurch sich als A ausgeben kann).

Zero-Knowledge-Eigenschaft

Teilnehmer A braucht dabei jedoch den Isomorphismus selbst nicht preiszugeben. Tatsächlich ist es sogar so, dass ein Dritter C, der den Nachrichtenaustausch zwischen A und B abhört, daraus überhaupt keine Information gewinnt. Dies wird daran deutlich, dass ein Vierter D den Nachrichtenaustausch zwischen A und B simulieren könnte, ohne dass C dies merken würde.

Hierzu muss D lediglich in jeder Runde ein zufälliges Bit j und einen zufälligen Isomorphismus h wählen, H = h(Gj) berechnen und an B senden, daraufhin das gewählte Bit j an A senden und daraufhin h an B senden (Bild 1).

  
A  B
  
Bild 1: Bit-Commitment-Protokoll

Einem Außenstehenden C erscheint es so, als ob A sich durch Senden des Graphen H auf ein bestimmtes Bit festlegt, als ob daraufhin B ein zufälliges Bit j würfelt, und als ob daraufhin A zeigt, dass er sich auf eben dieses j festgelegt hat, indem er nämlich den Isomorphismus h mit H = h(Gj) offenbart.

Da D keinerlei Information, die C nicht auch hat, in den simulierten Nachrichtenaustausch hineinsteckt, kann C auch keine Information aus dem Nachrichtenaustausch herausholen. Ein Protokoll, aus dessen Nachrichtenaustausch keine Information gewonnen werden kann, hat die Zero-Knowledge-Eigenschaft.

Literatur

[BNS 05]A. Beutelspacher, H.B. Neumann, T. Schwarzpaul: Kryptografie in Theorie und Praxis. Vieweg (2005)

 

Weiter mit:   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©   Created: 04.12.2003   Updated: 08.06.2018
Valid HTML 4.01 Transitional

Hochschule Flensburg
Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik