Nicht kommutative Gruppe mit "Faktorisierungsproblem" |
| 20.12.2010, 19:45 | Kai___ | Auf diesen Beitrag antworten » | ||
| Nicht kommutative Gruppe mit "Faktorisierungsproblem" Hallo zusammen. Ich habe folgendes Problem: Ich brauche eine Gruppe, welche nicht-abelsch ist. Diese muss darueberhinaus noch endlich und das Problem des Faktorisierungsproblem beinhalten. Meine Ideen: Meine erste Idee war Matrizen über $Z_p$ zu nehmen. Allerdings lassen diese sich ja relativ schnell zerlegen. (Dreieckszerlegung und das ganze andere, was sich die Numeriker immer ausdenken 
Dann wollte ich komplexe Zahlen nehmen, diese sind allerdings abelsch bezüglich *. Dann kam ich auf Quaternionen, diese sind allerdings, wenn man nur endlich viele Elemente hat automatisch kommutativ. (Satz von Wedderburn) Gibt es solche Gruppen? Wenn ja, sind diese effektiv berechenbar? Grüße und schonmal Danke, Kai |
||||
| 20.12.2010, 20:40 | kiste | Auf diesen Beitrag antworten » | ||
Würdest du die Eigenschaft "Faktorisierungsproblem" noch erklären? |
||||
| 20.12.2010, 21:06 | Kai__ | Auf diesen Beitrag antworten » | ||
| Faktorisierungsproblem Hallo Kiste, natürlich. In diesem Fall geht es darum, dass jemand nicht wissen soll, was "aufmultipliziert" worden ist UND nicht in der Lage sein soll, wie es z.B. bei Matrizen der Fall wäre, andere Elemente aufzumultiplizieren, die genau das selbe Ergebnis liefern. (In diesem Fall sei angenommen, dass dieser Person nur polynomiell viel Rechenzeit zur Verfügung steht) Brauche dies für eine kryptographische Anwendung, find aber leider gerade keine Gruppe wo so etwas geht. |
||||
| 20.12.2010, 21:30 | kiste | Auf diesen Beitrag antworten » | ||
Das ist mir leider noch zu ungenau, kannst du genau spezifizieren welche Eigenschaft du haben möchtest? Wenn du ein Element a hast und ein Element b, und b entstanden ist durch ax, so lässt sich x doch berechnen durch x = a^-1*b. Wie soll man das nicht herausfinden können? Polynomiell viel Rechenzeit in welcher Eingabegröße? |
||||
| 20.12.2010, 22:12 | Kai__ | Auf diesen Beitrag antworten » | ||
Hallo Kiste, (sehr verkürzt) was ich erreichen möchte ist ein aggregierenden Hash, indem die Reihenfolge beachtet werden muss. Beispielweise sei eine (gescheite) elliptische Kurve E(F_q) gegeben. Nun kann ich einen Startwert mittels einer Zufallszahl s \in q übernehmen. Beispielweise Q := sP. In dem Fall sei P ist ein "guter" Punkt. Nun kann ich weitere Werte auf dieser Kurve aggregieren, nämlich mit folgender Vorschrift: Q \leftarrow mQ Diese Methode kann ich für beliebige m \in Z_q durchführen. Damit habe ich die Werte auf der Kurve "gehashed". Für einen "Angreifer" ist es sehr schwer t aus der Gleichung Q = tP zu berechnen. Das impliziert, dass es auch sehr schwer ist eine Kollision zu finden. Bei dieser Methode, wessen Beweis ich mir schon von meinem Prof überprüfen hab lassen, ist das Problem, dass die Reihenfolge in welcher ich auf die Kurve hashe, irrelevant ist. (Da Abelsch) Heisst umrissen: HASH(1||2) = HASH(2||1) == HASH(1||HASH(2)) (geht natürlich auch mit mehr Werten) Für das Signaturschema, welches im Rahmen meiner Thesis erdacht wurde ist dieser "Hash" perfekt. Nun kommts aber: Da ich aber diese Methode für ein weiteres, ähnliches, Signaturschema hernehmen möchte, brauche ich allerdings eine nicht-abelsche Modifikation/neue Idee derselben Herangehensweise. Deswegen auch die Idee mit den Matrizen; die wären perfekt gewesen, wenn sie denn nicht "aufsplittbar" wären. Daher suche ich jetzt nach einem ähnlichen Verfahren, welches jedoch eben die Reihenfolge relevant macht. Daher das "Faktorisierungsproblem" in Gänsefüßchen. (Bin eh der Meinung, dass DLP == FACTORING ist, aber das ist eine andere Baustelle) Hoffe, dass mein Problem nun klarer wird. Grüße, Kai |
||||
| 20.12.2010, 23:19 | Abakus | Auf diesen Beitrag antworten » | ||
Hallo! Zu deinem Problem kann ich wenig sagen; wenn Du nichtkommutative Gruppen suchst: schaue auf oder , die symmetrische bzw. alternierende Gruppe auf n Elementen. Grüße Abakus 
|
||||
| Anzeige | ||||
|
|
||||
| 20.12.2010, 23:27 | Kai__ | Auf diesen Beitrag antworten » | ||
Hallo Abakus, danke, an die hab ich auch schon gedacht; allerdings weiß ich nicht, wie schwer das finden von "Teilern" ist. Werd dann morgen doch mal an die Uni fahren müssen. 
Trotzdem danke an alle. Wenn mir der gute Prof gescheiten Input gibt, lass ich es euch wissen!
|
||||
| 21.12.2010, 00:00 | Abakus | Auf diesen Beitrag antworten » | ||
Jede endliche Gruppe lässt sich in so eine symmetrische Gruppe einbetten. Also viel anderes gibt es nicht, wenn es eine Gruppe sein soll. Grüße Abakus
|
||||
| 21.12.2010, 00:07 | Kai__ | Auf diesen Beitrag antworten » | ||
Gilt denn damit auch, dass das Finden von "Teilern" schwer ist? Naja, ich muss erstmal schlafen, das wird morgen ein harter Tag. 
|
||||
| 21.12.2010, 00:12 | Kai__ | Auf diesen Beitrag antworten » | ||
Bzw. was würdest Du denn vorschlagen, wenn es keine Gruppe sein soll? Ich mein Matrizen über NxN N>1 sind m.E. ja norm. keine Gruppe, da nicht alle Matrizen regulär sind. Genau wie E(K) mit P ja praktisch keine Gruppe bildet, da nicht sichergestellt werden kann, dass P wirklich ein Generator ist. Wichtig in diesem Zusammenhang ist mir, dass es es die Standardsachen von kryptographischen Hashes erfüllt, mit der EInschränkung, dass das DIng halt aggregieren muss. Wenn DU noch eine Idee hast, immer her damit
|
||||
| 22.12.2010, 16:13 | Kai__ | Auf diesen Beitrag antworten » | ||
Wie versprochen die Antwort auf mein Problem. Ist zwar DLP, aber das tuts auch: Zopfgruppe(n) (Engl: Braid Groups) Trotzdem nochmals danke an alle! |
||||
| 23.12.2010, 23:05 | Abakus | Auf diesen Beitrag antworten » | ||
Also das hier: Zopfgruppe (Wiki) Sieht jedenfalls interessant aus, ist mir jedoch neu. Grüße Abakus
|
||||
| 24.12.2010, 00:30 | kiste | Auf diesen Beitrag antworten » | ||
Ist aber nicht endlich
(dafür eben endlich präsentiert) |
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
