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 jedesmal gewinnt? Es könnte Zufall sein – die Wahr­schein­lich­keit dafür ist allerdings gering, nämlich 1 : 2n. Oder aber A ist in der Lage zu täuschen. Dann aber kennt er einen Iso­morphismus zwischen den zugrunde­liegenden Graphen G0 und G1.

Je öfter also das Protokoll wiederholt wird, wobei jedesmal A gewinnt, desto sicherer ist sich B, dass A einen Iso­morphismus zwischen G0 und G1 kennt.

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

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

Zero-Knowledge-Eigenschaft

Teilnehmer A braucht dabei jedoch den Iso­morphismus selbst nicht preiszugeben. Tatsächlich ist es sogar so, dass ein Dritter C, der den Nachrichten­austausch zwischen A und B abhört, daraus überhaupt keine Information gewinnt. Dies wird daran deutlich, dass ein Vierter D den Nachrichten­austausch 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 Iso­morphismus 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ßen­stehenden 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 Iso­morphismus h mit H = h(Gj) offenbart.

Da D keinerlei Information, die C nicht auch hat, in den simulierten Nachrichten­austausch hineinsteckt, kann C auch keine Information aus dem Nachrichten­austausch herausholen. Ein Protokoll, aus dessen Nachrichten­austausch 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   ©   Created: 04.12.2003   Updated: 11.06.2016
Valid HTML 4.01 Transitional


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