tmp leht katsetusteks
- Andris Ambainis
- Title: Quantum algorithms for trees of unknown structure
- Abstract: N/A
- Joint work with Martins Kokainis
- arxiv link
- Mohammad Fawaz Yousef Anagreh
- Egils Avots
- Aleksandrs Belovs
- Provably secure key establishment against quantum adversaries
- Abstract: At Crypto 2011, some of us had proposed a family of cryptographic protocols for key establishment capable of protecting quantum and classical legitimate parties unconditionally against a quantum eavesdropper in the query complexity model. Unfortunately, our security proofs were unsatisfactory from a cryptographically meaningful perspective because they were sound only in a worst-case scenario. Here, we extend our results and prove that for any {$ e > 0 $}, there is a classical protocol that allows the legitimate parties to establish a common key after {$ O(N) $} expected queries to a random oracle, yet any quantum eavesdropper will have a vanishing probability of learning their key after {$ O(N^{1.5-e}) $} queries to the same oracle. The vanishing probability applies to a typical run of the protocol. If we allow the legitimate parties to use a quantum computer as well, their advantage over the quantum eavesdropper becomes arbitrarily close to the quadratic advantage that classical legitimate parties enjoyed over classical eavesdroppers in the seminal 1974 work of Ralph Merkle. Along the way, we develop new tools to give lower bounds on the number of quantum queries required to distinguish two probability distributions. This method in itself could have multiple applications in cryptography. We use it here to study average-case quantum query complexity, for which we develop a new composition theorem of independent interest.
- Authors: Aleksandrs Belovs, Gilles Brassard, Peter Hoyer, Marc Kaplan, Sophie Laplante, Louis Salvail
- arxiv link
- Ivan Bliznets
- Silvio Capobianco
- Title: Nonuniversality in Computation: a (non)-disproof of the Church-Turing thesis
- Abstract: In a 2005 paper, Selim G. Akl proved a fundamental theorem of unconventional computation: no discrete machine that can perform only boundedly many operations at any given time can perfectly simulate every computing machine. As a corollary to this result, Akl inferred that the Church-Turing thesis is false: such claim summoned much criticism, addressed by him in a 2015 paper. In this talk, I will discuss Akl's theorem, the controversy it raised, and the flaws in the argument for refuting the Church-Turing thesis: among these, that the latter appears to be incorrectly stated.
- Publication info: The talk expands a 2016 talk from the Theory Lunch sessions at the Institute of Cybernetics, of which a report can be found here: https://theorylunch.wordpress.com/2016/09/08/nonuniversality-in-computation-a-proof-by-semantic-shift/
- Tore Vincent Carstens
- Title: On quantum indistinguishability under chosen plaintext attacks
- Abstract: N/A
- Publication info: not published yet
- Maksims Dimitrijevs
- Ehsan Ebrahimi
- Title: On Quantum Indifferentiability
- Abstract: In this talk, we present the Indifferentiability framework in the quantum setting in which the quantum distinguisher has classical access to the construction and superposition access to the underlying primitive used in the construction. This is applicable to the post-quantum cryptography setting. We show that almost all the classical construction are not perfectly quantum indifferentiable from the random oracle (or ideal cipher).
- Not published yet
- Joint work with Dominique, Tore and Gelo
- Ludmila Glinskih
- Juhani Karhumäki
- Title: Reachability via co-opreating morphism
- Abstract: The goal of this presentation is to analyze the equality mechanism of co-operating morphisms of free monoids, and to point out that the reachability questions lead to undecidability and easy characterizations of recursively enumerable languages. In particular, we aim to show, which subcontructions are needed in such results. Moreover, we recall that in some cases the undecidability of the reachability is achieved although the sets of all reachable objects are simple, more formally, regular languages.
- Publication info:
- J. Karhumäki, On the power of cooperating morphisms via reachability problems, IJFCS 20 (2009), 803-818.
- J.Karhumäki and A. Saarela, Noneffective regularity of equality languages of bounded delay morphisms, DMTCS 12 (2010) 9-17.
- Petteri Kaski
- Kamil Khadiev
- Aliya Khadieva
- Title: Reordering Method for Quantum and Classical Ordered Binary Decision Diagrams.
- Abstract: We consider Quantum OBDD model. It is restricted version of read-once Quantum Branching Programs, with respect to ''width'' complexity. It is known that maximal complexity gap between deterministic and quantum model is exponential. But there are few examples of such functions. We present method (called reordering), which allows to build Boolean function {$ g $} from Boolean Function {$ f $}, such that if for {$ f $} we have gap between quantum and deterministic OBDD complexity for natural order of variables, then we have almost the same gap for function {$ g $}, but for any order. Using it we construct the total function {$ REQ $} which deterministic OBDD complexity is {$ 2^{\Omega( \frac{n}{log n})} $} and present quantum OBDD of width {$ O(n^2) $}. It is bigger gap for explicit function that was known before for OBDD of width more than linear.
- Joint work with Kamil Khadiev
- arxiv link springer link
- Toomas Krips
- Title: Alternative Implementations of Secure Real Numbers
- Abstract: This paper extends the choice available for secure real number implementations with two new contributions. We will consider the numbers represented in form a-φ b where φ is the golden ratio, and in form (-1)s.2e where e is a fixed-point number. We develop basic arithmetic operations together with some frequently used elementary functions. All the operations are implemented and benchmarked on SHAREMIND secure multi-party computation framework. It turns out that the new proposals provide viable alternatives to standard floating- and fixed-point implementations from the performance/error viewpoint in various settings. However, the optimal choice still depends on the exact requirements of the numerical algorithm to be implemented.
- Publication info: published in ACM CCS 2016
- eprint link
- Ivo Kubjas
- Title: Two-Party Function Computation on the Reconciled Data
- Abstract: We look at a new problem termed function computation on the reconciled data, which generalizes a set reconciliation problem in the literature. Assume a distributed data storage system with two users A and B. The users possess a collection of binary vectors S_A and S_B, respectively. They are interested in computing a function {$ \phi $} on the reconciled data $S_A \cup S_B$.
It is shown that any deterministic protocol, which computes a sum of reconciled sets of binary vectors represented as nonnegative integers, has to communicate at least {$2^n + n - 1 $} bits in the worst-case scenario, where {$ n $} is the length of the binary vectors. Connections to other problems in computer science, such as set disjointness and finding the intersection, are established, yielding a variety of additional upper and lower bounds on the communication complexity. A protocol for computation of a sum function, which is based on use of a family of hash functions, is presented, and its characteristics are analyzed.
- arxiv link
- Joint work with Vitaly Skachek
- Publication info: Two-Party Function Computation on the Reconciled Data; 55th Annual Allerton Conference on Communication, Control, and Computing; October 4-6, 2017; Monticello, IL, USA.
- Peeter Laud
- Title: Secure Multiparty Sorting Protocols with Covert Privacy
- Abstract: We introduce the notion of covert privacy for secret-sharing-based secure multiparty computation (SMC) protocols. We show how covertly or actively private SMC protocols, together with recently introduced verifiable protocols allow the construction of SMC protocols secure against active adversaries. For certain computational problems, the relative overhead of our protocols, when compared to protocols secure against passive adversaries only, approaches zero as the problem size increases. We analyse the existing adaptations of sorting algorithms to SMC protocols and find that unless they are already using actively secure primitive protocols, none of them are covertly private or verifiable. We propose a covertly private sorting protocol based on radix sort, the relative over head of which again approaches zero, when compared to the passively secure protocol. Our results reduce the computational effort needed to counteract active adversaries for a significant range of SMC applications, where sorting is used as a subroutine.
- Joint work with Martin Pettai
- Publication info: N/A
- Hendrik Maarand
- Title: Certified Foata Normalization for Generalized Traces
- Abstract: Mazurkiewicz traces are a well-known formalism for non-interleaving concurrency. The two essential components of it are the alphabet and the independency relation on the alphabet, which describes which pairs of letters in a string are allowed to commute so that the meaning of the string stays the same. A trace is thus an equivalence class of strings where two strings are equivalent if one can be transformed to the other by repeatedly exchanging adjacent independent elements. In its standard form the independency relation is fixed. As part of their effort to classify models of concurrency, Sassone, Nielsen and Winskel have developed a generalization of Mazurkiewicz traces where the independency relation may depend on the context where it is used. We present a definition of the Foata normal form for these generalized traces together with a normalization algorithm and its correctness proof in the dependently typed programming language Agda. We motivate our work with an example from shared memory concurrency.
- Publication info: N/A
- Abdullah Makkeh
- Title: Bivariate Partial Information Decomposition: The Optimization Perspective
- Abstract: Bertschinger, Rauh, Olbrich, Jost, and Ay (Entropy, 2014) have proposed a definition of a decomposition of the mutual information MI(X : Y,Z) into shared, synergistic, and unique information by way of solving a convex optimization problem. We will discuss the solution of their Convex Program from theoretical and practical points of view.
- Publication info: published in Entropy journal volume 19 issue 10
- Link
- Härmel Nestra
- Title: Double Applicative Functors
- Abstract: We propose an approach using double applicative functors to increase the expressive power of exception handling in parsing.
- Publication info: N/A
- Fatemeh Noroozi
- Alisa Pankova
- Title: Privacy-preserving duplication detection
- Abstract: This talk describes our solution for Track 1 of the iDASH privacy and security workshop (http://www.humangenomeprivacy.org/2017). The goal of this track was to develop privacy-preserving technique that removes duplicated entries from datatables that belong to independent clients. Each client uploads its (encrypted) data to the servers, and for each record it should get back a bit denoting which records have already been uploaded before by some other clients, and hence need to be removed. We propose two solutions to this problem. The first one is faster, but it is secure only if the outputs are returned to all clients simultaneously in the end, after all clients have already uploaded their data. The second solution is slower, but it remains secure even if the results have to be output to a client immediately after its data are uploaded.
- Joint work with Peeter Laud
- Publication info: N/A
- Janno Siim
- Vitaly Skachek
- Title: Constructions and Bounds for Batch Codes with Small Parameters
- Abstract: Linear batch codes and codes for private information retrieval (PIR) with a query size t and a restricted size r of the reconstruction sets are studied. New bounds on the parameters of such codes are derived for small values of t or r by providing corresponding constructions. By building on the ideas of Cadambe and Mazumdar, a new bound in a recursive form is derived for batch codes and PIR codes.
- Joint work with Eldho K. Thomas
- Jukka Suomela
- Marek Sýs
- Hellis Tamm
- Title: Theoretical aspects of symbolic automata.
- Abstract: Symbolic finite automata extend classical automata by allowing infinite alphabets given by Boolean algebras and having transitions labeled by predicates over such algebras. Symbolic automata have been intensively studied recently and they have proven useful in several applications. We study some theoretical aspects of symbolic automata. Especially, we study minterms of symbolic automata, that is, the set of maximal satisfiable Boolean combinations of predicates of automata. We define canonical minterms of a language accepted by a symbolic automaton and show that these minterms can be used to define symbolic versions of some known classical automata. Also we show that canonical minterms have an important role in finding minimal nondeterministic symbolic automata. We show that Brzozowski's double-reversal method for minimizing classical deterministic automata as well as its generalization is applicable for symbolic automata.
- Publication info: SOFSEM 2018
- link
- Jevgenijs Vihrovs
- Markus Whiteland
- Title: On $k$-Abelian Equivalence Classes via Regularity
- Abstract: Two words u and v are said to be $k$-abelian equivalent if, for each word $x$ of length at most $k$, the number of occurrences of {$ x $} as a factor of {$ u $} is the same as for {$ v $}. We study some combinatorial properties of {$ k $}-abelian equivalence classes. Using an alternative characterization of $k$-abelian equivalence we show that, over any fixed alphabet, the language of lexicographically least representatives of {$ k $}-abelian equivalence classes is a regular language. The growth function of this language (i.e., the function giving, for each {$ n $}, the number of words of length {$ n $} in the language) gives the function giving the number of distinct {$ k $}-abelian equivalence classes of length {$ n $}. It was known that this language has a polynomial growth function, that is, the number of words of length $n$ in the language is of order $\Theta(n^r)$ for some $r\in\mathbb{N}$ depending on $k$. We show that, in fact, the growth of the language is asymptotically equal to a polynomial, that is, the constants implied by $\Theta$ above can be taken to be equal. The aim of this talk is to discuss analysis of regular languages with polynomial growth, especially on how to distinguish growth functions that are asymptotically equal to a polynomial.
- Publication info: not available
- link
- Abuzer Yakaryilmaz
- Yauhen Yakimenka
- Title: Distance Properties of Short LDPC Codes and their Impact on the BP, ML and Near-ML Decoding Performance
- Abstract: In this work, we study different parameters of low-density parity-check (LDPC) codes, such as minimum distance, stopping distance, stopping redundancy, girth of the Tanner graph - and their influence on decoding performance for different decoding methods. For different codes, we also provide simulation results to support our findings.
- Publication info: Castle Meeting 2017
- Michal Zajac
- Bingsheng Zhang
- Title: Statement Voting and Liquid Democracy
- Abstract: In this work, we introduce a new concept, statement voting. Statement voting can be viewed as a natural extension of traditional candidate voting. Instead of defining a fixed election candidate, each voter can define a statement in his or her ballot but leave the vote undefined during the voting phase. During the tally phase, the (conditional) actions expressed in the statement will be carried out to determine the final vote. We provide a comprehensive study of this new concept: under the Universal Composability (UC) framework, we define a class of ideal functionalities for statement voting, and then construct several protocols for realizing these functionalities. Since statement voting covers liquid democracy as a special case, our constructions immediately provide us the first solutions to liquid democracy. We remark that our statement voting can be extended to enable more complex voting and generic ledger-based non-interactive multi-party computation. We believe that the statement voting concept opens a door for constructing a new class of e-voting schemes.
- Publication info: N/A
- Eprint link
