Kártyajáték és Kriptográfia

Algoritmusok

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

  • 2145 megtekintés

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ó?

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.

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.

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.

( hzsolt94 v | 2015. 12. 02., sze – 00:23 )

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.