Abstracts

• Andris Ambainis
  • Title: Quantum algorithms for trees of unknown structure
  • Abstract:
    • We study quantum algorithms on search trees of unknown structure, in a model where the tree can be discovered by local exploration. That is, we are given the root of the tree and access to a black box which, given a vertex {$ v $}, outputs the children of {$ v $}.
      We construct a quantum algorithm which, given such access to a search tree of depth at most {$ n $}, estimates the size of the tree {$ T $} within a factor of {$ 1 \pm \delta $} in {$ O(\sqrt{nT}) $} steps. More generally, the same algorithm can be used to estimate size of directed acyclic graphs (DAGs) in a similar model.
    • We then show two applications of this result:
    1. We show how to transform a classical search algorithm with backtracking which examines T nodes of a search tree into an {$ O(\sqrt{T}n^{3/2}) $} time quantum algorithm, improving over an earlier quantum algorithm of Montanaro.
    2. We give a quantum algorithm for evaluating AND-OR formulas in a model where the formula can be discovered by local exploration (modeling position trees in 2-player games). We show that, in this setting, formulas of size T and depth {$ T^{o(1)} $} can be evaluated in quantum time {$ O(T^{1/2+o(1)}) $}. Thus, the quantum speedup is essentially the same as in the case when the formula is known in advance.
  • Joint work with Martins Kokainis
  • arxiv link
• Mohammad Fawaz Yousef Anagreh
  • Title: Accelerate Performance of Calculation for Elliptic Curve Cryptosystem Based on MOF by Parallel Computing
  • Abstract: Elliptic Curve Cryptosystem (ECC) is widely used in devices with limited memory such as smart cards and PDAs. Many researchers are focusing to enhance the calculation of elliptic curve cryptosystem because ECC with 160-bits key size is a same security level with 2048-bits key size of RSA. This research focuses on optimizing the Elliptic Curve Cryptography (ECC) scalar multiplication by optimizing one of the ECC calculations, which is based on the Mutual Opposite Form (MOF) algorithm. MOF Algorithm is one of singed binary representation methods. The converting from binary representation to singed binary representation is to reduce the hamming weight which is number of non-zero bits in ECC Key. The goal of reducing hamming weight is to reduce the number of addition operations(ECCADD) in calculation the scalar multiplication of ECC. In this research a new algorithm is introduced (ASSM-MOF) that combines the add-subtract scalar multiplication algorithm with the MOF representation. The implementation of the algorithm produces an efficient parallel method that improves the computation time achieves a 90% speed up compared to the existing method. C++.Net environment is used to write the serial and Parallel Codes using OpenMP Library. All codes are tested on the same machine. We use the Intel Pentium machine to implement the algorithm. The specification of the Intel Pentium is: Dual-Core T4500 Processor (2.30 GHz, 1 MB L2 cache).
  • Publication info: International Arab Journal of Information Technology
  • paper link
• Egils Avots
  • Title: Audio based emotion recognition in an uncontrolled environment
  • Abstract: The presented research focuses on voice based emotion recognition. At current stage tests are performed to compare the prediction accuracy between humans and most recent vocal emotion recognition methods, which are based on various feature selection and recognition using neural networks, deep learning, GMM, SVM, random forest and other machine learning algorithms. The study will focus on the six basic emotions and natural expression. Furthermore, we will propose our own method for vocal emotion recognition based on pitch, intensity, bandwidths, mean autocorrelation, mean noise-to-harmonics ratio and standard deviation to recognize the emotional state of a speaker. The mentioned features are used in conjunction with learning algorithms, such as SVM and CNN, to predict the emotion of the speaker. All tests will be carried out using Acted Facial Expressions In The Wild (AFEW) database.
  • Publication info: N/A
• 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
  • Title: Parameterized Algorithms for Partitioning Graphs into Highly Connected Clusters
  • Abstract: Clustering is a well-known and important problem with numerous applications. The graph-based model is one of the typical cluster models. In the graph model, clusters are generally defined as cliques. However, such an approach might be too restrictive as in some applications, not all objects from the same cluster must be connected. That is why different types of cliques relaxations often considered as clusters. In our work, we consider a problem of partitioning graph into clusters and a problem of isolating cluster of a special type whereby cluster we mean highly connected subgraph. Initially, such clusterization was proposed by Hartuv and Shamir. And their HCS clustering algorithm was extensively applied in practice. It was used to cluster cDNA fingerprints, to find complexes in protein-protein interaction data, to group protein sequences hierarchically into superfamily and family clusters, to find families of regulatory RNA structures. The HCS algorithm partitions graph in highly connected subgraphs. However, it is achieved by deletion of not necessarily the minimum number of edges. In our work, we try to minimize the number of edge deletions. We consider problems from the parameterized point of view where the main parameter is a number of allowed edge deletions.
  • Link to paper https://arxiv.org/abs/1706.09487 the work was presented at MFCS 2017 (http://mfcs2017.cs.aau.dk/)
• 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: An encryption scheme is called indistinguishable under chosen plaintext attacks (short IND-CPA), if an attacker cannot distinguish the encryptions of two messages of his choice. Alternatively there are other variants of this definition, that all turn out to be equivalent in the classical case. However in the case of a quantum attacker many of these variants are not equivalent. We give an overview of these different variants of quantum IND-CPA for the special case of symmetric encryption schemes, and prove various equivalences, implications, non-equivalence and non implications between these variants. Implications are proven by reduction and non-implications are proven by given a separating example of an encryption scheme, and proving that it is secure with respect to one definition, but not with respect to the other.
  • Publication info: not published yet
• Maksims Dimitrijevs
  • Title: Uncountable Classical and Quantum Complexity Classes
  • Abstract: Polynomial-time constant-space quantum Turing machines (QTMs) and logarithmic-space probabilistic Turing machines (PTMs) recognize uncountably many languages with bounded error (Say and Yakaryilmaz 2014, arXiv:1411.7647). In this paper, we investigate more restricted cases for both models to recognize uncountably many languages with bounded error. We show that double logarithmic space is enough for PTMs on unary languages in sweeping reading mode or logarithmic space for one-way head. On unary languages, for quantum models, we obtain middle logarithmic space for counter machines. For binary languages, arbitrary small non-constant space is enough for PTMs even using only counter as memory. For counter machines, when restricted to polynomial time, we can obtain the same result for linear space. For constant-space QTMs, we follow the result for a restricted sweeping head, known as restarting realtime
  • Joint work with Abuzer Yakaryilmaz
• 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
  • Title: Satisfiable Tseitin formulas are hard for nondeterministic read-once branching programs
  • Abstract: N/A
  • Joint work with Dmitry Itsykson
  • Publication info: MFCS 2017
  • Link
• 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
  • Title: Delegatable and error-tolerant algorithms
  • Abstract: Is it possible to delegate a computation to an unreliable and more powerful counterparty? Can we design algorithms in such a way that not only can their execution be delegated, but a controlled number of adversarial errors can take place during the execution and yet one can recover the desired result? This talk will review theory and engineering efforts to bring such algorithm designs to the computing practice, including some of our recent work.
  • Publication info: ALENEX 2018
• Kamil Khadiev
  • Title: Quantum versus Classical Online Algorithms with Advice and Restricted Memory
  • Abstract: In this paper, we consider online algorithms. Typically the model is investigated with respect to competitive ratio. We consider algorithms with restricted memory (space) and explore their power. We focus on quantum and classical online algorithms. We show that there are problems that can be better solved by quantum algorithms than classical ones in a case of logarithmic memory. Additionally, we show that quantum algorithm has an advantage, even if deterministic algorithm gets advice bits. We propose ``Black Hats Method''. This method allows us to construct problems that can be effectively solved by quantum algorithms. At the same time, these problems are hard for classical algorithms. The separation between probabilistic and deterministic algorithms can be shown with a similar method.
  • joined with Aliya Khadieva, Dmitry Kravchenko and Alexander Rivosh
  • Link to the paper: Talk is based on two papers: The first one is submitted to STACS 2018 And it will be available with name "Quantum versus Classical Online Algorithms with Advice and Logarithmic Space" in arxiv. The second one is https://arxiv.org/abs/1709.08409
• 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(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
  • Title: Audio-Visual Emotion Recognition in Video Clips
  • Abstract: This paper presents a multimodal emotion recognition system, which is based on the analysis of audio and visual cues. From the audio channel, Mel-Frequency Cepstral Coefficients, Filter Bank Energies and prosodic features are extracted. For the visual part, two strategies are considered. First, facial landmarks’ geometric relations, i.e. distances and angles, are computed. Second, we summarize each emotional video into a reduced set of key-frames, which are taught to visually discriminate between the emotions. In order to do so, a convolutional neural network is applied to key-frames summarizing videos. Finally, confidence outputs of all the classifiers from all the modalities are used to define a new feature space to be learned for final emotion label prediction, in a late fusion/stacking fashion. The experiments conducted on the SAVEE, eNTERFACE’05, and RML databases show significant performance improvements by our proposed system in comparison to current alternatives, defining the current state-of-the-art in all three databases.
  • Authors: Fatemeh Noroozi, Student Member, IEEE, Marina Marjanovic, Member, IEEE, Angelina Njegus, Sergio Escalera, and Gholamreza Anbarjafari, Senior Member, IEEE
  • IEEE Transactions on Affective Computing
  • [http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=7945502&tag=1|link]]
• 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
  • Title: An Efficient Pairing-Based Shuffle Argument
  • Abstract:
    • We construct the most efficient known pairing-based NIZK shuffle argument. It consists of three subarguments that were carefully chosen to obtain optimal efficiency of the shuffle argument:
      1 A same-message argument based on the linear subspace QANIZK argument of Kiltz and Wee,
      2 A (simplified) permutation matrix argument of Fauzi, Lipmaa, and Zajac,
      3 A (simplified) consistency argument of Groth and Lu.
      We prove the knowledge-soundness of the first two subarguments in the generic bilinear group model, and the culpable soundness of the third subargument under a KerMDH assumption. This proves the soundness of the shuffle argument. We also discuss our partially optimized implementation that allows one to prove a shuffle of 100 000 ciphertexts in less than a minute and verify it in less than 1.5 minutes.
  • Publication info: Prastudy Fauzi, Helger Lipmaa, Janno Siim and Michal Zajac. An Efficient Pairing-Based Shuffle Argument. In Thomas Peyrin and Tsuyoshi Takagi, editors, ASIACRYPT 2017, volume ? of Lecture Notes in Computer Science, pages ?--?, Hong Kong, China, December 3--7, 2017. Springer, Heidelberg.
  • eprint link
• 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
  • Title: Understanding computation via computation
  • Abstract: As theoretical computer scientists, we seek to understand what can be automated, but what do we know about automating our own work? Is it possible for us to outsource our own research questions to computers?
    In this talk I will survey some of our recent success stories related to the use of computational techniques in the study of algorithms and computational complexity. My focus will be on the theory of distributed computing; the models of distributed computing appear to be particularly well-suited for computational investigations.
    I will give examples of distributed algorithms that were designed or co-designed by computers and that far outperform any previous human-designed algorithms. I will describe some meta-algorithmic techniques - how to design algorithms for designing algorithms - and we will also see an example of how to use computers to discover lower bound proofs.
  • Links to papers: PODC 2017 SIROCCO 2015 J. Comput. Syst. Sci. 2016 arxiv
• Marek Sýs
  • Title: Factorization of widely used RSA moduli
  • Abstract: Recently published algorithmic flaw in the construction of primes for RSA key generation affects millions of devices in several domains (electronic identity documents, software signing, Trusted Computing and PGP). The primes generated by the widely-used Infineon's library suffer from a significant loss of entropy. Library generates primes (and moduli) of the specific algebraic form. Keys generated by the library contain a strong fingerprint that is verifiable in microseconds on an ordinary laptop. All vulnerable keys can be quickly identified, even in very large datasets. Moreover public RSA moduli of common key sizes 1024 or 2048 bits can be practically factorized (3~CPU months resp. 100~CPU years) which allows directly to compute corresponding private keys. Our factorization method is based on the Coppersmith's attack typically used in situations when partial information (about private key or message) is known. The talk will cover an idea of the Coppersmith's attack and our heuristic search for an alternative form of the primes since the direct application of Coppersmith's attack is not feasible. Optimisation of our approach and the parameter selection will be discussed together with limitations of our method.
  • Publication info: ACM CCS 2017
  • paper link
• 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
  • Title: All Classical Adversary Methods are Equivalent for Total Functions
  • Abstract: We show that all known classical adversary lower bounds on randomized query complexity are equivalent for total functions, and are equal to the fractional block sensitivity {$ fbs(f) $}. That includes the Kolmogorov complexity bound of Laplante and Magniez and the earlier relational adversary bound of Aaronson. For partial functions, we show unbounded separations between {$ fbs(f) $} and other adversary bounds, as well as between the relational and Kolmogorov complexity bounds.
  • [https://arxiv.org/abs/1709.08985|arxiv link] (all coauthors listed there)
• 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
  • Title: Magic coins are useful for small-space quantum machines
  • Abstract: Although polynomial-time probabilistic Turing machines can utilize uncomputable transition probabilities to recognize uncountably many languages with bounded error when allowed to use double logarithmic space, it is known that such ``magic coins'' give no additional computational power to constant-space versions of those machines. We show that adding a few quantum bits to the model changes the picture dramatically. For every language {$L$}, there exists such a two-way quantum finite automaton (2qcfa) that recognizes a language of the same Turing degree as {$L$} with bounded error in polynomial time. When used as verifiers in public-coin interactive proof systems, such automata can verify membership in all languages with bounded error, outperforming their classical counterparts, which are known to fail for the palindromes language. Corollaries demonstrate even faster machines when one is allowed to use a counter as memory, and an alternative proof of the uncountability of stochastic languages.
  • arxiv link
  • A. C. Cem Say, Abuzer Yakaryilmaz: Magic coins are useful for small-space quantum machines. Quantum Information & Computation 17(11&12): 1027-1043 (2017)
• 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
  • Title: A Subversion-Resistant SNARK
  • Abstract: While succinct non-interactive zero-knowledge arguments of knowledge (zk-SNARKs) are widely studied, the question of what happens when the CRS has been subverted has received little attention. In ASIACRYPT 2016, Bellare, Fuchsbauer and Scafuro showed the first negative and positive results in this direction, proving also that it is impossible to achieve subversion soundness and (even non-subversion) zero knowledge at the same time. On the positive side, they constructed an involved sound and subversion zero-knowledge argument system for NP. We show that Groth's zk-SNARK for Circuit-SAT from EUROCRYPT 2016 can be made computationally knowledge-sound and perfectly composable Sub-ZK with minimal changes. We just require the CRS trapdoor to be extractable and the CRS to be publicly verifiable. To achieve the latter, we add some new elements to the CRS and construct an efficient CRS verification algorithm. We also provide a definitional framework for sound and Sub-ZK SNARKs and describe implementation results of the new Sub-ZK SNARK.
  • Publication info:
    • Behzad Abdolmaleki, Karim Baghery, Helger Lipmaa and Michal Zajac. A Subversion-Resistant SNARK. In Thomas Peyrin and Tsuyoshi Takagi, editors, ASIACRYPT 2017, volume ? of Lecture Notes in Computer Science, pages ?--?, Hong Kong, China, December 3--7, 2017. Springer, Heidelberg.
  • eprint link
• 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