Secret Sharing Scheme < Krypt.+Kod.+Compalg. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 12:02 Di 11.01.2011 | | Autor: | susans |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Gibt es eine Methode, die mxn-Matrizen beliebig mit Elementen aus {0,1} besetzt, so dass diese Matrizen lösbar sind?
|
|
| |
|
Hallo,
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
>
> Gibt es eine Methode, die mxn-Matrizen beliebig mit
> Elementen aus {0,1} besetzt, so dass diese Matrizen lösbar
> sind?
Ach wie ich solche freundlichen und präzise gestellten Fragen mit einem netten "Hallo" zu Beginn und einem "Tschüß" am Ende liebe ...
Siehe Forenregeln oder Erziehung in der Kindheit!
Mann Mann Mann !!!
Was meinst du mit Matrizen sind "lösbar"?
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:58 Di 11.01.2011 | | Autor: | susans |
Hallo,
>Ach wie ich solche freundlichen und präzise gestellten >Fragen mit einem netten "Hallo" zu Beginn und einem >"Tschüß" am Ende liebe ...
Sorry, so weit habe ich gar nicht gedacht!
>Siehe Forenregeln oder Erziehung in der Kindheit!
Das sitzt! Das wird mir nicht mehr passieren!
>Was meinst du mit Matrizen sind "lösbar"?
Ich habe A*x=b ; b ist bekannt; Wie kann ich A belegen, so dass mit Gauss-Elimination dieses LGS eindeutig lösbar ist?
Viele Grüße,
Susan
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:01 Di 11.01.2011 | | Autor: | susans |
Hallo,
habe etwas vergessen:
A ist eine mxn-Matrix. Zeilen- und Spaltenanzahl werden angegeben.
Gruß,
Susan
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:40 Di 11.01.2011 | | Autor: | felixf |
Moin Susan!
> habe etwas vergessen:
>
> A ist eine mxn-Matrix. Zeilen- und Spaltenanzahl werden
> angegeben.
Bitte formuliere dein Problem mal praezise. Ansonsten kann man nicht wirklich antworten.
Erstmal noch eine Frage: ueber welchen Ring.Koerper soll das ganze stattfinden? [mm] $\IF_2$? [/mm] Oder [mm] $\IZ$ [/mm] bzw. [mm] $\IQ$?
[/mm]
Und wie geht das Problem jetzt genau? Du hast $m, n, b$ gegeben und willst wissen, ob es ein $A [mm] \in \{ 0, 1 \}^{m \times n}$ [/mm] gibt so dass $A x = b$ loesbar ist? Oder willst du ein solches $A$ finden? Oder willst du alle solchen $A$ finden? Oder willst du wissen, wieviele solche $A$ es gibt?
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:06 Di 11.01.2011 | | Autor: | susans |
Hey Felix,
danke für's antworten.
>Erstmal noch eine Frage: ueber welchen Ring.Koerper soll >das ganze stattfinden? ? Oder bzw. ?
[mm] Z_p [/mm] (p-Primzahl).
>Und wie geht das Problem jetzt genau?
Ich implementiere eine lineare Konstruktion eines Secret Sharing Schemes von van Dyjk.
Ich habe den Algorithmus bewiesen und auch in Java implementiert. Van Dijk gibt sechs Matrizen an für die seine Konstruktion korrekt ist. Andere Matrizen zu finden lässt er offen. Ihm ist keine Methode bekannt Matrizen so zu belegen, dass sie sein Theorem erfüllen.
> Du hast m, n, b gegeben
korrekt
Ich will wissen, ob ich ein A finden kann, so dass die Einheitsvektoren als Linearkombination der Spalten der Matrix A ausgedrückt werden können.
Und wenn solche A existieren, dann möchte ich sie finden.
Wenn man dann auch noch erfahren kann, wie viele solche A es gibt, dann auch das.
Viele Grüße,
Susan
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:35 Di 11.01.2011 | | Autor: | felixf |
Moin Susan!
> Hey Felix,
>
> danke für's antworten.
>
> >Erstmal noch eine Frage: ueber welchen Ring.Koerper soll
> >das ganze stattfinden? ? Oder bzw. ?
> [mm]Z_p[/mm] (p-Primzahl).
Ok, also ueber [mm] $\IF_p$ [/mm] (ist nur eine andere Schreibweise fuer [mm] $\IZ_p$, $\IZ/p\IZ$ [/mm] oder was auch immer).
> >Und wie geht das Problem jetzt genau?
> Ich implementiere eine lineare Konstruktion eines Secret
> Sharing Schemes von van Dyjk.
>
> Ich habe den Algorithmus bewiesen und auch in Java
> implementiert. Van Dijk gibt sechs Matrizen an für die
> seine Konstruktion korrekt ist. Andere Matrizen zu finden
> lässt er offen. Ihm ist keine Methode bekannt Matrizen so
> zu belegen, dass sie sein Theorem erfüllen.
Was genau besagt sein Problem? Kannst du eine genauere Referenz angeben (am besten mit Link zu einer freien PDF-Version des Papers)?
> > Du hast m, n, b gegeben
> korrekt
>
> Ich will wissen, ob ich ein A finden kann, so dass die
> Einheitsvektoren als Linearkombination der Spalten der
> Matrix A ausgedrückt werden können.
> Und wenn solche A existieren, dann möchte ich sie
> finden.
> Wenn man dann auch noch erfahren kann, wie viele solche A
> es gibt, dann auch das.
Du willst also ein $A$, so dass fuer jeden Einheitsvektor [mm] $e_i \in \IF_p^n$ [/mm] das LGS $A x = [mm] e_i$ [/mm] loesbar ist? Das bedeutet doch gerade, dass der Bildraum die Dimension $n$ hat, also die Matrix Rang $n$.
Das geht genau dann, wenn $m [mm] \ge [/mm] n$ ist. Und in dem Fall gibt es recht viele solcher Matrizen.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:10 Di 11.01.2011 | | Autor: | susans |
Hallo Felix,
> Was genau besagt sein Problem?
Ich habe eine zugelassene Teilnehmer-Konstellation, z.b. [1,2], ist gegeben. Jeder dieser Teilnehmer, also Teilnehmer 1 und Teilnehmer 2 haben jeweils eigene Teilmatrizen. Diese Teilmatrizen werden aneinander gehängt etc...
Das Problem liegt darin, wie ich jedem Teilnehmer eine geeignete Teilmatrix erzeuge, so dass für k-viele Einheitsvektoren das LGS lösbar ist.
> Kannst du eine genauere
> Referenz angeben (am besten mit Link zu einer freien
> PDF-Version des Papers)?
Einen freien Link kann ich nicht angeben. Ich habe nur einen Ausdruck. Könnte es morgen früh einscannen.
M. van Dijk, A linear construction of secret sharing schemes, Designs, Codes and Cryptography
12(2), 161-201, 1997.
> Du willst also ein A, so dass fuer jeden Einheitsvektor
> [mm] e_i [/mm] das LGS A*x = [mm] e_i [/mm] loesbar ist?
Ja, für k viele Einheitsvektoren. k ist die Dimension des Geheimnisses und dient als Schranke für die Theoreme, die erfüllt sein müssen.
> Das bedeutet doch gerade, dass der Bildraum die Dimension > n hat, also die Matrix Rang n.
Ja.
> Das geht genau dann, wenn m > n ist. Und in dem Fall
> gibt es recht viele solcher Matrizen.
Das bedeutet ja dann, dass sie existieren. Wie finde ich sie?
Viele Grüße,
Susan
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:23 Fr 14.01.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
