Student Talks 2014 (abstracts)
Update Monads
Danel Ahman
University of Edinburgh, LFCS, United Kingdom
We introduce an interesting class of monads, called update monads, that form a true generalization of reader and writer monads.
An update monad is given by a set (of states), a monoid (of updates) and an action of the monoid on the set (expressing the effect that updates have on states). Update monads arise as compatible compositions of reader and writer monads, or equivalently, as distributive laws between reader and writer monads. As a result, while state monads fail to be a common generalization of reader and writer monads, update monads are so.
Update monads cover many natural examples. For example, reader and writer monads are special cases of update monads. State monads arise as those update monads where the monoid of updates is the free monoid on the overwrite semigroup structure on the set of states. Further examples with clear programming meaning are given by the state-logging monad and a monad for fixed-size write-once-read-multiple-times buffers.
A finer dependently-typed variation of the concept associates to every state its own set of enabled updates. A dependently-typed update monad is given by a directed container structure, rather than by a set and monoid related by an action. Categorically, such monads arise as the interpretation of the opposite category of directed containers into set functors.
This is joint work with Tarmo Uustalu.
Online Suffix Array Construction
Pavel Ajtkulov
Udmurt State University, Fac. of IT and Computer Engineering , Russian Federation
Authors: Dmitry Urbanovich, Pavel Ajtkulov
Suffix array is a data structure that has numerous applications such as building full-text indexes, data compression and sequences analysis. Suffix array sorts all the suffixes of the given string lexicographically, thus allowing to collocate repeating patterns in order to analyze them.
There exist a number of algorithms to efficiently construct suffix array from the ground up, as well as algorithms to efficiently transform suffix array in response to small changes in the string. The latter group of algorithms solves so called Dynamic Suffix Array Problem. We consider a restricted version of this problem which only allows to add new symbols to the end of the string (online construction). We aim to explore the possibility to efficiently construct suffix array in such a setting.
The result is the algorithm with complexity O(n log n), adding each new character with amortized O(log n), which is optimal for choosen underlying dynamic data structure. We also showed that string matching can be done online within O(k + log n) despite the fact we are using dynamic data structure with logarithmic factor slowdown. The algorithm uses essentially the same idea as Ukkonen’s algorithm [1]: it makes use of implicit suffixes, whose materialization is postponed. The underlying data structure is based on balanced binary search tree and is responsible for storing suffix array itself as well as quickly modifying it. It also maintains LCP array — an important tool for lowering time complexity upper bound.
To our best knowledge such an algorithm has not been yet presented. There is an alternative approach [2]: build suffix array for text in reverse order and match in reverse as well. This approach has a drawback that you don’t have actual suffix array of non-reversed text. Also supporting sliding window in such a setting isn’t straightforward if possible at least. There’s also Salson’s dynamic extended suffix array [3] which allows all this, but doesn’t guarantee worst case amortization.
The work is complete with respect to the stated goal.
- E. Ukkonen, E. On-line construction of suffix trees. Algorithmica, v. 14, n. 3, pp. 249-260, 1995.
- V. Mäkinen, G. Navarro, K. Sadakane. Advantages of backward searching - efficient secondary memory and distributed implementation of compressed suffix arrays. In Proc. of ISAAC 2004, v. 3341 of Lect. Notes in Comput. Sci., pp. 681-692. Springer, 2004.
- M. Salson, T. Lecroq, M. Léonard, L. Mouchard. Dynamic extended suffix arrays. In Journal of Discrete Algorithms, v. 8, n. 2, pp. 241-257, 2010.
Input Synthesis for Sampled Data Systems with Program Logic
Takumi Akazaki
University of Tokyo, Japan
Inspired by a concrete industry problem we consider the input synthesis problem for hybrid systems: given a hybrid system that is subject to input from outside (also called disturbance or noise), find an input sequence that steers the system to the desired postcondition. In this paper we focus on sampled data systems—systems in which a digital controller interrupts a physical plant in a periodic manner, a class commonly known in control theory—and furthermore assume that a controller is given in the form of an imperative program. We develop a structural approach to input synthesis that features forward and backward reasoning in program logic for the purpose of reducing a search space. The effectiveness of our approach is demonstrated by a prototype implementation that successfully solves the original problem of a considerable size.
A Hybrid Model of Fixed and Floating Point Numbers in Secure Multiparty Computations
Toomas Krips
University of Tartu, Inst. of Computer Science, Estonia
We developed fixed-point numbers for the secure multiparty computation platform Sharemind. We also used Chebyshev polynomials and Taylor polynomials to implement square root, inverse, the exponential function and the error functions on fixed-point numbers and on a hybrid version of fixed-point numbers and floating-point numbers.
Verifiable Computation in Multiparty Protocols with Honest Majority
Alisa Pankova
Cybernetica AS, Estonia
A lot of cryptographic protocols have been proposed for semi-honest model. In general, they are much more efficient than those proposed for the malicious model. In this paper, we propose a method that allows to detect the parties that have violated the protocol rules after the computation has ended, thus making the protocol secure against covert attacks. This approach can be useful in the settings where for any party it is fatal to be accused in violating protocol rules. In this way, up to the verification, all the computation can be performed in semi-honest model, which makes it very efficient in practice. The verification is statistical zero-knowledge, and it is based on linear probabilistically checkable proofs (PCP) for verifiable computation. Each malicious party is detected with probability (1 - e) for a negligible e that is defined by the failure of the corresponding linear PCP. The initial protocol has to be executed only once, and the verification requires in total 5 additional rounds in the end. If some parties act dishonestly, in the worst case they may force the protocol to substitute each round with 2 rounds, due to the transmission functionality that prevents the protocol from stopping. The verification also ensures that all the parties have sampled all the randomness from an appropriate distribution. Its efficiency does not depend on whether the inputs of the parties have been shared, or each party uses its own private input.
From Input-Private to Universally Composable Secure Multiparty Computation
Pille Pullonen
Cybernetica AS, Estonia
Secure multiparty computation systems are commonly built form a small set of primitive components. If the initial blocks are composable then we can infer the security properties of the composed system from the properties of the initial components. The standard notions of universally composable security can be overly restrictive in secure multiparty computation context and can lead to protocols with sub-optimal efficiency as additional steps are required to make the functionality secure. As a countermeasure, we introduce a notion of privacy that is satisfied by simpler protocols and is preserved by composition. We also fix a passive security model and show how to convert a black-box private protocol into a black-box universally composable protocol in the passive model. Therefore, we obtain a possibility to compose secure protocols out of efficient private protocols and a secure universally composable finishing step.
Specifying Sharemind's Arithmetic Black Box
Jaak Randmets
Cybernetica AS, Estonia
In this talk, we discuss the design choices and initial experiences with a domain-specific language and its optimizing compiler for specifying protocols for secure computation. We give the rationale of the design, describe the translation steps, the location of the compiler in the whole Sharemind protocol stack, and the results we have obtained with the system.
Online Suffix Array Construction
Dmitrii Urbanovich
Udmurt State University, Fac. of IT and Computer Engineering, Russian Federation
Authors: Dmitry Urbanovich, Pavel Ajtkulov
Suffix array is a data structure that has numerous applications such as building full-text indexes, data compression and sequences analysis. Suffix array sorts all the suffixes of the given string lexicographically, thus allowing to collocate repeating patterns in order to analyze them.
There exist a number of algorithms to efficiently construct suffix array from the ground up, as well as algorithms to efficiently transform suffix array in response to small changes in the string. The latter group of algorithms solves so called Dynamic Suffix Array Problem. We consider a restricted version of this problem which only allows to add new symbols to the end of the string (online construction). We aim to explore the possibility to efficiently construct suffix array in such a setting.
The result is the algorithm with complexity O(n log n), adding each new character with amortized O(log n), which is optimal for choosen underlying dynamic data structure. We also showed that string matching can be done online within O(k + log n) despite the fact we are using dynamic data structure with logarithmic factor slowdown. The algorithm uses essentially the same idea as Ukkonen’s algorithm [1]: it makes use of implicit suffixes, whose materialization is postponed. The underlying data structure is based on balanced binary search tree and is responsible for storing suffix array itself as well as quickly modifying it. It also maintains LCP array — an important tool for lowering time complexity upper bound.
To our best knowledge such an algorithm has not been yet presented. There is an alternative approach [2]: build suffix array for text in reverse order and match in reverse as well. This approach has a drawback that you don’t have actual suffix array of non-reversed text. Also supporting sliding window in such a setting isn’t straightforward if possible at least. There’s also Salson’s dynamic extended suffix array [3] which allows all this, but doesn’t guarantee worst case amortization.
The work is complete with respect to the stated goal.
- E. Ukkonen, E. On-line construction of suffix trees. Algorithmica, v. 14, n. 3, pp. 249-260, 1995.
- V. Mäkinen, G. Navarro, K. Sadakane. Advantages of backward searching - efficient secondary memory and distributed implementation of compressed suffix arrays. In Proc. of ISAAC 2004, v. 3341 of Lect. Notes in Comput. Sci., pp. 681-692. Springer, 2004.
- M. Salson, T. Lecroq, M. Léonard, L. Mouchard. Dynamic extended suffix arrays. In Journal of Discrete Algorithms, v. 8, n. 2, pp. 241-257, 2010.
Last changed
November 26, 2014 19:55 EET
by
local organizers, ewscs14(at)cs.ioc.ee
EWSCS'14 page:
//cs.ioc.ee/ewscs/2014/