Kokkuvõte: We give an overview of the state of the art in secure electronic voting, focusing on protocols that meet the most stringent security requirements to date regarding ballot secrecy and election integrity. In particular, protocols based on homomorphic threshold encryption schemes and protocols based on so-called verifiable mixes will be considered in detail.
Kokkuvõte: Cryptographic proofs are mostly presented in the form of reduction from one (basic) cryptographic primitive (such as one-way function or collision-resistant hash function) to another (typically, a cryptographic protocol). Reduction has shown itself as a powerful tool for constructing provably secure cryptographic schemes. However, several interesting results exist that limit the scope of reduction techniques. We present a short overview of these "negative" results and outline the mathematical apparatus used to prove them. Finally, we introduce some new non-existence results about linkage-based time-stamping schemes.
Ettekande kiled. [pdf]
Kokkuvõte: Traditsiooniline otsingumootor (nt Google) teisendab etteantud märksõnad viideteks dokumentidele, mis kasutajale huvi võiksid pakkuda. Idee on lihtne: tulemustes viidatud dokument peab sisaldama etteantud märksõnu. Paljudel juhutudel on aga selliselt saadud tulemuste arv väga suur ja mürane (st dokumendid ei kirjelda huvipakkuvat infot) ning kasutaja peab hakkama päringut ümbersõnastama või lihtsalt suurt hulke dokumente läbi vaatama. Ettekanne vaatleb, kuidas loomuliku keele analüüsi vahendeid otsingutulemuste parandamiseks ära saaks kasutada, keskendudes süntaksianalüüsile.
Ettekande kiled. [pdf]
Kokkuvõte: Vaatleme selliseid funktoreid, mis viivad mingist väiksest kategooriast kõigi hulkade kategooriasse. Selliste funktorite põimikkorrutis on automaatide põimikkorrutise üldistus. Kui kahe sellise funktori G ja H põimikkorrutisega tensorkorrutamise funktor säilitab D-piirid (D on väike kategooria), siis funktoriga G tensorkorrutamine säilitab D-piirid. Kui funktorite G ja H põimikkorrutisega tensorkorrutamise funktor säilitab esitatavate funktorite D-piirid, siis funktoriga G ja funktoriga H tensorkorrutamine säilitab esitatavate funktorite D-piirid. Teatud lisaeeldustel on võimalik tõestada ka vastupidised väited.
Ettekande kiled. [pdf]
Kokkuvõte: We propose a new cryptographically protected multi-round auction mechanism for online auctions. This auction mechanism is designed to provide (in this order) security, cognitive convenience, and round-effectiveness. One can vary internal parameters of the mechanism to trade off bid privacy and cognitive costs, or cognitive costs and the number of rounds. We are aware of no previous work that interleaves cryptography explicitly with the mechanism design.
E. Elkind, H. Lipmaa. Interleaving Cryptography and Mechanism Design: The Case of Online Auctions. In Ari Juels, editor, Financial Cryptography - Eighth International Conference, volume ? of Lecture Notes in Computer Science, pages ?--?, Key West, FL, USA, February 9-12 2004. Springer-Verlag. Accepted. [ps.gz, ps.bz2, pdf]
Kokkuvõte: Categories are often used for representation of executable specifications of programming languages (e.g. automata). From the very beginning the decomposition methods for automata use wreath product construction. In this talk, a generalization of automata with "memory" is described as systems of type $({\rm {\bf A}}\longrightarrow {\rm {\bf Set}}; \Box)$. Wreath products of these systems are defined and studied as a general decomposition operation. These general conceptions are illustrated by the examples of specialization them to semigroup action systems, attributed automata etc.
Ettekande kiled. [pdf]
Kokkuvõte: Applets have popularized the idea of downloading and running untrusted code on your computer without user's intervention or approval. A similar model has been transferred to high-security embedded devices such as smartcards which are used in payments, mobile telephony and authentication. This raises major security issues, which are typically tackled by not allowing applets to directly access hardware resources, statically verifying properties like type and memory safety of the program etc. There are cases however, when one does not only need to be confirmed of security properties, but also needs to be assured that the program actually does what it is supposed to do. A way to address this issue is verifying the compiled code via programming logics and weakest precondition calculus. In the talk i will present the first steps towards developing a methodology for verifying the correctness of JVM bytecode programs. We start by looking at the verification of simple compiled while programs and then move to the extensions needed for a more complicated languages.
Ettekande kiled. [pdf]
Kokkuvõte: Finite-state devices such as finite-state automata (FSA) and finite-state transducers (FST) have been known in computer science since 1940s. In computational linguistics, however, for a long time more powerful formalisms such as context-free grammars or unification grammars have been preferred, as it was proved by Chomsky in 1960s, that natural languages are not finite-state nor context-free, nor even context-sensitive. Finite-state devices have been "rediscovered" and widely used in language technology during last two decades.
In the presentation the overview of the operations on FSTs, as well as algorithmic properties of FSTs are given. The most successful application areas of FSTs in language technology are introduced. Finite-state computational morphology, and specifically Estonian finite-state morphology are discussed in details. The use of operations on FSTs and regular expressions, such as concatenation, composition, inversion and Kleene's closure, are demonstrated by the examples of modeling the complex morphological processes in Estonian: inflection by means of both suffixing and stem changes, derivation and compounding, as well as guessing of the unknown words (words not included into the lexicon). Different approaches of modeling the natural language morphology are discussed, which are suitable for different language technological applications. Finally, weighted FSTs and their applications are introduced.
Ettekande kiled. [pdf]
Kokkuvõte: Monaadid on lihtne kategooriateooria mõiste, mille programmeerimisteooriasse tõid Moggi ja Wadleri teedrajavad uurimused ning mis sellest alates on radikaalselt muutnud mittepuhaste keelte semantika kirjeldamist ja programmeerimispraktikat puhastes keeltes. Ghani ja Lüth on propageerinud ideed, et õige modulaarne viis kõrvalefekte kombineerida on kasutades monaadide koprodukti. Oma ettekandes tutvustan põgusalt nimetatud teooriaid ning peatun lähemalt probleemil, kuidas rehkendada kahe ideaalse monaadi koprodukti. (Ühistöö N. Ghaniga.)
N. Ghani, T. Uustalu. Coproducts of ideal monads. Submitted to Theor. Inform. and Appl. [.ps]
Kokkuvõte: Nagu hästi teada, on rekursiivselt defineeritud funktsiooni termineeruvuse staatiliselt kindlaks tegemine on algoritmiliselt lahendamatu probleem. Seetõttu on nn. tugevas funktsionaalprogrammeerimises aktiivset uurimist leidnud keeled, kus üldrekursiivsed definitsioonid pole lubatud, vaid tuleb kasutada spetsiifilisi rekursioonioperaatoreid, mis tagavad programmide termineeruvuse konstruktsiooni kohaselt. Ettekandes vaatleme termineeruvaid rekursiooniaperaatorid, mis on indutseeritud teatavate omadustega koalgebrate poolt. See võimaldab käsitleda paljusid varem uuritud spetsiifilisi konstruktsioone ühteses formalismis ning loob võimaluse nende üldistamiseks. Muuhulgas demonstreerime komonaadilise rekursiooni üldistust antud raamistikus.
V. Capretta, T. Uustalu, V. Vene. Recursive Coalgebras from Comonads. Submitted to CMCS'04. [ps.gz]
Ettekande kiled. [pdf]
Kokkuvõte: Käesoleva seminari ülesanne on saada üle eestlastele nii omasest üksinokitsemisest ning üritada grupitöö korras tegeleda mõne lahendamist vajava arvutiteadusliku probleemiga. Seekord valisin valdkonnaks kergesti hoomatava (kuid kindlasti mitte kergekaalulise) mänguteooria, täpsemalt mänguprogrammides kasutusel olevad andmestruktuurid ning küsimuse, kas neid andmestruktuure saab organiseerida efektiivsemalt, kui arvesdada seisude lagunemisega sõltumatuteks alamseisudeks. Kuna sarnaseid probleeme on uuritud ka varem (kuigi kogu mängulaua jaoks), tuleks enne seminari kodus kindlasti tutvust teha kirjandusviidetega.
Viited materjalidele:
Peeter Laud