Browse ORBi

- What it is and what it isn't
- Green Road / Gold Road?
- Ready to Publish. Now What?
- How can I support the OA movement?
- Where can I learn more?

ORBi

Coercion-Resistant Voting in Linear Time via Fully Homomorphic Encryption: Towards a Quantum-Safe Scheme Roenne, Peter ; Atashpendar, Arash ; et al in Financial Cryptography and Data Security 2019. FC 2019: International Workshops, CIW, VOTING, and WTSC (2020) We present an approach for performing the tallying work in the coercion-resistant JCJ voting protocol, introduced by Juels, Catalano, and Jakobsson, in linear time using fully homomorphic encryption (FHE ... [more ▼] We present an approach for performing the tallying work in the coercion-resistant JCJ voting protocol, introduced by Juels, Catalano, and Jakobsson, in linear time using fully homomorphic encryption (FHE). The suggested enhancement also paves the path towards making JCJ quantum-resistant, while leaving the underlying structure of JCJ intact. The pairwise comparison-based approach of JCJ using plaintext equivalence tests leads to a quadratic blow-up in the number of votes, which makes the tallying process rather impractical in realistic settings with a large number of voters. We show how the removal of invalid votes can be done in linear time via a solution based on recent advances in various FHE primitives such as hashing, zero-knowledge proofs of correct decryption, verifiable shuffles and threshold FHE. We conclude by touching upon some of the advantages and challenges of such an approach, followed by a discussion of further security and post-quantum considerations. [less ▲] Detailed reference viewed: 369 (81 UL)From Information Theory Puzzles in Deletion Channels to Deniability in Quantum Cryptography Atashpendar, Arash Doctoral thesis (2019) Research questions, originally rooted in quantum key exchange (QKE), have branched off into independent lines of inquiry ranging from information theory to fundamental physics. In a similar vein, the ... [more ▼] Research questions, originally rooted in quantum key exchange (QKE), have branched off into independent lines of inquiry ranging from information theory to fundamental physics. In a similar vein, the first part of this thesis is dedicated to information theory problems in deletion channels that arose in the context of QKE. From the output produced by a memoryless deletion channel with a uniformly random input of known length n, one obtains a posterior distribution on the channel input. The difference between the Shannon entropy of this distribution and that of the uniform prior measures the amount of information about the channel input which is conveyed by the output of length m. We first conjecture on the basis of experimental data that the entropy of the posterior is minimized by the constant strings 000..., 111... and maximized by the alternating strings 0101..., 1010.... Among other things, we derive analytic expressions for minimal entropy and propose alternative approaches for tackling the entropy extremization problem. We address a series of closely related combinatorial problems involving binary (sub/super)-sequences and prove the original minimal entropy conjecture for the special cases of single and double deletions using clustering techniques and a run-length encoding of strings. The entropy analysis culminates in a fundamental characterization of the extremal entropic cases in terms of the distribution of embeddings. We confirm the minimization conjecture in the asymptotic limit using results from hidden word statistics by showing how the analytic-combinatorial methods of Flajolet, Szpankowski and Vallée, relying on generating functions, can be applied to resolve the case of fixed output length and n → ∞. In the second part, we revisit the notion of deniability in QKE, a topic that remains largely unexplored. In a work by Donald Beaver it is argued that QKE protocols are not necessarily deniable due to an eavesdropping attack that limits key equivocation. We provide more insight into the nature of this attack and discuss how it extends to other prepare-and-measure QKE schemes such as QKE obtained from uncloneable encryption. We adopt the framework for quantum authenticated key exchange developed by Mosca et al. and extend it to introduce the notion of coercer-deniable QKE, formalized in terms of the indistinguishability of real and fake coercer views. We also elaborate on the differences between our model and the standard simulation-based definition of deniable key exchange in the classical setting. We establish a connection between the concept of covert communication and deniability by applying results from a work by Arrazola and Scarani on obtaining covert quantum communication and covert QKE to propose a simple construction for coercer-deniable QKE. We prove the deniability of this scheme via a reduction to the security of covert QKE. We relate deniability to fundamental concepts in quantum information theory and suggest a generic approach based on entanglement distillation for achieving information-theoretic deniability, followed by an analysis of other closely related results such as the relation between the impossibility of unconditionally secure quantum bit commitment and deniability. Finally, we present an efficient coercion-resistant and quantum-secure voting scheme, based on fully homomorphic encryption (FHE) and recent advances in various FHE primitives such as hashing, zero-knowledge proofs of correct decryption, verifiable shuffles and threshold FHE. [less ▲] Detailed reference viewed: 489 (130 UL)Revisiting Deniability in Quantum Key Exchange via Covert Communication and Entanglement Distillation Atashpendar, Arash ; ; Roenne, Peter et al in Secure IT Systems, 23rd Nordic Conference, NordSec 2018. Lecture Notes in Computer Science, vol 11252. Springer, Cham (2018, November 02) We revisit the notion of deniability in quantum key exchange (QKE), a topic that remains largely unexplored. In the only work on this subject by Donald Beaver, it is argued that QKE is not necessarily ... [more ▼] We revisit the notion of deniability in quantum key exchange (QKE), a topic that remains largely unexplored. In the only work on this subject by Donald Beaver, it is argued that QKE is not necessarily deniable due to an eavesdropping attack that limits key equivocation. We provide more insight into the nature of this attack and how it extends to other constructions such as QKE obtained from uncloneable encryption. We then adopt the framework for quantum authenticated key exchange, developed by Mosca et al., and extend it to introduce the notion of coercer-deniable QKE, formalized in terms of the indistinguishability of real and fake coercer views. Next, we apply results from a recent work by Arrazola and Scarani on covert quantum communication to establish a connection between covert QKE and deniability. We propose DC-QKE, a simple deniable covert QKE protocol, and prove its deniability via a reduction to the security of covert QKE. Finally, we consider how entanglement distillation can be used to enable information-theoretically deniable protocols for QKE and tasks beyond key exchange. [less ▲] Detailed reference viewed: 238 (56 UL)A Proof of Entropy Minimization for Outputs in Deletion Channels via Hidden Word Statistics Atashpendar, Arash ; Mestel, David ; et al E-print/Working paper (2018) From the output produced by a memoryless deletion channel from a uniformly random input of known length n, one obtains a posterior distribution on the channel input. The difference between the Shannon ... [more ▼] From the output produced by a memoryless deletion channel from a uniformly random input of known length n, one obtains a posterior distribution on the channel input. The difference between the Shannon entropy of this distribution and that of the uniform prior measures the amount of information about the channel input which is conveyed by the output of length m, and it is natural to ask for which outputs this is extremized. This question was posed in a previous work, where it was conjectured on the basis of experimental data that the entropy of the posterior is minimized and maximized by the constant strings 𝟶𝟶𝟶… and 𝟷𝟷𝟷… and the alternating strings 𝟶𝟷𝟶𝟷… and 𝟷𝟶𝟷𝟶… respectively. In the present work we confirm the minimization conjecture in the asymptotic limit using results from hidden word statistics. We show how the analytic-combinatorial methods of Flajolet, Szpankowski and Vall\'ee for dealing with the hidden pattern matching problem can be applied to resolve the case of fixed output length and n→∞, by obtaining estimates for the entropy in terms of the moments of the posterior distribution and establishing its minimization via a measure of autocorrelation. [less ▲] Detailed reference viewed: 191 (45 UL)From Clustering Supersequences to Entropy Minimizing Subsequences for Single and Double Deletions Atashpendar, Arash ; ; et al E-print/Working paper (2018) A binary string transmitted via a memoryless i.i.d. deletion channel is received as a subsequence of the original input. From this, one obtains a posterior distribution on the channel input, corresponding ... [more ▼] A binary string transmitted via a memoryless i.i.d. deletion channel is received as a subsequence of the original input. From this, one obtains a posterior distribution on the channel input, corresponding to a set of candidate supersequences weighted by the number of times the received subsequence can be embedded in them. In a previous work it is conjectured on the basis of experimental data that the entropy of the posterior is minimized and maximized by the constant and the alternating strings, respectively. In this work, in addition to revisiting the entropy minimization conjecture, we also address several related combinatorial problems. We present an algorithm for counting the number of subsequence embeddings using a run-length encoding of strings. We then describe methods for clustering the space of supersequences such that the cardinality of the resulting sets depends only on the length of the received subsequence and its Hamming weight, but not its exact form. Then, we consider supersequences that contain a single embedding of a fixed subsequence, referred to as singletons, and provide a closed form expression for enumerating them using the same run-length encoding. We prove an analogous result for the minimization and maximization of the number of singletons, by the alternating and the uniform strings, respectively. Next, we prove the original minimal entropy conjecture for the special cases of single and double deletions using similar clustering techniques and the same run-length encoding, which allow us to characterize the distribution of the number of subsequence embeddings in the space of compatible supersequences to demonstrate the effect of an entropy decreasing operation. [less ▲] Detailed reference viewed: 171 (42 UL)Deniability in Quantum Cryptography Atashpendar, Arash ; Roenne, Peter ; Ostrev, Dimiter et al Poster (2017, June 14) This poster describes ongoing work on deniability in quantum cryptography, an area of research that remains almost entirely unexplored in the quantum information processing literature. Deniability is a ... [more ▼] This poster describes ongoing work on deniability in quantum cryptography, an area of research that remains almost entirely unexplored in the quantum information processing literature. Deniability is a well-known and fundamental concept in classical cryptography and it can be defined as the ability for the sender of a message to deny the contents of a message or the very act of having participated in an exchange, e.g. having sent the said message. We discuss deniability in the context of quantum key exchange and address a particular problem, first discovered by Donald Beaver, where he claims that all QKD protocols are undeniable. The claim is that while we do get a one-time pad (OTP) using QKD, it does not provide the property of key equivocation as it is expected in the Shannon sense for a OTP. Intuitively, this difficulty lies in the quantum channel alone and it has to do with the fact that in QKD, while we generate entropy by expanding an initially short pre-shared key into an arbitrary longer secret key, we do so by exchanging information over a quantum as well as a classical channel, which could potentially leave a binding transcript of Alice's decisions to the final secret key. This is in contrast with the implicit assumption that Eve knows nothing about how two given parties have established their shared OTP in the first place. We discuss the importance of deniability in cryptography and its wide range of applications, along with cryptographic primitives other than key exchange where deniability might be a desired property. Finally, we present a series of fundamental open questions in this area of research and discuss quantum cryptographic primitives that lend themselves to devising deniable protocols. [less ▲] Detailed reference viewed: 309 (25 UL)A Scalable Parallel Cooperative Coevolutionary PSO Algorithm for Multi-objective Optimization Atashpendar, Arash ; ; Danoy, Grégoire et al in Journal of Parallel and Distributed Computing (2017) We present a parallel multi-objective cooperative coevolutionary variant of the Speed-constrained Multi-objective Particle Swarm Optimization (SMPSO) algorithm. The algorithm, called CCSMPSO, is the first ... [more ▼] We present a parallel multi-objective cooperative coevolutionary variant of the Speed-constrained Multi-objective Particle Swarm Optimization (SMPSO) algorithm. The algorithm, called CCSMPSO, is the first multi-objective cooperative coevolutionary algorithm based on PSO in the literature. SMPSO adopts a strategy for limiting the velocity of the particles that prevents them from having erratic movements. This characteristic provides the algorithm with a high degree of reliability. In order to demonstrate the effectiveness of CCSMPSO, we compare our work with the original SMPSO and three different state-of-the-art multi-objective CC metaheuristics, namely CCNSGA-II, CCSPEA2 and CCMOCell, along with their original sequential counterparts. Our experiments indicate that our proposed solution, CCSMPSO, offers significant computational speedups, a higher convergence speed and better or comparable results in terms of solution quality, when evaluated against three other CC algorithms and four state-of-the-art optimizers (namely SMPSO, NSGA-II, SPEA2, and MOCell), respectively. We then provide a scalability analysis, which consists of two studies. First, we analyze how the algorithms scale when varying the problem size, i.e., the number of variables. Second, we analyze their scalability in terms of parallelization, i.e., the impact of using more computational cores on the quality of solutions and on the execution time of the algorithms. Three different criteria are used for making the comparisons, namely the quality of the resulting approximation sets, average computational time and the convergence speed to the Pareto front. [less ▲] Detailed reference viewed: 317 (52 UL)A Parallel Cooperative Coevolutionary SMPSO Algorithm for Multi-objective Optimization Atashpendar, Arash ; ; Danoy, Grégoire et al in IEEE International Conference on High Performance Computing Simulation (HPCS) (2016, July) Detailed reference viewed: 290 (46 UL)Information Leakage due to Revealing Randomly Selected Bits Atashpendar, Arash ; ; Ryan, Peter in Security Protocols XXIII: Lecture Notes in Computer Science, Volume 9379, 2015 (2015, November 25) This note describes an information theory problem that arose from some analysis of quantum key distribution protocols. The problem seems very natural and is very easy to state but has not to our knowledge ... [more ▼] This note describes an information theory problem that arose from some analysis of quantum key distribution protocols. The problem seems very natural and is very easy to state but has not to our knowledge been addressed before in the information theory literature: suppose that we have a random bit string y of length n and we reveal k bits at random positions, preserving the order but without revealing the positions, how much information about y is revealed? We show that while the cardinality of the set of compatible y strings depends only on n and k, the amount of leakage does depend on the exact revealed x string. We observe that the maximal leakage, measured as decrease in the Shannon entropy of the space of possible bit strings corresponds to the x string being all zeros or all ones and that the minimum leakage corresponds to the alternating x strings. We derive a formula for the maximum leakage (minimal entropy) in terms of n and k. We discuss the relevance of other measures of information, in particular min-entropy, in a cryptographic context. Finally, we describe a simulation tool to explore these results. [less ▲] Detailed reference viewed: 490 (67 UL)VizBin - an application for reference-independent visualization and human-augmented binning of metagenomic data Laczny, Cedric Christian ; ; Plugaru, Valentin et al in Microbiome (2015) Background Metagenomics is limited in its ability to link distinct microbial populations to genetic potential due to a current lack of representative isolate genome sequences. Reference-independent ... [more ▼] Background Metagenomics is limited in its ability to link distinct microbial populations to genetic potential due to a current lack of representative isolate genome sequences. Reference-independent approaches, which exploit for example inherent genomic signatures for the clustering of metagenomic fragments (binning), offer the prospect to resolve and reconstruct population-level genomic complements without the need for prior knowledge. Results We present VizBin, a Java™-based application which offers efficient and intuitive reference-independent visualization of metagenomic datasets from single samples for subsequent human-in-the-loop inspection and binning. The method is based on nonlinear dimension reduction of genomic signatures and exploits the superior pattern recognition capabilities of the human eye-brain system for cluster identification and delineation. We demonstrate the general applicability of VizBin for the analysis of metagenomic sequence data by presenting results from two cellulolytic microbial communities and one human-borne microbial consortium. The superior performance of our application compared to other analogous metagenomic visualization and binning methods is also presented. Conclusions VizBin can be applied de novo for the visualization and subsequent binning of metagenomic datasets from single samples, and it can be used for the post hoc inspection and refinement of automatically generated bins. Due to its computational efficiency, it can be run on common desktop machines and enables the analysis of complex metagenomic datasets in a matter of minutes. The software implementation is available at https://claczny.github.io/VizBin under the BSD License (four-clause) and runs under Microsoft Windows™, Apple Mac OS X™ (10.7 to 10.10), and Linux. [less ▲] Detailed reference viewed: 428 (30 UL)BinSeqPy Atashpendar, Arash Software (2014) BinSeqPy is a library for the Python programming language, aimed at performing experiments and analyses of combinatorial structures dealing with binary (sub/super)-sequences. It provides an array of low ... [more ▼] BinSeqPy is a library for the Python programming language, aimed at performing experiments and analyses of combinatorial structures dealing with binary (sub/super)-sequences. It provides an array of low-level as well as high-level mathematical functions for addressing a variety of information theory and combinatorial problems involving binary subsequences and their embeddings in supersequences. These range from bitstring transformations, information entropy analysis routines, plotting functions and algorithms related to subsequence embeddings to functions dedicated to hidden word statistics. [less ▲] Detailed reference viewed: 104 (21 UL)QKD Simulator Atashpendar, Arash Software (2014) QKD simulator © is a web application aimed at simulating and analyzing Quantum Key Distribution protocols. The online simulator is powered by the QKD Simulation Toolkit, which has been designed and ... [more ▼] QKD simulator © is a web application aimed at simulating and analyzing Quantum Key Distribution protocols. The online simulator is powered by the QKD Simulation Toolkit, which has been designed and implemented to support customizing a wide range of parameters for individual components and sub-protocols, e.g., the quantum channel, sifting, error estimation, information reconciliation and privacy amplification. Each simulation run provides detailed information about the intermediate and final stages of the protocol. [less ▲] Detailed reference viewed: 266 (24 UL)A Native Approach to Semantics and Inference in Fine-Grained Documents Atashpendar, Arash ; Kirsch, Laurent ; Botev, Jean et al in Proceedings of the 2nd Joint International Semantic Technology Conference (JIST) (2012) Detailed reference viewed: 294 (57 UL)Deniable Public-Key Authenticated Quantum Key Exchange van Wier, Jeroen ; Atashpendar, Arash ; Roenne, Peter E-print/Working paper (n.d.) In this work, we explore the notion of deniability in public-key authenticated quantum key exchange (QKE), which allows two parties to establish a shared secret key without leaving any evidence that would ... [more ▼] In this work, we explore the notion of deniability in public-key authenticated quantum key exchange (QKE), which allows two parties to establish a shared secret key without leaving any evidence that would bind a session to either party. The deniability property is expressed in terms of being able to simulate the transcripts of a protocol. The ability to deny a message or an action has applications ranging from secure messaging to secure e-voting and whistle-blowing. While quite well-established in classical cryptography, it remains largely unexplored in the quantum setting. Here, we first present a natural extension of classical definitions in the simulation paradigm to the setting of quantum computation and formalize the requirements for a deniable QKE scheme. We then prove that the BB84 variant of QKE, when authenticated using a strong designated verifier signature scheme, satisfies deniability and, finally, propose a concrete instantiation. [less ▲] Detailed reference viewed: 29 (4 UL) |
||