10.02.2005

Protokół rozproszonego generowania (pseudo)losowych liczb pierwszych

Przedstawiony będzie protokół generowania (pseudo)losowych liczb pierwszych przez kilku uczestników/agentów jednocześnie bez udziału żadnej tzw. zaufanej (podejrzanej?) trzeciej strony. W rezultacie każdy uczestnik będzie miał częściową informację o wygenerowanej liczbie pierwszej. Ale nikt (nawet serwer) nie będzie mógł jej odtworzyć bez zgody wszystkich uczestników. Ewentualnie, ze z góry określonym progiem większym niż połowa wszystkich uczestników, np. za zgodą co najmniej 3 spośród wszystkich 5. Podobnie jak w teście pierwszości Solovaya-Strassena, ważnym krokiem protokołu jest obliczanie symbolu Jacobiego, ale w rozproszonym środowisku wieloagentowym. Motywacja do zaprojektowania protokołu jest wzmocnienie zabezpieczeń rozmaitych kryptosystemów opartych na dużych liczbach pierwszych, np. algorytmów podpisu elektronicznego, czy schematów rozproszenia hasła/klucza [ang. secret sharing].