M. Agrawal, N. Kayal, N. Saxena. PRIMES is in P. Preprint, 2002. [html, pdf, ps]
Sveni ülevaateartikkel. [ps.gz]
Ettekande kiled. [ps.gz]
Kokkuvõte: Ettekanne on pühendatud hiljutisele avastusele - keel PRIMES on keerukusklassis P, st. on leitud tõestatult polünomiaalses ajas töötav algarvulisuse kontrolli algoritm (Agrawal, Kayal, Saxena 2002). Esmalt anname lühiülevaate probleemi ajaloost ning selle olulisusest algoritmilises arvuteoorias ning keerukusteoorias. Probleem PRIMES kuulub keerukusklasside NP ja co-NP lõikesse. Alates 70ndatest aastatest on püütud näidata selle (mitte)kuulumist klassi P. Kahjuks ei selgita positiivne tulemus PRIMES in P tuntud keerukusklasside vahekorda, vaid sunnib püstitama uusi testülesandeid.
Arvutialgebra seisukohast pole uuel algoritmil praktilist tähtsust, kuna selle keerukus Õ(log12 n) on võrreldes tõenäosuslike Solovay-Strassen (1977) ja Miller-Rabin (1976-80) testide keerukusega Õ(log2 n) liiga suur. Kui leiab kinnitust uus arvuteoreetiline hüpotees, siis on võimalik vähendada keerukust Õ(log3 n), mis oleks rakendusteks piisav.
Oluline võit kiiruses on saavutatud algarvulisust või seda ümber lükkavate sertifikaatide arvu ja väärtuste piiramisega O(log6 n). See võimaldab teostada otsinguid polünomiaalses ajas hoolimata sellest, et vajaliku sertifikaadi leidmine ise on keeruline. Ettekandes näitamegi, et sertifikaatide arv on piiratud ning nende leidmine ja kontroll on polünomiaalses ajas tehtav.
Kokkuvõte: Ettekandes antakse ülevaade digitaalallkirja kontseptsiooni ajaloost, mis algas 1976. aastal seoses Diffie ja Hellmanni teedrajava avastusega. Tutvustatakse lühidalt digitaalallkirja krüptograafilisi mehhanisme ja selgitatakse, mida tähendab nende turvalisus matemaatilises mõttes. Vaadeldakse ka mehhanisme, mis aitavad praktikas kaitsta allkirja moodustamiseks kasutatavat krüptograafilist võtit. Püütakse vastata küsimusele, miks juba täna ei kasutata digitaalallkirja massiliselt ja millal ja miks see juhtuda võiks.
Ettekanne on osaliselt ajendatud ülemaailmsest kriisist, mis on tekkinud peale juba ligi kümme aastat kestnud üritusi digitaalallkirja massiliselt kasutama hakata. Üheks põhjuseks loeb ettekande autor üha süvenevat lahkheli krüptograafias käsitletava "teoreetilise turvalisuse" ja reaalses maailmas vajaliku "praktilise turvalisuse" vahel, mis põhineb riskide maandamisel.
Ettekandes näidatakse, et teaduslik lähenemine tegeliku turvalisuse probleemile võimaldab koostada palju listsamaid lahendusi digitaalallkirja kasutamisele, kui senised, ja võib kaasa aidata ka digitaalallkirja massilisele levikule.
Kokkuvõte: Programmikeelte teooria üks suuri suundi hetkel on tüübisüsteemid kui väga paindlik vahend mitmesuguste ohutusdistsipliinide sisseehitamiseks programmikeeltesse ning modulaarsust, "murede lahutamist" ning programmikeeltele programmiloogikate pealeehitamist toetav disainiprintsiip. Tüübisüsteemide teoreetiliseks aluseks on kaks matemaatilise loogika haru, tüübiteooria ja tõestusteooria, mida omavahel seostab Curry-Howardi isomorfismina tuntud vastavus teatud tüübisüsteemide ja tõestussüsteemide vahel. Oma baaskujul väidab C-H isomorfism, et lihtsalt tüübitud lambda-arvutus ning intuitsionistliku lauseloogika loomuliku tuletuse süsteem on sisuliselt üks ja sama asi. C-H isomorfism on sedastatav ka polümorfselt tüübitud lambda-arvutuse ja intuitsionistliku 2. järku lauseloogika vahel, sõltuvalt tüübitud lambda-arvutuse ja intuitsionistliku predikaatloogika vahel jne. Ootamatum aga on, et klassikalise lauseloogika mitmesugused võimalikud loomuliku tuletuse süsteemid on vaadeldavad juhtimisoperaatoreid toetavate tüübitud funktsionaalkeeltena.
Ettekande kiled. [pdf]
Kokkuvõte: Boole'i funktsioonide esitamine binaarsetel otsustusdiagrammidel (BDDdel). Shannoni arendusel põhinevad BDDd, nende optimeerimine; redutseeritud järjestatud BDDd (ROBDDd), ROBDDde omadused ja rakendusvaldkond. Struktuursete BDDde süntees, omadused; alternatiivne BDDde esitusviis, suunareegel. ROBDD ja struktuurse BDD mudeli võrdlus. Digitaalseadmete test ja rikete modelleerimine; defekt, viga, rike; konstantrikete mudel. Rikete simuleerimise ülesanne. Struktuursete BDDde eelised rikete simuleerimisel.
Ettekande kiled. [ps.gz]
Kokkuvõte: Osutub, et algoritmid Boole'i valemite kehtestavate väärtuste arvu loendamiseks ja antud valemi järgi BDD konstrueerimiseks on omavahel tihedalt seotud keskse mõiste "ortogonaalne DNF" kaudu. Ettekandes üritatakse selgitada ülalnimetatud seost ning vaadata, milleks see seos võib kasulik olla.
J. Villemson. Size-efficient interval time stamps (PhD thesis). Diss. Math. Univ. Tartuensis, v. 29. Univ. of Tartu, 2002. [ps.gz]
Kokkuvõte: Digitaalsignatuuride ajatembelduses osutuvad otstarbekateks binaarsed linkimisskeemid, millele saab ehitada intervallajatembeldussüsteeme. Ettekandes uuritakse, kuidas neid süsteeme nii ehitada, et saadavate ajatemplite suurus tuleks optimaalne. Tõestatakse templi suuruse asümptootiline alamtõke ning näidatakse graafipere, mis sellele tõkkele läheneb.
Ettekande kiled. [ps.gz]
Kokkuvõte: Tänapäeval on magasinorienteeritud keeled (näit. Forth) kasutusel assemblerkeele rollis piiratud ressurssidega tööstuslikes süsteemides (robootika, sardsüsteemid, smartcard-rakendused jm.). Selliste süsteemide testimine enne miljonitesse eksemplaridesse tiraz^eerimist on igati aktuaalne probleem. Magasinkeelte puhul pakub peamist huvi kontroll magasini kasutamise üle. Seni rakendust leidnud vahendid piirduvad enamasti magasini sügavuse hindamisega, staatilise tüübikontrolli vahendeid on arendatud, kuid senised realisatsioonid pole tööstusesse jõudnud.
Käesolevas ettekandes tutvustatakse raamistikku, mis lubab analüüsida magasinoperatsioonide jada ning arvutada operatsioonide tegelikku käitumist konkreetses kontekstis. Defineeritakse formaalsed reeglid magasineffektide arvutamiseks, mis toetavad nn. jokkertüüpe ning tüüpide hierarhiat, samuti polümorfseid operatsioone.
P. Laud. Computationally secure information flow (PhD thesis). Univ. des Saarlandes, 2002. [html, ps.gz]
Ettekande kiled. [ps.gz]
Kokkuvõte: Mingil programmil, mis töötleb salajasi andmeid, võib olla ka vaja osa oma väljunditest avalikuks teha. Sel juhul tuleks kindel olla, et neist avalikest väljunditest ei saaks tuletada mingeidki tulemusi töödeldavate salajaste andmete kohta. Me ütleme, et programmil on turvaline infovoog, kui tema salajased sisendid ja tema avalikud väljundid on teineteisest sõltumatud.
Krüptimise väljund - krüptotekst - tavaliselt ei ole vastavast avatekstist sõltumatu (vähemalt senini, kuni võti on avatekstist lühem). Sellegipoolest ütleb meie intuitsioon, et krüptitud kujul võib salajasi asju avalikuks teha, mingit infoleket see ei põhjusta. Asi on selles, et krüptotekst on talle vastavast avatekstist arvutuslikult sõltumatu - mitte ükski kiire algoritm ei ole suuteline aru saama, et nendevaheline sõltuvus olemas on.
Arvutuslikust sõltuvusest jõuame kohe ka arvutuslikult turvalise infovoo mõisteni. Kui me infolekete puudumise all mõistame infovoo arvutuslikku turvalisust, siis saame me ka neid programme turvaliseks pidada, mis oma salajasi sisendeid krüptivad ja tulemusi avalikustavad. Käesolevas ettekandes me käsitlemegi seda definitsiooni lähemalt.
Me tutvustame ka staatilist programmianalüüsi, mille abil on võimalik kontrollida, kas programmil on arvutuslikult turvaline infovoog. Programmianalüüs järgib krüptimisprimitiivi intuitiivseid omadusi (krüptoteksti arvutuslik sõltumatus avatekstist).
H. Lipmaa, N. Asokan, V. Niemi. Secure Vickrey auctions without threshold trust. To appear in Proc. of 6th Int. Financial Cryptography Conf., FC'02 (Southampton Beach, Bermuda, March 2002), Lect. Notes in Comp. Sci., Springer-Verlag, Berlin. [html, ps.gz, pdf]
Roosta ettekande kiled. [pdf]
Kokkuvõte: We argue that threshold trust is not an option in most of the real-life electronic auctions. We then propose two new cryptographic Vickrey auction schemes that involve, apart from the bidders and the seller S, an auction authority A so that unless S and A collude the outcome of auctions will be correct, and moreover, S will not get any information about the bids, while A will learn bid statistics. Further extensions make it possible to decrease damage that colluding S and A can do, and to construct (m+1)st price auction schemes. The communication complexity between the S and A in medium-size auctions is at least one order of magnitude less than in the Naor-Pinkas-Sumner scheme.
Helger Lipmaa