Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Психикалық покер – сенімді үшінші тараптың қатысуынсыз қашықтықтан әділ ойын ойнауға қатысты криптографиялық мәселелер жиынтығының жалпы атауы. Бұл термин сондай-ақ осы мәселелерді және олардың мүмкін шешімдерін зерттейтін теорияларға да қолданылады. Атау покер карта ойынынан алынған, себебі осы мәселелердің бірі осы ойынға қатысты. Екі тарапты ойын ретінде сипатталатын ұқсас мәселелерге Блумның қашықтықтан монета лақтыруы, Яоның «Миллионерлер мәселесі» және Рабиннің жасырын ауыстыруы жатады. Мәселені былай қоюға болады: «Сенімді төрешіге жүгінбестен, белгілі бір ақпаратқа тек рұқсат етілген тұлғалардың ғана қол жеткізуін қалай қамтамасыз етуге болады?» (Сенімді үшінші тарапты жою, оның сенімділігін анықтау қажеттілігінен құтылуға және қажетті ресурстарды азайтуға мүмкіндік береді.) Покерде бұл мынадай сұраққа айналады: «Біз өз қолымыздағы карталарды араластырып жатқанда, ешбір ойыншының колоданы өзгертіп немесе басқа ойыншылардың карталарын қарап алмауына қалай кепілдік беруге болады?» Дәстүрлі карта ойынында, егер ойыншылар бетпе-бет отырып, бір-бірін бақыласа, бұл салыстырмалы түрде оңай болар еді, кем дегенде, әдеттегі алдау мүмкіндігі жоқ болса. Алайда, егер ойыншылар бір-бірінен қашық жерде отырса және бүкіл колоданы бір-біріне жіберсе (мысалы, почта арқылы), бұл кенеттен өте қиынға соғады. Онлайн-покер сияқты электрондық карта ойындарында, ойынның механизмдері пайдаланушыдан жасырылғандықтан, егер қолданылатын әдіс кез келген тарапқа электрондық «колоданы» манипуляциялау немесе орынсыз бақылау арқылы алдауға мүмкіндік бермейтін болса, мұндай ойын мүмкін емес. Мұны істеу үшін бірнеше протокол ұсынылды, алғашқысын Ади Шамир, Рон Ривест және Лен Адлеман (RSA шифрлау протоколының авторлары) жасады. Бұл протокол екі тараптың қауіпсіз хабар алмасудың орнына криптографияны қолдана отырып, қауіпсіз есептеулер жүргізуінің алғашқы мысалы болды. Кейіннен бастапқы протоколдан ішінара ақпараттың жария болуына байланысты Шафи Голдвассер мен Сильвио Микали семантикалық қауіпсіздік тұжырымдамасын ұсынды. Көп ойыншылы психикалық покер тұжырымдамасы Моти Юнгтың 1984 жылғы «Криптопротоколдар» кітабында енгізілді. Бұл сала кейіннен қауіпсіз көп тарапты есептеу протоколдары (екі тарапты және көп тарапты) деп аталатын бағытқа дамыды.
Mental poker is the common name for a set of cryptographic problems that concerns playing a fair game over distance without the need for a trusted third party. The term is also applied to the theories surrounding these problems and their possible solutions. The name comes from the card game poker which is one of the games to which this kind of problem applies. Similar problems described as two party games are Blum's flipping a coin over a distance, Yao's Millionaires' Problem, and Rabin's oblivious transfer. The problem can be described thus: "How can one allow only authorized actors to have access to certain information while not using a trusted arbiter?" (Eliminating the trusted third party avoids the problem of trying to determine whether the third party can be trusted or not, and may also reduce the resources required.) In poker, this could translate to: "How can we make sure no player is stacking the deck or peeking at other players' cards when we are shuffling the deck ourselves?". In a physical card game, this would be relatively simple if the players were sitting face to face and observing each other, at least if the possibility of conventional cheating can be ruled out. However, if the players are not sitting at the same location but instead are at widely separate locations and pass the entire deck between them (using the postal mail, for instance), this suddenly becomes very difficult. And for electronic card games, such as online poker, where the mechanics of the game are hidden from the user, this is impossible unless the method used is such that it cannot allow any party to cheat by manipulating or inappropriately observing the electronic "deck". Several protocols for doing this have been suggested, the first by Adi Shamir, Ron Rivest and Len Adleman (the creators of the RSA encryption protocol). This protocol was the first example of two parties conducting secure computation rather than secure message transmission, employing cryptography; later on due to leaking partial information in the original protocol, this led to the definition of semantic security by Shafi Goldwasser and Silvio Micali. The concept of multi player mental poker was introduced in Moti Yung's 1984 book Cryptoprotocols. The area has later evolved into what is known as secure multi party computation protocols (for two parties, and multi parties as well).
Коммутативтік шифрлауды қолдана отырып, карталарды араластыру
Карталарды сенімді үшінші тарапсыз араластырудың бір мүмкін алгоритмі – коммутативті шифрлау схемасын қолдану. Коммутативті схема дегеніміз, егер дерек бірнеше рет шифрланса, осы деректерді шешу реті маңызды болмайды. Мысалы: Алиса жазылмаған мәтіннен хабарламаға ие. Ол оны шифрлап, бұрмаланған шифрмәтінді алады, содан кейін оны Бобқа береді. Боб сол схеманы Алиса қолданғандай, бірақ басқа кілтпен шифрмәтінді қайта шифрлайды. Шифрлау схемасы коммутативті болса, кім алдымен шешіп алатынының маңызы жоқ.
One possible algorithm for shuffling cards without the use of a trusted third party is to use a commutative encryption scheme. A commutative scheme means that if some data is encrypted more than once, the order in which one decrypts this data will not matter. Example: Alice has a plaintext message. She encrypts this, producing a garbled ciphertext which she gives then to Bob. Bob encrypts the ciphertext again, using the same scheme as Alice but with another key. When decrypting this double encrypted message, if the encryption scheme is commutative, it will not matter who decrypts first.
Әлсіздік
Шифрлау схемасы белгілі ашық мәтіндік шабуылдарға қарсы қауіпсіз болуы керек: Боб Алисаның бастапқы кілтін (немесе оның жеткілікті бөлігін) оның тартқан карталарының шифрланбаған мәндерін білу арқылы анықтай алмауы керек, бұл оған қолында жоқ карталарды шифрдан алуға мүмкіндік бермеуі тиіс. Бұл, мысалы, әр картаны кілтпен XOR операциясы арқылы шифрлеу сияқты, қарапайым коммутативті шифрлау схемаларын жоққа шығарады. (Бастапқы алмасу кезінде әр карта үшін жеке кілт қолдану, бұл схеманы қауіпсіз ететін болса да, карталар қайтарылғанға дейін шатастырылғандықтан жұмыс істемейді.) Келісілген колодаға байланысты бұл алгоритм нашар болуы мүмкін. Деректерді шифрлеген кезде, осы деректердің белгілі бір қасиеттері ашық мәтіннен шифрланған мәтінге дейін сақталуы мүмкін. Бұл белгілі бір карталарды "маркулап" қою үшін пайдаланылуы мүмкін. Сондықтан тараптар шифрлеу кезінде қасиеттері сақталмайтын карталардан тұратын колода туралы келісуі керек.
The encryption scheme used must be secure against known plaintext attacks: Bob must not be able to determine Alice's original key A (or enough of it to allow him to decrypt any cards he does not hold) based on his knowledge of the unencrypted values of the cards he has drawn. This rules out some obvious commutative encryption schemes, such as simply XORing each card with the key. (Using a separate key for each card even in the initial exchange, which would otherwise make this scheme secure, doesn't work since the cards are shuffled before they're returned.) Depending on the deck agreed upon, this algorithm may be weak. When encrypting data, certain properties of this data may be preserved from the plaintext to the ciphertext. This may be used to "tag" certain cards. Therefore, the parties must agree on a deck where no cards have properties that are preserved during encryption.
"Ақылы карта ойындары үшін құралдар қорабы" және оны іске асыру
Кристиан Шиндельгауэр өзінің 1998 жылғы "Ақыл-ойын карта ойындары үшін құралдар жинағы" [SCH98] атты мақаласында карталар мен карталар тізбегінде көптеген пайдалы операцияларды орындау және тексеру үшін күрделі протоколдарды сипаттайды. Бұл жұмыс жалпы мақсаттағы операцияларға (карталарды жасыру және ашу, араластыру және қайта араластыру, тізбекке карта қосу және т.б.) қатысты, бұл протоколдарды кез келген карта ойынына қолдануға мүмкіндік береді. Шиндельгауэр қолданған криптографиялық протоколдар квадраттық қалдықтарға негізделген, ал жалпы схема осы жоғарыдағы протоколға ұқсас. Операциялардың дұрыстығын нөлдік білімді дәлелдер арқылы тексеруге болады, сондықтан ойыншылар ойынның дұрыстығын тексеру үшін өз стратегияларын ашуға міндетті емес. C++ libtmcg [STA05] кітапханасы Шиндельгауэр құралдар жинағының іске асырылуын қамтамасыз етеді. Ол неміс карта ойыны Skat-тың қауіпсіз нұсқасын іске асыру үшін қолданылды, соның нәтижесінде нақты қолданыстағы өнімділік шамалы болды. Skat ойынын үш ойыншы 32 картадан тұратын колодамен ойнайды, сондықтан ол бес-сегіз ойыншы толық 52 картадан тұратын колоданы пайдаланатын покер ойынына қарағанда есептеулер жағынан аз күш кетіреді.
Christian Schindelhauer describes sophisticated protocols to both perform and verify a large number of useful operations on cards and stacks of cards in his 1998 paper "A Toolbox for Mental Card Games" [SCH98]. The work is concerned with general purpose operations (masking and unmasking cards, shuffling and re shuffling, inserting a card into a stack, etc.) that make the protocols applicable to any card game. The cryptographic protocols used by Schindelhauer are based on quadratic residuosity, and the general scheme is similar in spirit to the above protocol. The correctness of operations can be checked by using zero knowledge proofs, so that players do not need to reveal their strategy to verify the game's correctness. The C++ library libtmcg [STA05] provides an implementation of the Schindelhauer toolbox. It has been used to implement a secure version of the German card game Skat, achieving modest real world performance. The game Skat is played by three players with a 32 card deck, and so is substantially less computationally intensive than a poker game in which anywhere from five to eight players use a full 52 card deck.