Fórumok
Egy kis kártyajáték implementációjának tervezése közben lukadtam ki az alábbi problémára:
A, B, C és D kártyáznának távolról, kölcsönösen ismerik egymás nyílt kulcsait.
Kellene generálni egy leosztást (N lap egy permutációját) úgy, hogy minden játékos biztos lehessen benne, véletlenszerű a leosztás már a játék elején, de ne ismerje a többi játékos lapjait, csak a sajátjait. Zero-knowledge proof?
Valahogy úgy indulnék neki, mint a Diffie-Hellman kulcsgenerálásnál, de lényeges szempont, hogy a résztvevők ne ismerhesség meg a teljes kulcsot.
Van valami ötletetek, milyen irányba nézelődjek analóg problémák iránt?
Köszi
Hozzászólások
Ez nekem nagyon is hasonlít egy titokmegosztási problémára-
A titok, hogy kinél milyen lapok vannak, és mindenki csak a saját lapjait tudja.
Innen indulnék el: https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing
Arra kidolgoztam egy sémát, hogy hogyan tudják a résztvevők laponként, ellenőrizhetően elárulni a titkukat, de arra ezzel sem látom az irányt, hogy a kezdeti titok, a leosztás kialakuljon úgy, hogy kizárható legyen az összejátszás. Tehát egy résztvevő magában is ki tudja kényszeríteni a véletlenszerű leosztást vagy ellenőrizni tudja, hogy a többi résztvevő nem csal.
Mondjuk nem mélyedtem el benne, majd este. Köszi
Hogy érted, hogy csalna a többi résztvevő?
Egyvalaki (az osztó) generálja a leosztást, generál N darab titkot, ami tartalmaz információkat arról, hogy kinek milyen lapja van, de az összes N titok kell ahhoz, hogy kiderüljün, mi is volt a generált leosztás.
Nem értem a "kikényszeríteni a véletlenszerű leosztás" dolgot, meg az ellenőrzést, hogy a többi nem csal. Ki generálja a leosztást? Ki az osztó?
Igen, ez a kérdés, ki akarom hagyni az osztót. :)
Nem tudom lehetséges-e egyáltalán, de valami azt súgja, hogy az.
A kártyajátéknál mindig van osztó. Minden játék így indul.
Olyan nincs, hogy mindenki osztó, vagy senki sem osztó. Kell lennie egy független harmadik félnek, aki nem játszik, és nincs érdeke csalni az osztásnál senki felé.
Tud-e a négy játékosnak egy közös titkot generálni, amit egyik sem ismer teljesen, csak részlegesen?
Van ugye N szereplőd (játékos). Nekik kell közösen megállapodniuk egy S titokban, amelye igaz:
1. Minden szereplőnek van egy S_i titka, amit ő véletlenszerűen (vagy bárhogy - pl. mindig enyém két ász - generál), amelyekből generálódik S.
2. Az S titok teljes ismeretében sem lehet megtudni, hogy az egyes S_i-k micsodák.
3. Ellenőrizni lehet S ismeretében azt, hogy egyik S_i sem egyezik meg semelyik S_j-vel, anélkül, hogy tudnánk S_i és S_j értékét.
Találtam egy ilyet a témához:
https://en.wikipedia.org/wiki/Secure_multi-party_computation
Azt hiszem lesz olvasnivalóm egy időre.
a bitcoin vanity address generalasban van valami hasonlo moka a privkey es a publickey-ekkel.
--
A vegtelen ciklus is vegeter egyszer, csak kelloen eros hardver kell hozza!
Ha kihagyod az osztót, az azt jelenti, hogy nincs információ-asszimetria a rendszerben (mert amúgy van: az osztó ismeri a leosztást, a többiek nem).
Ha mindenki ugyanannyi információval rendelkezik arról, hogy éppen melyik leosztást játsszák le (és tudja verifikálni, hogy a többiek ugyanazt játsszák le, mint ő), az azt jelenti, hogy mindenkinek megvan a teljes információ arról, hogy mi a leosztás, azaz mindenki látja a többiek lapjait is. Ennek semmi értelme. Kell lennie információ-asszimetriának.
A Shamir-féle titokmegosztásban is van ilyen: aki a titokmegosztást csinálja (az osztó) tud mindent, a titokdarabok tudói meg épp csak annyit, ami nekik kell.
A privát kulcsok nem ismertek, azt lehetne felhasználni szerintem, míg a nyílt kulcsok ismertek. Persze nem vagyok szakmabeli, uh csak kibicelek.
Egy "parti" szerver felállítása. ~15 éve csak a vizsgafeladatom vége felé jutott eszembe, így az implementáció elmaradt. Az oktatóm gyanakvó szemekkel nézett rám az ötlet miatt, hogy root jogot adjon a szerverre a teszt telepítések miatt ;)
Maradtam az osztó/csatlakozó megoldás mellett.
Lehet benne valami ...
Ha a kártyapakli "végtelen" akkor viszonylag egyszerűen megoldható lehet. Ha véges akkor nem igazán tudod megoldani hogy kiszűrd az ütközéseket és mégse tudja minden fél a másik lapjait.
https://en.wikipedia.org/wiki/Mental_poker
http://www.nongnu.org/libtmcg/
Azt hiszem megtaláltam, amit kerestem.