Algorytmy transformacji wielomianowych i ich zastosowania

Widok

Metadane zasobu

Tytuł	Algorytmy transformacji wielomianowych i ich zastosowania
Osoby	Autorzy: Joanna Ewa Kapusta Partner: Instytut Badań Systemowych PAN w Warszawie
Opis	W pracy zaprezentowano nowe algorytmy obliczania transformacji wielomianowych dla baz zależnych od specjalnych konfiguracji punktów. Proponowane algorytmy operują na zbiorach punktów rozszerzających klasę ciągów punktów, dla których znane są szybkie algorytmy tego rodzaju. Przedstawiono algorytmy dla jednowymiarowych oraz wielowymiarowych transformacji wielomianowych wykorzystujących bazy Lagrange’a, Newtona i potęgową z uwzględnieniem punktów, których współrzędne są generowane przez równanie rekurencyjne pierwszego rzędu. Wspomniane algorytmy w istotny sposób wykorzystują jedno- i wielowymiarowe sploty. Zaprezentowano je w postaci łatwej do efektywnej implementacji. Ponadto przeprowadzono szczegółową analizę złożoności obliczeniowej tych algorytmów. Podane zostały ich zastosowania w aktualnych problemach kryptograficznych takich jak: dzielenie sekretu, głosowanie elektroniczne, wymiana kluczy z wykorzystaniem transmisji rozgłoszeniowej. W pracy szczególną uwagę zwrócono na głosowania elektroniczne ze względu na duży potencjał, jaki ze sobą niosą oraz na naturalne powiązanie prezentowanego modelu głosowań z omawianymi algorytmami transformacji wielomianowych. Przedstawiono model, który może być wykorzystany do zbierania i zliczania głosów oddawanych przez internet oraz z wykorzystaniem maszyn do głosowania. Zaprezentowano hierarchiczny model dzielenia sekretu, który jest uogólnieniem klasycznego schematu Shamira. Schemat Shamira bazuje na interpolacji Lagrange’a, natomiast proponowany hierarchiczny model dzielenia sekretu bazuje na interpolacji Hermite’a. Zastosowanie interpolacji Hermite’a pozwala na stosowanie tego schematu w grupach o ustalonej hierarchii. W pracy przedstawiono kilka wariantów schematu dzielenia sekretu umożliwiających dopasowanie go do potrzeb tego typu grup. Zaprezentowany model pozwala również na uwzględnienie sytuacji, w której do odzyskania sekretu konieczne jest uczestnictwo wybranych jednostek. W pracy skupiono się na praktycznych zastosowaniach, możliwych do wykorzystania w życiu społecznym czy przedsięwzięciach komercyjnych (głosowania, transmisja rozgłoszeniowa). (Polski) Opis w innym języku: The paper presents new algorithms for calculating polynomial transformations for bases dependent on special configurations of points. The proposed algorithms operate on sets of points extending the class of point sequences, for which fast algorithms of this type are known. The algorithms for one-dimensional and multivariate polynomial transformations using Lagrange, Newton and power bases are given including points whose coordinates are generated by the recursive equation first row. The mentioned algorithms make a significant use of one-dimensional and multidimensional weaves. In addition, a detailed analysis of the computational complexity of these algorithms was carried out. Their applications have been given in current cryptographic problems such as secret sharing, electronic voting, key exchange using broadcasting. In this work, particular attention was paid to electronic voting due to the high potential that they carry with them and the natural linking of the presented model of votes with the polynomial transformation algorithms under discussion. This model can be used to collect and count votes cast over the Internet and using voting machines. A hierarchical model of secret sharing is presented, which is a generalization of the classic Shamir scheme. Shamir's scheme is based on Lagrange interpolation, while the proposed hierarchical model of secret sharing is based on Hermite interpolation. The use of Hermite interpolation allows the use of this scheme in groups with a fixed hierarchy. The paper presents several variants of the secret sharing scheme that allows it to be adapted to the needs of these types of groups. The presented model also allows to take into account the situation in which the participation of selected units is necessary to regain the secret. The work focuses on practical applications that can be used in social life or commercial ventures (voting, broadcast). (Angielski)
Słowa kluczowe	"głosowanie elektroniczne"@pl, "jednowymiarowe transformacje wielomianowe"@pl, "wielowymiarowe transformacje wielomianowe"@pl, "baza Lagrange'a"@pl, "baza Newtona"@pl, "baza potęgowa"@pl, "transmisja rozgłoszeniowa"@pl, "dzielenie sekretów"@pl
Klasyfikacja	Typ zasobu: praca dyplomowa Dyscyplina naukowa: dziedzina nauk technicznych / informatyka (2011) Grupa docelowa: naukowcy, studenci, przedsiębiorcy Szkodliwe treści: Nie
Charakterystyka	Miejsce powstania: Warszawa Czas powstania: 2010 Liczba stron: 94 Promotor: Ryszard Smarzewski Język zasobu: Polski Lokalizacja: Warszawa
Licencja	CC BY-SA 4.0
Informacje techniczne	Deponujący: Justyna Kupczak Data udostępnienia: 16-10-2018
Kolekcje	Kolekcja Instytutu Badań Systemowych PAN w Warszawie, Kolekcja e-Biblio IBS PAN

Cytowanie

Skopiowano

Joanna Ewa Kapusta. Algorytmy transformacji wielomianowych i ich zastosowania. [praca dyplomowa] Dostępny w Atlasie Zasobów Otwartej Nauki, . Licencja: CC BY-SA 4.0, https://creativecommons.org/licenses/by-sa/4.0/legalcode.pl. Data dostępu: DD.MM.RRRR.

Podobne zasoby

Brak podobnych zasobów

Zobacz inne zasoby