Құпиялы сақталатын көп тарапты есептеулер

Кіріспе

Шифрлаудың кіші саласы

Қауіпсіз көп тарапты есептеу (қауіпсіз есептеу, көп тарапты есептеу (MPC) немесе құпиялылықты сақтау есептеу деп те аталады) – криптографияның кіші саласы болып табылады, оның мақсаты тараптардың өздерінің деректерін құпия ұстай отырып, осы деректер бойынша бірлесіп функцияны есептеу әдістерін жасау. Дәстүрлі криптографиялық міндеттерден айырмашылығы, онда криптография байланыс немесе сақтаудың қауіпсіздігі мен толықтығын қамтамасыз етеді және қарсылас қатысушылар жүйесінен тыс болады (жіберуші мен алушыны тыңдаушы), бұл модельдегі криптография қатысушылардың бір-бірінен құпиялылығын қорғайды. Қауіпсіз көп тарапты есептеудің негізі 1970 жылдардың соңында ойындық покер жұмысымен қаланды, бұл криптографиялық жұмыс сенімді үшінші тарапты қажет етпей, қашықтықтан ойын ойнау/есептеу міндеттерін симуляциялайды. Дәстүрлі түрде криптография мазмұнды жасырумен байланысты болса, ал осы жаңа есептеу түрі мен протоколы – көптеген дерек көздерінен алынған деректерді есептеу кезінде деректер туралы ішінара ақпаратты жасыру және дұрыс нәтижелерді шығарумен байланысты. 1980 жылдардың соңында Майкл Бен-Ор, Шафи Голдвассер және Ави Вигдерсон, сондай-ақ тәуелсіз түрде Дэвид Шоум, Клод Крепо және Иван Дамгард «қауіпсіз арналар жағдайында кез келген функцияны қауіпсіз есептеу қалай жүзеге асырылатынын» көрсететін мақалалар жариялады.

Тарих

Арнайы мақсаттағы протоколдар 1970 жылдардың соңында қолданысқа енді. Кейіннен, 1982 жылы қауіпсіз есептеу ресми түрде екі тарапты қауіпсіз есептеу (2PC) түрінде ұсынылды (миллионерлердің мәселесі деп аталатын, бульдік предикат болатын нақты мәселе үшін), ал 1986 жылы Эндрю Яо барлық мүмкін есептеулер үшін жалпылама түрде енгізілді. Бұл сала Secure Function Evaluation (SFE) деп те аталады. Екі тарапты жағдайды Одед Голдрейх, Сильвио Микали және Ави Вигдерсон көп тарапты жағдайға кеңейтті. Есептеу барлық кіріс деректерін құпия бөлісу және қастандық жағдайында нөлдік білімді дәлелдеу негізінде жүзеге асырылады, онда қастандық қарсыластың жағдайында адал ойыншылардың көпшілігі жаман мінез-құлықты анықтап, адал емес тұлғаны жоюмен немесе оның кірісін ашумен есептеуді жалғастырады. Бұл жұмыс қауіпсіз есептеу үшін болашақтағы барлық көп тарапты протоколдарда қолданылатын негізгі жалпы схеманы ұсынды. Бұл жұмыс GMW парадигмасы деп аталатын, жартылай адал қарсыластарға қарсы қауіпсіз, қастандық қарсыластарға қарсы қауіпсіз көп тарапты есептеу протоколын құрастыру тәсілін енгізді. Бұл жұмыстың нәтижесінде бірінші сенімді қауіпсіз протокол пайда болды, ол ешкімнің нәтижесін ашпай, қате мінез-құлықты мейірімділікпен қабылдайды, бұл мақсатта жиі қолданылатын "үлестің үлесі" идеясы және тараптардың біріне өз кірісін шартты түрде жасыруға мүмкіндік беретін протокол ойлап табылды. GMW парадигмасы негізгі протоколға әкелетін үлкен шығындарға байланысты көп жылдар бойы тиімсіз деп есептелді. Алайда, тиімді протоколдар жасау мүмкіндігі көрсетілді, бұл зерттеу бағытын практикалық тұрғыдан одан да қызықты етеді. Жоғарыда аталған нәтижелер қарсылас полиномиалдық уақыт есептеулерімен шектелген және барлық байланысты бақылайтын модельде алынды, сондықтан бұл модель "есептеулік модель" деп аталады. Сонымен қатар, бұл міндеттер үшін жасырын беру протоколының толық екендігі дәлелденді. Жоғарыда аталған нәтижелер пайдаланушылардың көпшілігі адал болған жағдайда қауіпсіз есептеуді жүзеге асыру мүмкіндігін көрсетті. Келесі шешілмейтін мәселе – қарсыласқа нүктеден нүктеге байланыс қолжетімді емес қауіпсіз байланыс арналарының жағдайы болды; бұл жағдайда тараптардың 1/3-і дұрыс емес және қастандық жасаған жағдайда шешімдерге қол жеткізуге болады, ал шешімдер криптографиялық құралдарды қолданбайды (қауіпсіз байланыс қолжетімді болғандықтан). Тарату арнасын қосу жүйеге азшылықтың жартысына дейін түзетуге мүмкіндік береді, ал байланыс графигіндегі байланыс шектеулері Perfectly Secure Message Transmission кітабында зерттелді. Жылдар өте келе, жалпы мақсаттағы көп тарапты протоколдар ұғымы, жалпы және негізгі протокол мәселелерін зерттеу үшін өнімді салаға айналды, мысалы, әмбебап құрастырылатындық немесе проактивті құпия бөлісудегі мобильді қарсылас. 2000 жылдардың соңынан бастап, әсіресе 2010 жылдан бастап, жалпы мақсаттағы протоколдар саласы практикалық қолдануларды ескере отырып, протоколдардың тиімділігін арттыруға көшті. MPC үшін тиімді протоколдар ұсынылды және MPC-ні әртүрлі нақты өмірлік мәселелерді шешу үшін практикалық шешім ретінде қарастыруға болады (әсіресе құпияларды тек сызықтық түрде бөлісуді және негізінен тараптар арасындағы өзара әрекеттесуі аз акцияларға жергілікті операцияларды қажет ететіндер), мысалы, үлестірілген дауыс беру, жеке сауда-саттық және аукциондар, қолтаңба немесе шифрлау функцияларын бөлісу және жеке ақпаратты алу. Көп тарапты есептеудің алғашқы кең ауқымды және практикалық қолданылуы 2008 жылдың қаңтар айында Данияның қант қызылшасы аукционында екі жақты электрондық аукционды өткізу болды. Әрине, теориялық ұғымдар мен зерттеулер, сондай-ақ қолданбалы құрылымдар қажет (мысалы, МКК-ні күнделікті бизнес құрамына енгізу шарттары ұсынылды және талқыланды). 2020 жылы қауіпсіз көп тарапты есептеумен жұмыс істейтін бірқатар компаниялар "MPC технологиясының танылуын, қабылдануын және пайдалануын жеделдету" мақсатымен MPC альянсын құрды.

Special purpose protocols for specific tasks started in the late 1970s. Later, secure computation was formally introduced as secure two party computation (2PC) in 1982 (for the so called Millionaires' Problem, a specific problem which is a Boolean predicate), and in generality (for any feasible computation) in 1986 by Andrew Yao. The area is also referred to as Secure Function Evaluation (SFE). The two party case was followed by a generalization to the multi party by Oded Goldreich, Silvio Micali, and Avi Wigderson. The computation is based on secret sharing of all the inputs and zero knowledge proofs for a potentially malicious case, where the majority of honest players in the malicious adversary case assure that bad behavior is detected and the computation continues with the dishonest person eliminated or his input revealed. This work suggested the very basic general scheme to be followed by essentially all future multi party protocols for secure computing. This work introduced an approach, known as GMW paradigm, for compiling a multi party computation protocol which is secure against semi honest adversaries to a protocol that is secure against malicious adversaries. This work was followed by the first robust secure protocol which tolerates faulty behavior graciously without revealing anyone's output via a work which invented for this purpose the often used `share of shares idea' and a protocol that allows one of the parties to hide its input unconditionally. The GMW paradigm was considered to be inefficient for years because of huge overheads that it brings to the base protocol. However, it is shown that it is possible to achieve efficient protocols, and it makes this line of research even more interesting from a practical perspective. The above results are in a model where the adversary is limited to polynomial time computations, and it observes all communications, and therefore the model is called the `computational model'. Further, the protocol of oblivious transfer was shown to be complete for these tasks. The above results established that it is possible under the above variations to achieve secure computation when the majority of users are honest. The next question to solve was the case of secure communication channels where the point to point communication is not available to the adversary; in this case it was shown that solutions can be achieved with up to 1/3 of the parties being misbehaving and malicious, and the solutions apply no cryptographic tools (since secure communication is available). Adding a broadcast channel allows the system to tolerate up to 1/2 misbehaving minority, whereas connectivity constraints on the communication graph were investigated in the book Perfectly Secure Message Transmission. Over the years, the notion of general purpose multi party protocols became a fertile area to investigate basic and general protocol issues properties on, such as universal composability or mobile adversary as in proactive secret sharing. Since the late 2000s, and certainly since 2010 and on, the domain of general purpose protocols has moved to deal with efficiency improvements of the protocols with practical applications in mind. Increasingly efficient protocols for MPC have been proposed, and MPC can be now considered as a practical solution to various real life problems (especially ones that only require linear sharing of the secrets and mainly local operations on the shares with not much interactions among the parties), such as distributed voting, private bidding and auctions, sharing of signature or decryption functions and private information retrieval. The first large scale and practical application of multi party computation was the execution of an electronic double auction in the Danish Sugar Beet Auction, which took place in January 2008. Obviously, both theoretical notions and investigations, and applied constructions are needed (e. g., conditions for moving MPC into part of day by day business was advocated and presented
in). In 2020, a number of companies working with secure multiparty computation founded the MPC alliance with the goal of "accelerate awareness, acceptance, and adoption of MPC technology."

Хаттамалар

Екі тарапты есептеу (2PC) және көп тарапты есептеу (MPC) үшін ұсынылған протоколдардың арасында маңызды айырмашылықтар бар. Сонымен қатар, маңызды арнайы мақсаттағы протоколдар үшін (дауыс беру, аукциондар, төлемдер және т.б.) әдеттегі протоколдардан өзгешеленетін арнайы протокол жасалуы тиіс.

Екі тараптық есептеу

Екі тарапты параметрлер ерекше қызығушылық тудырады, тек қолданыс тұрғысынан ғана емес, сонымен қатар екі тарапты параметрлерде көп тарапты жағдайда қолданылмайтын арнайы техникаларды қолдануға болады. Шындығында, қауіпсіз көп тарапты есептеу (жақсырақ айтқанда, қауіпсіз функцияны бағалаудың шектеулі жағдайы, онда тек бір функция бағаланады) алғаш рет екі тарапты параметрлерде ұсынылған. Алғашқы жұмыс көбінесе Яоның екі мақаласының бірі деп есептеледі; алайда, мақалаларда қазір Яоның бүлінген схема протоколы деп белгілі нәрсе жоқ. Яоның негізгі протоколы жартылай адал қарсыластарға қарсы қауіпсіз және раундтар саны бойынша өте тиімді, ол тұрақты және бағаланатын функцияға тәуелсіз. Функция бинарлық ұзындығы белгіленген кірістермен Бульдік тізбек ретінде қарастырылады. Бульдік тізбек - үш түрлі сымдармен байланыстырылған қақпалар жиынтығы: тізбек кіріс сымдары, тізбек шығыс сымдары және аралық сымдар. Әр қақпа екі кіріс сымын қабылдайды және келесі деңгейде бірнеше қақпаларға берілуі мүмкін бір шығыс сымына ие. Тізбектің қарапайым бағалауы әр қақпаны кезекпен бағалау арқылы жүзеге асырылады; қақпалар топологиялық ретпен орналасқан деп есептеледі. Қақпа шындық кестесі түрінде ұсынылады, сондықтан кіріс сымдарынан келетін әр мүмкін бит жұбы үшін кесте бірегей шығыс битін тағайындайды; бұл қақпаның шығыс сымының мәні. Бағалау нәтижелері тізбек шығыс сымдарында алынған биттер болып табылады. Яо тізбекті қалай бүлінгенді (оның құрылымын жасыруды) түсіндірді, сонда екі тарап, жіберуші және қабылдаушы, тізбектің шығысын және басқа ештеңені біле алмайды. Жоғары деңгейде, жіберуші бүлінген тізбекті дайындап, оны қабылдаушыға жібереді, ол оны білмейтіндей бағалайды, өзінің және жіберушінің шығысына сәйкес келетін кодтамаларды үйренеді. Содан кейін ол тек жіберушінің кодтамасын қайта жібереді, бұл жіберушіге шығыстың өзінің бөлігін есептеуге мүмкіндік береді. Жіберуші қабылдаушының шығыс кодтамасынан биттерге сәйкестікті қабылдаушыға жібереді, бұл қабылдаушыға олардың шығысын алуға мүмкіндік береді. Егжей-тегжейлі айтқанда, бүлінген тізбек келесідей есептеледі. Негізгі компонент - екі кілтті симметриялық шифрлеу схемасы. Тізбектің қақпасын ескере отырып, оның кіретін сымдарының әрбір мүмкін мәні (0 немесе 1) кездейсоқ санмен (белгімен) кодталады. Қақпаны бағалаудан алынған мәндер, төрт мүмкін кіріс биттерінің әрқайсысы үшін, сондай-ақ кездейсоқ белгілермен ауыстырылады. Қақпаның бүлінген шындық кестесі кіріс белгілерін кілттер ретінде пайдалана отырып, әрбір шығыс белгісінің шифрлануынан тұрады. Бұл төрт шифрлаудың шындық кестедегі орны кездейсоқ, сондықтан қақпа туралы ешқандай ақпарат ағып кетпейді. Әрбір бүлінген қақпаны дұрыс бағалау үшін шифрлеу схемасының келесі екі қасиеті болуы керек. Біріншіден, кез келген екі бөлек кілт астындағы шифрлеу функциясының ауқымдары (көптеген жағдайларда) бөлек. Екінші қасиет - берілген шифрланған мәтіннің берілген кілтпен шифрланғанын тиімді тексеруге болады. Осы екі қасиетпен қабылдаушы барлық тізбек кіріс сымдарының белгілерін алғаннан кейін, әр қақпаны оның белгілік кілттерімен шифрланған төрт шифр мәтінінің қайсысы екенін анықтап, содан кейін шығыс сымының белгісін алу үшін шифрлау арқылы бағалай алады. Бұл білмейтіндей жасалады, өйткені қабылдаушы бағалау кезінде биттердің кодтамасын ғана біледі. Жіберушінің (яғни тізбек жасаушының) кіріс биттері бағалаушыға тек кодтама ретінде жіберілуі мүмкін, ал қабылдаушының (яғни тізбек бағалаушының) кіріс биттеріне сәйкес келетін кодтамалар 1-ден 2-ге дейін білмейтін беру (OT) протоколы арқылы алынады. 1-ден 2-ге дейін OT протоколы C1 және C2 мәндеріне ие жіберушіге алушы сұраған мәнді (b {1,2} мәні) жіберуге мүмкіндік береді, жіберуші қандай мән берілгенін білмейді, ал алушы тек сұралған мәнді біледі. Егер қаскөй қарсыластарды қарастырылса, екі тараптың да дұрыс мінез-құлқына кепілдік беру үшін қосымша механизмдер қажет. Құрылымы бойынша, OT протоколы зиянды қарсыластарға қарсы қорғалған болса, жіберушіге қауіпсіздікті көрсету оңай, өйткені қабылдаушы тек нұсқаулардан ауытқыса, тізбек шығыс сымдарына жетуге мүмкін емес бүлінген тізбекті бағалауы керек. Жіберуші жағында жағдай мүлдем басқаша. Мысалы, ол қателікпен бүлінген тізбекті жіберуі мүмкін, ол қабылдаушының кіріс деректерін ашатын функцияны есептейді. Бұл жеке өмірдің құпиялылығы енді сақталмайды дегенді білдіреді, бірақ тізбек бүлінгендіктен қабылдаушы мұны анықтай алмайды. Алайда, бұл протоколды зиянды қарсыластарға қарсы қауіпсіз ету үшін нөлдік білімді дәлелдерді тиімді қолдануға болады, бұл жартылай адал протоколмен салыстырғанда шамалы қосымша шығынға әкеледі.

The two party setting is particularly interesting, not only from an applications perspective but also because special techniques can be applied in the two party setting which do not apply in the multi party case. Indeed, secure multi party computation (in fact the restricted case of secure function evaluation, where only a single function is evaluated) was first presented in the two party setting. The original work is often cited as being from one of the two papers of Yao; although the papers do not actually contain what is now known as Yao's garbled circuit protocol. Yao's basic protocol is secure against semi honest adversaries and is extremely efficient in terms of number of rounds, which is constant, and independent of the target function being evaluated. The function is viewed as a Boolean circuit, with inputs in binary of fixed length. A Boolean circuit is a collection of gates connected with three different types of wires: circuit input wires, circuit output wires and intermediate wires. Each gate receives two input wires and it has a single output wire which might be fan out (i. e. be passed to multiple gates at the next level). Plain evaluation of the circuit is done by evaluating each gate in turn; assuming the gates have been topologically ordered. The gate is represented as a truth table such that for each possible pair of bits (those coming from the input wires' gate) the table assigns a unique output bit; which is the value of the output wire of the gate. The results of the evaluation are the bits obtained in the circuit output wires. Yao explained how to garble a circuit (hide its structure) so that two parties, sender and receiver, can learn the output of the circuit and nothing else. At a high level, the sender prepares the garbled circuit and sends it to the receiver, who obliviously evaluates the circuit, learning the encodings corresponding to both his and the sender's output. He then just sends back the sender's encodings, allowing the sender to compute his part of the output. The sender sends the mapping from the receivers output encodings to bits to the receiver, allowing the receiver to obtain their output. In more detail, the garbled circuit is computed as follows. The main ingredient is a double keyed symmetric encryption scheme. Given a gate of the circuit, each possible value of its input wires (either 0 or 1) is encoded with a random number (label). The values resulting from the evaluation of the gate at each of the four possible pair of input bits are also replaced with random labels. The garbled truth table of the gate consists of encryptions of each output label using its inputs labels as keys. The position of these four encryptions in the truth table is randomized so no information on the gate is leaked. To correctly evaluate each garbled gate the encryption scheme has the following two properties. Firstly, the ranges of the encryption function under any two distinct keys are disjoint (with overwhelming probability). The second property says that it can be checked efficiently whether a given ciphertext has been encrypted under a given key. With these two properties the receiver, after obtaining the labels for all circuit input wires, can evaluate each gate by first finding out which of the four ciphertexts has been encrypted with his label keys, and then decrypting to obtain the label of the output wire. This is done obliviously as all the receiver learns during the evaluation are encodings of the bits. The sender's (i. e. circuit creators) input bits can be just sent as encodings to the evaluator; whereas the receiver's (i. e. circuit evaluators) encodings corresponding to his input bits are obtained via a 1 out of 2 oblivious transfer (OT) protocol. A 1 out of 2 OT protocol enables the sender possessing of two values C1 and C2 to send the one requested by the receiver (b a value in {1,2}) in such a way that the sender does not know what value has been transferred, and the receiver only learns the queried value. If one is considering malicious adversaries, further mechanisms to ensure correct behavior of both parties need to be provided. By construction it is easy to show security for the sender if the OT protocol is already secure against malicious adversary, as all the receiver can do is to evaluate a garbled circuit that would fail to reach the circuit output wires if he deviated from the instructions. The situation is very different on the sender's side. For example, he may send an incorrect garbled circuit that computes a function revealing the receiver's input. This would mean that privacy no longer holds, but since the circuit is garbled the receiver would not be able to detect this. However, it is possible to efficiently apply Zero Knowledge proofs to make this protocol secure against malicious adversaries with a small overhead comparing to the semi honest protocol. which defines how to compute addition and multiplication on secret shares, is often used to compute functions with Shamir secret shares. Additive secret sharing schemes can tolerate the adversary controlling all but one party, that is , while maintaining security against a passive and active adversary with unbounded computational power. Some protocols require a setup phase, which may only be secure against a computationally bounded adversary. A number of systems have implemented various forms of MPC with secret sharing schemes. The most popular is SPDZ, which implements MPC with additive secret shares and is secure against active adversaries.

Басқа хаттамалар

2014 жылы, нәтиже алғанда тоқтатылатын қарсылас тарапқа өзара алдын ала белгіленген ақшалай айып төлеуге мәжбүр болатын, "қауіпсіз есептеудегі әділдік моделі" Биткойн желісі немесе әділ лотерея үшін сипатталды және Ethereum-да сәтті іске асырылды.

Қолда қолданылатын МКК жүйелері

Соңғы жылдары 2PC және MPC жүйелерінде көптеген үлкен жетістіктерге қол жеткізілді.

Яо-базалық протоколдар

Яо негізделген протоколдармен жұмыс істеу кезіндегі басты мәселелердің бірі – қауіпсіз бағалануға тиіс функцияның (кәдімгі бағдарлама болуы мүмкін) схема түрінде ұсынылуы керек, көбінесе ол XOR және AND шлюздерінен тұрады. Көптеген нақты бағдарламалар циклдар мен күрделі дерек құрылымдарын қамтитындықтан, бұл оңай міндет емес. Fairplay жүйесі осы мәселені шешуге арналған алғашқы құрал болды. Fairplay екі негізгі компоненттен тұрады. Біріншісі – компилятор, ол пайдаланушыларға қарапайым жоғары деңгейдегі тілде бағдарлама жазуға және осы бағдарламаларды Бульдік схема түрінде шығаруға мүмкіндік береді. Екінші компонент схеманы бұрмалап, бұрмаланған схеманы қауіпсіз бағалау үшін протоколды іске қоса алады. Яо протоколына негізделген екі тарапты есептеуден басқа, Fairplay көп тарапты протоколдарды да іске асыра алады. Бұл BMR протоколын қолдану арқылы жүзеге асырылады. Қазірге дейін белсенді қауіпсіздікті қамтамасыз етуде ең нәтижелі тәсіл – garbling техникасы мен «кесіп таңдау» парадигмасының үйлесімі болып көрінеді. Бұл комбинация тиімді құрылымдарды жасауға мүмкіндік береді. Адал емес мінез-құлыққа байланысты жоғарыда аталған проблемаларды болдырмау үшін, конструктор бағалаушыға бір схеманың көптеген бұрмалауларын жібереді. Содан кейін олардың шамамен жартысы (нақты протоколға байланысты) сәйкестікті тексеру үшін ашылады, және егер ашылмаған бөліктерінің көпшілігі жоғары ықтималдылықпен дұрыс болса, нәтиже – барлық бағалаулардың көпшілік дауысы. Осында көпшілік шығыны қажет. Егер шығыстарда келіспеушілік болса, алушы жіберушінің алдап жатқанын біледі, бірақ ол шағымдана алмайды, өйткені бұл оның кірісі туралы ақпаратты ашады. Активті қауіпсіздіктің бұл тәсілін Линдэлл мен Пинкас бастады. Пинкас және тағы басқалар бұл техниканы 2009 жылы іске асырды, соның арқасында Яо негізделген активті қауіпсіз іске асырудың тиімділігі одан әрі жақсарды, тек 40 схема және алдау ықтималдығын алу үшін азайтылған міндеттемелер саны қажет болды. Жақсартулар жаңа әдістердің нәтижесінде болды. Соңғы уақытта көп ядролы CPU-да жұмыс істеуге арналған, бұрмаланған схемаларға негізделген жоғары параллельді іске асыруға назар аударылды. Кройтер және тағы басқалар қуатты кластерлік компьютердің 512 ядросында жұмыс істейтін іске асыруды сипаттады. Осы ресурстарды пайдаланып, олар 4095 биттік редакциялық қашықтық функциясын бағалай алды, оның схемасында шамамен 6 миллиард шлюз бар. Бұл үшін олар Fairplay-ден гөрі жақсырақ схема компиляторын және құбыржол сияқты бірнеше жаңа оңтайландыруларды жасады, онда бұрмаланған схеманың желіде берілуі схеманың қалған бөлігі әлі құрылып жатқанда басталады. AES-ті есептеу уақыты 512 түйін кластерлік машинаны пайдалану арқылы бір блокқа 1,4 секундқа дейін, ал бір түйінді пайдалану арқылы 115 секундқа дейін қысқартылды. Шелат пен Шен бұл нәтижені тауарлық жабдықты пайдалана отырып, бір блокқа 0,52 секундқа дейін жақсартты. Сол мақалада бір секундта 21 блок өңделуі туралы хабарланды, бірақ бір блок өңдеуге 48 секунд кетті. Осы арада зерттеушілердің басқа тобы тұтынушы GPU-ларын пайдаланып, ұқсас параллельдік деңгейге жетуді зерттеді. Олар өздерінің GPU-ға арналған протоколын жасау үшін беймәлім беру кеңейтулерін және басқа да жаңа әдістерді қолданды. Бұл тәсіл кластерлік есептеуді іске асырумен салыстырылатын тиімділікке қол жеткізеді, ұқсас ядролар санын пайдаланады. Алайда авторлар тек AES схемасының іске асырылуы туралы хабарлайды, онда шамамен 50 000 шлюз бар. Екінші жағынан, қажетті жабдық мұнда әлдеқайда қолжетімді, өйткені ұқсас құрылғылар көптеген адамдардың үстелдік компьютерлерінде немесе ойын консольдарында болуы мүмкін. Авторлар стандартты жұмыс үстелінде стандартты GPU-мен AES блогына 2,7 секунд уақыт алады. Егер олар қауіпсіздікті жасырын қауіпсіздікке ұқсас деңгейге төмендетсе, олар AES блогы үшін 0,30 секунд жұмыс уақытын алады. Пассивті қауіпсіздік жағдайында 250 миллион шлюзді схемаларды өңдеу туралы хабарлар бар, секундына 75 миллион шлюз өңделеді.

One of the main issues when working with Yao based protocols is that the function to be securely evaluated (which could be an arbitrary program) must be represented as a circuit, usually consisting of XOR and AND gates. Since most real world programs contain loops and complex data structures, this is a highly non trivial task. The Fairplay system was the first tool designed to tackle this problem. Fairplay comprises two main components. The first of these is a compiler enabling users to write programs in a simple high level language, and output these programs in a Boolean circuit representation. The second component can then garble the circuit and execute a protocol to securely evaluate the garbled circuit. As well as two party computation based on Yao's protocol, Fairplay can also carry out multi party protocols. This is done using the BMR protocol,

The approach that so far seems to be the most fruitful in obtaining active security comes from a combination of the garbling technique and the "cut and choose" paradigm. This combination seems to render more efficient constructions. To avoid the aforementioned problems with respect to dishonest behaviour, many garblings of the same circuit are sent from the constructor to the evaluator. Then around half of them (depending on the specific protocol) are opened to check consistency, and if so a vast majority of the unopened ones are correct with high probability. The output is the majority vote of all the evaluations. Here the majority output is needed. If there is disagreement on the outputs the receiver knows the sender is cheating, but he cannot complain as otherwise this would leak information on his input. This approach for active security was initiated by Lindell and Pinkas. This technique was implemented by Pinkas et al. in 2009, the efficiency of actively secure Yao based implementations was improved even further, requiring only 40 circuits, and a much smaller number of commitments, to obtain cheating probability. The improvements come from new methodologies for performing cut and choose on the transmitted circuits. More recently, there has been a focus on highly parallel implementations based on garbled circuits, designed to be run on CPUs with many cores. Kreuter, et al. describe an implementation running on 512 cores of a powerful cluster computer. Using these resources they could evaluate the 4095 bit edit distance function, whose circuit comprises almost 6 billion gates. To accomplish this they developed a custom, better optimized circuit compiler than Fairplay and several new optimizations such as pipelining, whereby transmission of the garbled circuit across the network begins while the rest of the circuit is still being generated. The time to compute AES was reduced to 1.4 seconds per block in the active case, using a 512 node cluster machine, and 115 seconds using one node. Shelat and Shen improve this, using commodity hardware, to 0.52 seconds per block. The same paper reports on a throughput of 21 blocks per second, but with a latency of 48 seconds per block. Meanwhile, another group of researchers has investigated using consumer grade GPUs to achieve similar levels of parallelism. They utilize oblivious transfer extensions and some other novel techniques to design their GPU specific protocol. This approach seems to achieve comparable efficiency to the cluster computing implementation, using a similar number of cores. However, the authors only report on an implementation of the AES circuit, which has around 50,000 gates. On the other hand, the hardware required here is far more accessible, as similar devices may already be found in many people's desktop computers or games consoles. The authors obtain a timing of 2.7 seconds per AES block on a standard desktop, with a standard GPU. If they allow security to decrease to something akin to covert security, they obtain a run time of 0.30 seconds per AES block. In the passive security case there are reports of processing of circuits with 250 million gates, and at a rate of 75 million gates per second.

Қауіпсіз көп тарапты есептеу деректерін талдауды іске асыру

Қауіпсіз көп тарапты есептеудің басты қолданыстарының бірі – бірнеше тараптың иелігіндегі деректерді талдауға немесе деректерді сақтаушыға талдаудың қандай түрде жүргізіліп жатқанын білдірмей, үшінші тараптардың деректерді жасырын талдауын жүзеге асыруға мүмкіндік беру болып табылады.

Жабдықтық іске асыру

Атауы Дамытушы Жыл Кірген жылы Ескертпелер Қазіргі күні қолданылуда ма? Trident MPCi4p informatics ltd. 2019 Криптографиялық кілттерді басқару үшін Secure Multi-party Computation (SMPC) қолдануға арналған, нарықтағы алғашқы Common Criteria EAL4+ сертификатталған физикалық аппараттық қауіпсіздік модулі. 2024 жылға дейін