Hiho,
erstmal vorweg: Es geht mir nicht darum, wie man mein Problem in welcher Sprache auch immer realisiert, sondern um die theoretische Lösung des Problems:

Ich habe eine Datenbank (f: |N -> |N) in der zu einigen (n Stück) Schlüsseln bestimmte Werte gespeichert sind. Natürlich existieren nicht alle möglichen Schlüssel.

Daraus will ich eine Datenbank (g: |N -> |N) folgender Art erzeugen:
sofern ein Schlüssel in f existiert, soll mir der Aufruf von g den gleichen Wert wie der Aufruf von f geben. Zudem kann ich an g nicht erkennen, welche Schlüssel in f existieren, dh. jeder Schlüssel gibt mir irgendeinen Wert zurück.

Mir ist natürlich klar, daß eine Triviallösung des Problems wäre, zu allen möglichen Schlüsseln irgendwas abzuspeichern, aber das wäre zu speicheraufwendig.

Die Gedanken, die ich mir bislang gemacht hab:
Irgendein Polynom n+1sten Grades nehmen, was an meinen Werten ein korrektes Ergebnis liefert. Das Problem dabei ist es die Koeffizienten zu bestimmen, ohne zu verraten, wie meine Schlüssel aussehen.

Fällt da irgenwem was besseres ein? Oder ne Idee, wie man die Koeffizienten geschickt bestimmen könnte?

edit pq: sieben Schlüßel entfernt und durch Schlüssel ersetzt =)\n\n

<!--EDIT|pq|1091792334-->

(f: |N -> |N) geht doch schonmal nicht, weil du eine Datenbank hast, oder? :)

was gibt g zurück, wenn f den Schlüssel nicht hat? Und habe ich das richtig verstanden, wenn du g(i) aufrufst, soll dann f(i) zurück gegegeben werden, wenn f(i) existiert, oder wie?

(ich habe mal den titel geändert. 'verschlüßelt' tat mir in den augen weh... =)

Jep, hast du richtig verstanden. (f: |N -> |N) soll halt ausdrücken, daß sowol die Schlüssel wie auch die Werte natürlichzahlig sind. Wenn f(i) nicht existiert, dann soll irgendwas zurückgegeben werden, aber bei jedem Aufruf natürlich das gleiche, damit man auch bei mehrmaligem Aufruf nicht erkennt, ob der Wert jetzt in f enthalten ist.

achso; aber

wenn x != y und x,y nicht in f; dann soll wohl auch gelten
g(x) != g(y) oder?

das ist wirklich nicht so einfach...

du könntest, wenn f(x) einen wert liefert, dann gib f(x) zurück, ansonsten gib sha1(x) zurück => dadurch ist g(i) != g(j) für alle i != j und i,j nicht in f

das muß nicht gelten - die Werte in f sind auch nicht eindeutig.

Die von dir angesprochene Lösung setzt vorraus, daß ich ein Programm hab, was in einer Blackbox läuft und Daten raussendet - unter der vorraussetzung wäre es einfach. Ich will aber ein Programm haben, bei dem man alles genau auseinandernehmen kann und ruhig wissen kann, wie es funktioniert und es trotzdem nicht rausbekommt.

sprich - ich kann nicht die richtigen Werte abspeichern.

Die erste Frage die da zu klären ist, wäre: Willst du, dass g exakt die gleichen Werte wie f liefert? Wenn dir die Ergebnisse mit einer kleinen Ungenauigkeit reichen ist es viel einfacher! Dann musst du dich noch fragen, wie zuverlässig das Speichersystem sein muss. Wenn du zum Beispiel erlaubst, dass beim Schreiben in g Daten kaputtgehen dürfen, dann wird's auch einfacher. Wenn du aber volle Zuverlässigkeit haben möchtest, weiß ich so auf Anhieb keine Hundertprozentige Lösung, außer die Datenbank eben mit Zufallswerten aufzufüllen.

kannst du nicht rsa dafür benutzen??

[quote=renee,05.08.2004, 16:56]kannst du nicht rsa dafür benutzen??[/quote]
dann bräuchte er ja public und private key für.

Schreiben in g muß nicht möglich sein. Das war vielleicht nicht klar in meiner Erklärung. f ist eine ganz normale Datenbank, aus der - sobald mir die Daten passen - g erzeugt werden soll und g bleibt dann konstant.

RSA geht deshalb nicht, weil der Benutzer zu den geeigneten Werten ja immer noch die richtigen Ergebnisse auslesen können muß. Dh. er muß entweder den Schlüssel haben (bringt dann nichts) oder er vergleicht die verschlüsselten Werte - dann weiß er aber sofort, zu welchem Schlüssel ein Wert existiert.

Mein aktueller Ansatz ist es aus dem übergebenen Schlüssel eine möglichst kurze Prüfsumme zu bilden, die über meiner Schlüsselmenge keine Kollisionen mit unterschiedlichen Werten hat und dort dann alle möglichen Prüfsummen mit Werten versehen. Allerdings reduziert das das Problem nur und löst es nicht.