Search

Käesolevas töös esitatakse meetodid teeotsingu läbiviimiseks kolmemõõtmelises ruumis. Esimeses peatükis defineeritakse lähteandmete vorming ning esitatakse kuupide kaheksandpuul põhinev analüüsi meetod ruumi mudeli loomiseks. Teine peatükk kirjeldab kahte erinevat võimalust otsingugraafi koostamiseks ning loetleb omadusi, mille abil erinevaid graafi koostamise meetodeid võrrelda. Kolmandas peatükis defineeritakse läbitavus-, kaalu- ja pöörangufunktsiooni abil mobiilse agendi profiil. Need kolm funktsiooni kirjeldavad agendi võimet ruumi läbida ning määravad selle optimaalsuse. Esitatakse reeglid otsingugraafi lihtsustamiseks konkreetse agendi profiili põhjal., This work explores additional methods for solving the unified path finding problem. Our previous work concentrated on finding the optimal path on a terrain presented as a heightmap. We extend the searchable area to three-dimensional space populated by convex geometrical objects.

Töö kombineerib erinevaid ideid, et saavutada aktiivses mudelis turvalist kahe osapoolega ühisarvutust. Töö käigus defineerime Sharemindi raamistikku kaks uut turvaala. Kasutame aditiivset ühissalastust, sõnumiautentimisskeeme, aditiivselt homomorfset krüptosüsteemi ning nullteadmustõestusi. Protokollistikud jagame kahte osasse, vastavalt ettearvutamise ja töö faas. Ettearvutamise ajal valmistatakse ette juhuslikke väärtusi, mis võimaldavad töö faasis arvutusi kiirendada. Eelkõige keskendume korrutamise jaoks vajalike Beaveri kolmikute genereerimisele., This thesis combines currently popular ideas in actively secure multi-party computation to define two actively secure two-party protocol sets for Sharemind secure multi-party computation framework. This includes additive secret sharing, dividing work as online and precomputation phase, using Beaver triples for multiplication and using message authentication codes for integrity checks. Our protocols use additively homomorphic Paillier cryptosystem, especially in the precomputation phase. The thesis includes two different setups for secure two-party computation which are also implemented and compared to each other. In addition, we propose new ideas to use additively homomorphic cryptosystem to generate Beaver triples for any chosen modulus. The important aspects of Beaver triple generation are maximising the amount of useful bits we get from one generation and assuring that these triples are correct.

Vaatleme stsenaariumi, kus mitu organisatsiooni sooviks oma individuaalsetest andmebaasidest ehitada ühe suure andmebaasi. Andmebaasi ehitamise eesmärgiks on ühiselt teostada arvutusi, mis oleksid kasulikud kõikidele osapooltele. Ühest küljest võivad kõik osapooled oma andmed avalikustada ning selle põhjal vajalikke arvutusi teha. Teisest küljest, ei ole kõiki andmeid võimalik avalikustada ning suur osa kasulikke arvutusi tehakse tõenäoliselt just privaatsete andmete pealt. Andmete avalikustamist võivad takistada nii organisatsiooni sisesed reeglid, kui ka seadused. Antud probleemile on olemas krüptograafiline lahendus - turvaline ühisarvutus. Turvalise ühisarvutuse abil saavad osapooled teha arvutusi nii, et iga osapool saab teada ainult arvutuse tulemuse ja ei saa teada midagi uut lähteandmete kohta. Käesolevas töös uurime ühe konkreetse turvalise ühisarvutuste raamistiku, Sharemindi, rakenduste jõudlust. Praegune Sharemindi rakendusserver töötab kolme masina peal, mis omavahel suheldes teostavad arvutusi. Antud raamistikus kasutatava turvalise ühisarvutuse jõudlus sõltub peamiselt edastatud andmete mahust ning seega võrgu jõudlusest, mille peal arvutusi läbi viiakse. Me ehitasime lineaarse regressioonimudeli, mille eesmärgiks on ennustada protokollide tööaega sõltuvalt võrgu parameetritest. Baasmudeli loomisel fikseerisime võrgu parameetrid olemasolevate tööriistadega ning hindasime mudeli parameetrite väärtused. Eksperimendid mudeli loomiseks viisime läbi eriotstarbelisel Sharemindi arvutusklastril. Teades mudeli parameetrite väärtuseid üritasime võrgu parameetrite põhjal ennustada mudeli tööaega. Klasti süsteemi peal valideerisime mudelit, ennustades algoritmide tööaega. Uurisime Apriori andmekaeve algoritmi, mis kasub Sharemindi turvalise ühisarvutuse protokolle. Ennustuse tulemused olid lähedased tegelikule protokollidele kulutatud ajale. Mudeli valideerimiseks paigaldasime Sharemindi raamistiku mitmelt pilveteenuse pakkujalt renditud taristule. Pilveteenused kiirendavad mitmesuguste rakenduste, eelkõige veebiteenuste arendusprotsessi, minimaliseerides esmast investeeringut, sest alustavad firmad ei pea oma riistvara hankima. Riistvara soetamise ja haldamise kulud vahetatakse pilveteenuse vastu. Pilve keskkonnas ei õnnestunud meil täpseid ennustusi protokollide tööaja kohta teha. Küll aga õnnestus teha umbkaudseid hinnanguid mudeli parameetrite kohta ning nende põhjal prtokollide tööaega hinnata. Kuigi hinnangud ei olnud väga täpsed, saime järeldada, et meie mudel ei ole vale, aga me ei suuda mudeli sisendparameetreid, võrgu latentsust ja ribalaiust, täpselt mõõta ning seetõttu on ka meie ennustused ebatäpsed. Selles töös uurisime ka turvalisel ühissalastusel põhinevate pilverakenduste majanduslikku otstarbekust. Jälgisime kahte aspekti: kas turvaline ühisarvutus pilves on piisavalt kiire ning kas kulud on mõistlikud. Leidsime, et arvutuste jõudlus on piisav mitmete potentsiaalsete rakenduste jaoks. Turvalise küsimustiku näitestsenaariumi põhjal järeldasime, et turvalise ühisarvutuse kulud pilverakendustes on samuti mõistlikud. Pilvekeskonnas on kaks peamist kuluallikat: serveri ülalhoidmiskulud ning võrguliiluse kulud. Leidsime, et suure hulga rakenduste jaoks on serveri ülalhoidmine kulukam kui andmeedastus. Selle töö tulemusena leidsime, et turvaline ühissalastus on mõistlik lahendus selliste rakenduste puhul, kus andmete privaatsuse tagamine on kriitilise tähtsusega. Tulemused näitavad, et Sharemindil põhinevad rakendused on praktilised ka siis, kui nad on juurutatud üle maailma laiali asuvates serverites. Lisaks näitasid meie katsed, et Sharemindi protkollide jõudlust saaks tõsta parandades vaba oleva võrgu ribalaiuse kasutamist raamistiku protokollide poolt., Imagine a scenario where multiple companies hold valuable information and they want to combine their data for analysis that would benefit them all. In an honest world, the companies could do just that - combine their data. However, in the real world, none of them can afford to make their data public because it could compromise their competitive advantage. One can easily find many similar real-world scenarios where there are privacy issues concerned with the data. Data privacy is also a very prominent issue when outsourcing the computing resources, for example, to cloud services. A cryptographic solution to this problem would be to use secure multiparty computation (SMC). SMC is a useful tool for computing the result of an operation with the inputs of multiple parties, without revealing what the inputs were. As a result, we can perform computations on the data without disclosing it. There exist two main approaches how to perform SMC. First, circuit evaluation, which is based on computations on arithmetic or logic circuits and is CPU intensive (CPU-bound). Second, general multiparty computation, which relies more on the communication between the parties (network-bound). Currently, the more efficient systems in this field use the latter approach. The theoretical complexity of these systems is well known. However, for real-life deployments the theoretical results alone are not enough. In this work, we would like to study the practical performance of the network-bound general multiparty computation. Based on the published results, the Sharemind SMC framework has shown the best performance and widest functionality among similar systems. One goal of this work was to create a mathematical model for predicting computational performance of SMC depending on the network parameters. The model was constructed based on a set of experiments conducted on th Sharemind framework. To validate our model, we set up a set of servers in the cloud environment. In this setting we measured the parameters of the network connections between the machines. The predictions were compared to the actual computation results. We were unable to accurately predict the running time of the protocols in the cloud. However, we concluded that this result was probably due to the inability to accurately estimate the effective network parameters to compute the model coefficients. The model validation in the experiment cluster environment showed that the models can be used to accurately predict the running time of the secure operations inside more complex algorithms. In the last part of the work, we utilized the general model to assess the feasibility of SMC in the cloud environment. With the model, we computed time estimations for executing certain operations in a sample scenario. The cost estimation showed that for a secure survey scenario, the cost of the secure computations is low compared to the cost of keeping the server running during the data gathering phase for the survey. The cost of the performed operations only starts to play a role with large data sets and computation heavy algorithms. The results of this work indicate that it is indeed feasible to do secure multiparty computation in the cloud environment for a whole range of real-world scenarios. This mainly benefits the potential cloud service scenarios where privacy of the stored data is one of the primary concerns. In this work we also found some indications of possible improvements to the Sharemind framework. We noticed that even though the protocols have a lot of avai\-lable bandwidth, they are not using it. For high throughput connections, the performance of the protocols may be significantly increased if the bandwidth utilization rate can be improved. As a future work, we could try other approaches to construct the models or, alternatively, build a specialized tool to measure the bandwidth parameter for the models.

Klassikaliste klient-server arhitektuuril põhinevate virtuaalmaailmade üheks nõrgaks kohaks on serverid, milledesse virtuaalmaailma kliendid ühenduvad. Kui tegemist on suure kasutajaskonna ja suure kasutatavusega virtuaalmaailmaga, siis kipuvad serverite halduskulud kasvama väga kiiresti ning nende kesise haldamise korral võivad kasutajad kogeda ebameeldivusi antud teenuse tõrkumise tõttu. Lisaks sellele on ka kontroll antud keskkonna üle serverite haldajatel, mistõttu võivad viimased ette teatamata oma teenused sulgeda. Klient-server arhitektuuril põhinevad populaarsetest teenustest nii World of Warcraft kui ka Second Life. Peer-to-peer (P2P) arhitektuur erineb klient-server arhitektuurist selle poolest, et iga osaleja P2P-l põhinevas võrgus võib käituda nii kliendi kui ka serverina – puudub keskne ühenduspunkt. Peer-to-peer tehnoloogial põhinevad näiteks populaarne failivahetuskesk-kond BitTorrent1 ja suhtluskeskkond Skype2. Tuhandete kasutajatega ja rikkaliku sisuga virtuaalmaailmad võivad vajada võrdlemisi palju ressursse, sh. arvutusvõimsust, internetiühenduse ribalaiust ja andmete salvestus-mahtu. Klient-server mudeli puhul on pudelikaelaks serverid, milledesse kliendid ühendu-vad – serverid peavad olema piisavalt võimsad ning neid peab olema piisavalt palju, et kliente samaaegselt hallata ja virtuaalmaailma simulatsiooni töös hoida. Peer-to-peer mudel kõrvaldab selle pudelikaela, võimaldades ühel kliendil jagada ülesandeid laiali teistele, vähem koormatud klientidele. Näiteks, kui kasutajad kirjutavad skripte, mis vajavad arvestatava hulga arvutusvõimsust (animeerides mingit objekti või lahendades mõnda arvutusülesannet), siis klient-server mudeli puhul on serveri ülesandeks klientide skripte jooksutada ning suur klientide ja skriptide arv võib serveri üle koormata. Seevastu P2P arhitektuuri puhul on võimalik rakendada koormusjaotusalgoritme ning leida kliendid, kellele võiks delegeerida mõnede skriptide jooksutamise selle alusel, kui palju ressursse ja arvutusvõimsust neil parasjagu üle on. Selline peer-to-peer tehnoloogial põhinev koormuse jaotamine võimaldab pakkuda kee-rulisemat ja rikkalikumat virtuaalmaailma kogemust klientidele. Koormuse jaotamine võimaldab vähendada teenusepakkuja kulusid interneti teenusele ja energiale. Siiski võib P2P võrgu osaliste koondkulu olla suuremgi kui tavalise klient-server võrgu puhul, kuna kõik osalised võivad olla võrdselt hõivatud, andes oma panuse ressursside kasutamisse. Samal ajal lisab P2P kasutamine ka turvariske, võrreldes klient-server mudeliga, milles on sisuliselt ainult üks usaldust vajav komponent – server. Käesoleva töö eesmärgiks on võrrelda klient-server mudeli ja peer-to-peer mudeli efektiivsust ja P2P arhitektuuri rakendatavust virtuaalmaailmades. Selleks viisime läbi katsed teadusuuringute tarbeks ehitatud virtuaalmaailmaga VirtualLife., The purpose of the given thesis is to investigate the usability and effectiveness of peer-to-peer architecture in contrast to traditional client-server architeture when simulating virtual worlds. In addition, we study how peer-to-peer helps to reduce the cost of ownership for the service provider as opposed to the traditional client-server architecture. A number of experiments were conducted with scientific research project VirtualLife using both peer-to-peer and client-server architectures. The experiments were conducted on a special-purpose cluster computer consisting of multiple virtual nodes. Some experiments were also repeated on a non virtualized environment consisting of physical computers, since it was found that the virtualized environment might have had a negative effect on the performance of the simulation. Based on the experiment results we conclude that using peer-to-peer architecture when simulating virtual worlds helps to provide a better user experience while reducing the cost of ownership for the service provider. We also confirm that the usage of peer-to-peer architecture might increase the bandwidth load and resource usage for the client participating in the virtual world.

Vaatleme olukorda, kus grupp samal alal tegutsevaid ettevõtteid soovib analüüsida oma tegevusvaldkonda. Kogu valdkonna analüüsiks tuleks vastavatelt ettevõtetelt nende tegevusnäitajad ühte kohta kokku koguda, et neid saaks korralikult analüüsida. Samas ei ole ettevõtted aga oma info jagamisest huvitatud, kuna see on üks osa nende ärisaladusest. Veelgi enam - kui see info peaks sisaldama ka näiteks ettevõtte klientide isiklikke andmeid, siis on sellise info jagamine teistele osapooltele seadusandlusega keelatud. Käesolev töö keskendub kirjeldatud probleemi ühele konkreetsele näitele. Infotehnoloogia ja Telekommunikatsiooni Liit (ITL) on mittetulundusühing, mis ühendab enam kui 60 info- ja kommunikatsioonitehnoloogia (IKT) alal tegutsevat ettevõtet Eestis. Kuna IKT on kiiresti arenev majandussektor, on need ettevõtted huvitatud ajakohaste majandusnäitajate võrdlemisest, et langetada paremaid strateegilisi otsuseid. Et ITL saaks neid andmeid turvaliselt koguda ja analüüsida, pakkusime välja lahenduse, kus kasutame Sharemindi raamistikku. Sharemind on hajus andmebaasi- ja rakendusserver, mis hoiab andmeid ühissalastatud kujul ning kasutab turvalise ühisarvutuse protokolle tagamaks, et üksikud algväärtused andmeanalüüsi käigus ei lekiks. Ühissalastatud andmete hoidmiseks kasutab Sharemind kolme sõltumatut osapoolt ehk andmekaevurit. Antud töö käigus arendsime välja ka JavaScripti teegi, mis võimaldab kasutajal andmeid oma veebilehitsejast sisestada. Sel juhul hoolitseb see teek andmete ühissalastuse eest ning jagab tekkinud osakud turvaliselt andmekaevurite vahel. Kirjeldatud lahendust kasutas ITL selle aasta alguses, et koguda oma liikmete majandusnäitajaid 2010. aasta kohta. Käesolevas töös on kirjeldatud nii kasutatud lahenduse tehnilised aspektid ja andmeanalüüs kui ka projekti ajaline käik. ITL-i juhatus on esimese andmekogumisperioodi tulemustega rahul ning soovib antud rakenduse kasutamist kindlasti jätkata., In this thesis we describe a situation where a consortium of companies working in the same field would like to jointly analyse the market in general. However, they cannot share their data with each other either because they are reluctant or prohibited to do so. We propose a solution where the consortium members could analyse the whole data set without breaching the privacy requirements. This is accomplished by using the Sharemind secure multiparty computation framework. As part of this thesis we have developed a JavaScript library that allows users to securely submit their data to the joint database using an online data entry application. Our work relies on a case-study of developing a prototype application for one of such consortiums, namely the Association of Information Technology and Telecommunications (ITL).

https://www.ester.ee/record=b5369600*est

https://www.ester.ee/record=b5415439*est

Sharemind on raamistik, mis võimaldab teha privaatsust säilitavaid arvutusi. Sharemind koosneb kolmest andmekaevandaja rakendusest ja juhtimisteegist. Andmekaevandajad, moodustades Sharemindi virtuaalmasina, teevad olemasolevate andmete peal privaatseid arvutusi. Juhtimisteegi abil saavad teised rakendused andmekaevandajate tööd kontrollida ning nende andmebaasidesse uusi andmeid sisestada. Sharemindi raamistikule on loodud kaks programmeerimiskeelt: Sharemindi assemblerkeel ja SecreC keel. Sharemindi assemblerkeel on madala taseme keel, mida käivitatakse otse Sharemindi virtuaalmasinas. Kuigi ta lubab teha privaatsust säilitavaid arvutusi teostavaid rakendusi, on rakenduste tegmise protsess keeruline, sest madala taseme keeles programmeerimine on aeganõudev ning vigadele avatud. Selleks, et arendajad ei peaks assemblerkeeles programmeerima, loodi SecreC keel. SecreC on C-keele laadne programmeerimiskeel, mis võimaldab luua andmekaevandusalgoritme Sharemindi raamistiku rakendustele. SecreC kompileeritakse Sharemindi assemblerkeeleks, mis seejärel käivitatakse virtuaalmasinas. Klientrakendused kasutavad juhtimisteeki andmekaevandaja rakendustega suhtlemiseks. Praegune Sharemindi klientrakenduste loomise protsess koosneb kasutajaliidese loomisest ja andmekaeve algoritmide realiseerimisest. Kasutajaliideses peab olema võimalus andmeid lisada, esitada päringuid olemasolevate andmete peal arvutuste tegemiseks ja arvutustulemusi kuvada. Järgnevalt tuleb luua andmekaevandusalgoritmid, mis realiseeritakse SecreC keeles. Loodud algoritme tuleb testida ning kontrollida, et lekkivaid andmeid ei oleks. Kuigi Sharemindi raamistik garanteerib andmete privaatsuse instruktsiooni tasemel, võivad lekked siiski esineda algoritmi tasemel. Käesoleva töö eesmärgiks on lihtsustada rakendustele algormitmide realiseerimise protsessi SecreC programmeerimiskeeles. Meie panususena on loodud integreeritud arenduskeskkond, mis toetab programmeerijat, pakkudes talle mitmeid tööriistu, mis peaksid lihtsustama programmeerimist nii SecreC keeles kui ka Sharemindi assemblerkeeles. Samuti on arenduskeskonnas liides SecreC kompileerimiseks assemblerkeeleks, kasutades Sharemindi raamistiku SerceC kompilaatorit. Juhtimisteek lubab virtuaalmasinas assemblerkeelt käivitada ning siluda. Silumise töörežiimis saab uurida virtuaalmasina pinu ja registreid. Arenduskeskond on programmeeritud C++ keeles ning kasutab Qt raamistiku suure osa funktsioonide realiseerimiseks. Qt raamistik pakub laialdast funktsionaalsust ning on platvormist sõltumatu. Samuti on kasutatud QScintilla teeki keskse koodiredaktori loomiseks. QScintilla on Qt raamistikule kohandatud versioon Scintilla teegist, mis on laialdaselt tuntud lähtekoodi redaktori teek., The goal of the bachelor’s thesis is to design and develop an Integrated Development Environment (IDE) for a privacy-preserving framework called Sharemind. More precisely, the IDE will have to enable the developer to comfortably write and debug programs written in the languages designed for Sharemind which are the assembly language of the system and the SecreC language. Sharemind is a data processing system capable of performing computations on input data without compromising its privacy. The system is based on solid cryptographic foundations – secret sharing is used to preserve the privacy of the data during storage and secure multi-party computation allows the data to be securely processed. SecreC is a C-like programming language designed for developing privacy-preserving algorithms. Currently, the SecreC compiler generates assembly code that then can be run in the Sharemind virtual machine. It has been shown to be practical for a variety of data mining tasks. The aim of this thesis is to simplify the development of privacy-preserving software using the Sharemind framework. When Sharemind is easier to develop for, it may find more use in real-world applications and will lead us to information systems with significantly better privacy guarantees. The IDE will have all the basic functionality like project management, code highlighting and code-completion which have become standard features in modern code development environments. Debugging will be an essential part of the system and its functionality will be supported for the assembly language. The tool will be written in C++. The libraries that will be used are Qt for its wide range of functionality, Sharemind controller library which will be the central part for debugging and QScintilla (which is a Qt port for a component called Scintilla) for code editing.

https://www.ester.ee/record=b5412660*est

https://www.ester.ee/record=b5410363*est

https://www.ester.ee/record=b5433159*est