Recent zbMATH articles in MSC 68Phttps://zbmath.org/atom/cc/68P2022-07-25T18:03:43.254055ZUnknown authorWerkzeugSignatures of extremal 2-unifrom hypergraphshttps://zbmath.org/1487.051872022-07-25T18:03:43.254055Z"Goltsova, T. Yu."https://zbmath.org/authors/?q=ai:goltsova.t-yu"Egorova, E. K."https://zbmath.org/authors/?q=ai:egorova.e-k"Mokryakov, A. V."https://zbmath.org/authors/?q=ai:mokryakov.a-v"Tsurkov, V. I."https://zbmath.org/authors/?q=ai:tsurkov.vladimir-i(no abstract)Using elastic net restricted kernel canonical correlation analysis for cross-language information retrievalhttps://zbmath.org/1487.620642022-07-25T18:03:43.254055Z"Polajnar, Emil"https://zbmath.org/authors/?q=ai:polajnar.emilSummary: Kernel methods, which are a non-linear variant of linear methods, are used to increase the flexibility and allow to examine non-linear relationships by linear methods. The conventional solution of the restricted kernel canonical correlation analysis problem has a major drawback, it solves the problem in a reasonable time frame only for problems with few variables. We successfully overcame this limitation by implementing the method with the alternating least-squares algorithm. This allowed us to apply the method to cross-language information retrieval problem on a big dataset. We compared the results to other established methods and they were encouraging.Preface to special issue for DCC 2020https://zbmath.org/1487.680112022-07-25T18:03:43.254055ZFrom the text: This is the fourth special issue on compact data structures and computation over compressed data resulting from special sessions at the IEEE Data Compression Conference (DCC).Information and communications security. 23rd international conference, ICICS 2021, Chongqing, China, November 19--21, 2021. Proceedings. Part Ihttps://zbmath.org/1487.680122022-07-25T18:03:43.254055ZThe articles of mathematical interest will be reviewed individually. For the preceding conference see [Zbl 07353247]. For Part II of the proceedings of the present conference see [Zbl 1487.68013].Information and communications security. 23rd international conference, ICICS 2021, Chongqing, China, November 19--21, 2021. Proceedings. Part IIhttps://zbmath.org/1487.680132022-07-25T18:03:43.254055ZThe articles of mathematical interest will be reviewed individually. For the preceding conference see [Zbl 07353247]. For Part I of the proceedings of the present conference see [Zbl 1487.68012].String processing and information retrieval. 28th international symposium, SPIRE 2021, Lille, France, October 4--6, 2021. Proceedingshttps://zbmath.org/1487.680182022-07-25T18:03:43.254055ZThe articles of mathematical interest will be reviewed individually. For the preceding symposium see [Zbl 07294409].An efficient and batch verifiable conditional privacy-preserving authentication scheme for VANETs using latticehttps://zbmath.org/1487.680252022-07-25T18:03:43.254055Z"Mukherjee, Sankar"https://zbmath.org/authors/?q=ai:mukherjee.sankar"Gupta, Daya Sagar"https://zbmath.org/authors/?q=ai:gupta.daya-sagar"Biswas, G. P."https://zbmath.org/authors/?q=ai:biswas.g-pSummary: With the rapid increase in the internet technologies, Vehicular Ad hoc Networks (VANETs) are identified as a crucial primitive for the vehicular communication in which the moving vehicles are treated as nodes to form a mobile network. To ameliorate the efficiency and traffic security of the communication, a VANET can wirelessly circulate the traffic information and status to the participating vehicles (nodes). Before deploying a VANET, a security and privacy mechanism must be implemented to assure the secure communication. Due to this issue, a number of conditional privacy-preserving authentication schemes are proposed in the literature to guarantee the mutual authentication and privacy protection. However, most of these schemes use the Diffie-Hellman (DH) problems to secure the communication. Note that, these DH-type problems can be solved in polynomial-time in the presence of new modern technologies like quantum computers. Therefore, to remove these difficulties, we motivated to attempt a non-DH type conditional privacy-preserving authentication scheme which can resist the quantum computers. In this paper, we developed the first lattice-based conditional privacy-preserving authentication (LB-CPPA) protocol for VANETs. A random oracle model is used to analyze the security of proposed protocol. The security of our LB-CPPA scheme is based on the complexity of lattice problems. By security analysis, we show that our proposal endorses the message integrity and authentication as well as the privacy preservation at the same time. A security comparison of our claim is also done. Further, we analyze the performance of the proposed scheme and compare it with the DH-type schemes.Lower bounds on the amortized time complexity of shared objectshttps://zbmath.org/1487.680282022-07-25T18:03:43.254055Z"Attiya, Hagit"https://zbmath.org/authors/?q=ai:attiya.hagit"Fouren, Arie"https://zbmath.org/authors/?q=ai:fouren.arieSummary: The amortized step complexity of an implementation measures its performance as a whole, rather than the performance of individual operations. Specifically, the amortized step complexity of an implementation is the average number of steps performed by invoked operations, in the worst case, taken over all possible executions. The amortized step complexity of a wide range of known lock-free implementations for shared data structures, like stacks, queues, linked lists, doubly-linked lists and binary trees, includes an additive factor linear in the point contention -- the number of processes simultaneously active in the execution.
This paper shows that an additive factor, linear in the point contention, is inherent in the amortized step complexity for lock-free implementations of many distributed data structures, including stacks, queues, heaps, linked lists and search trees.
For the entire collection see [Zbl 1387.68011].Treasure hunt with barely communicating agentshttps://zbmath.org/1487.680422022-07-25T18:03:43.254055Z"Dobrev, Stefan"https://zbmath.org/authors/?q=ai:dobrev.stefan"Královič, Rastislav"https://zbmath.org/authors/?q=ai:kralovic.rastislav"Pardubská, Dana"https://zbmath.org/authors/?q=ai:pardubska.danaSummary: We consider the problem of fault-tolerant parallel exhaustive search, a.k.a. ``Treasure Hunt'', introduced by \textit{P. Fraigniaud} et al. [in: Proceedings of the 48th annual ACM SIGACT symposium on theory of computing, STOC '16. New York, NY: Association for Computing Machinery (ACM). 312--323 (2016; Zbl 1373.68202)]: Imagine an infinite list of ``boxes'', one of which contains a ``treasure''. The ordering of the boxes reflects the importance of finding the treasure in a given box. There are \(k\) agents, whose goal is to locate the treasure in the least amount of time. The system is synchronous; at every step, an agent can ``open'' a box and see whether the treasure is there. The hunt finishes when the first agent locates the treasure.
The original paper [loc. cit.] considers non-cooperating randomized agents, out of which at most \(f\) can fail, with the failure pattern determined by an adversary. In this paper, we consider deterministic agents and investigate two failure models: The failing-agents model from [loc. cit.] and a black hole model: At most \(f\) boxes contain ``black holes'', placed by the adversary. When an agent opens a box containing a black hole, the agent disappears without an observable trace.
The crucial distinction, however, is that we consider ``barely communicating'' or ``indirectly weakly communicating'' agents: When an agent opens a box, it can tell whether the box has been previously opened. There are no other means of direct or indirect communication between the agents.
We show that adding even such weak means of communication has very strong impact on the solvability and complexity of the Treasure Hunt problem. In particular, in the failing agents model it allows the agents to be 1-competitive w.r.t. an optimal algorithm which does not know the location of the treasure, but is instantly notified of agent failures. In the black holes model (where there is no deterministic solution for non-communicating agents even in the presence of a single black hole) we show a lower bound of \(2f+1\) and an upper bound of \(4f+1\) for the number of agents needed to solve Treasure Hunt in presence of up to \(f\) black holes, as well as partial results about the hunt time in the presence of few black holes.
For the entire collection see [Zbl 1387.68011].Efficient oracles and routing schemes for replacement pathshttps://zbmath.org/1487.680512022-07-25T18:03:43.254055Z"Bilò, Davide"https://zbmath.org/authors/?q=ai:bilo.davide"Choudhary, Keerti"https://zbmath.org/authors/?q=ai:choudhary.keerti"Gualà, Luciano"https://zbmath.org/authors/?q=ai:guala.luciano"Leucci, Stefano"https://zbmath.org/authors/?q=ai:leucci.stefano"Parter, Merav"https://zbmath.org/authors/?q=ai:parter.merav"Proietti, Guido"https://zbmath.org/authors/?q=ai:proietti.guidoSummary: Real life graphs and networks are prone to failure of nodes (vertices) and links (edges). In particular, for a pair of nodes \(s\) and \(t\) and a failing edge \(e\) in an \(n\)-vertex unweighted graph \(G=(V(G),E(G))\), the replacement path \(\pi_{G-e}(s,t)\) is a shortest \(s-t\) path that avoids \(e\). In this paper we present several efficient constructions that, for every \((s,t)\in S\times T\), where \(S,T\subseteq V(G)\), and every \(e\in E(G)\), maintain the collection of all \(\pi_{G-e}(s,t)\), either implicitly (i.e., through compact data structures a.k.a. distance sensitivity oracles (DSO)), or explicitly (i.e., through sparse subgraphs a.k.a. fault-tolerant preservers (FTP)). More precisely, we provide the following results:
\begin{itemize}
\item[(1)] DSO: For every \(S,T\subseteq V(G)\), we construct a DSO for maintaining \(S\times T\) distances under single edge (or vertex) faults. This DSO has size \(\tilde{O}(n\sqrt{|S||T|})\) and query time of \(O(\sqrt{|S||T|})\). At the expense of having quasi-polynomial query time, the size of the oracle can be improved to \(\tilde{O}(n|S|+|T|\sqrt{|S|n})\), which is optimal for \(|T|=\Omega(\sqrt{n|S|})\). When \(|T|=\Omega(n^\frac{3}{4} |S|^\frac{1}{4})\), the construction can be further refined in order to get a polynomial query time. We also consider the approximate additive setting, and show a family of DSOs that exhibits a tradeoff between the additive stretch and the size of the oracle. Finally, for the meaningful single-source case, the above result is complemented by a lower bound conditioned on the Set-Intersection conjecture. This lower bound establishes a separation between the oracle and the subgraph settings.
\item[(2)] FTP: We show the construction of a path-reporting DSO of size \(\tilde{O}(n^{4/3}(|S||T|)^{1/3})\) reporting \(\pi_{G-e}(s,t)\) in \(O(|\pi_{G-e}(s,t)|+(n|S||T|)^{1/3})\) time. Such a DSO can be transformed into a FTP having the same size, and moreover it can be elaborated in order to make it optimal (up to a poly-logarithmic factor) both in space and query time for the special case in which \(T=V(G)\). Our FTP improves over previous constructions when \(|T|=O(\sqrt{|S|n})\) (up to inverse poly-logarithmic factors).
\item[(3)] Routing and Labeling Schemes: For the well-studied single-source setting, we present a novel routing scheme, that allows to route messages on \(\pi_{G-e}(s,t)\) by using edge labels and routing tables of size \(\tilde{O}(\sqrt{n})\), and a header message of poly-logarithmic size. We also present a labeling scheme for the setting which is optimal in space up to constant factors.
\end{itemize}
For the entire collection see [Zbl 1381.68010].Security notions for disk encryptionhttps://zbmath.org/1487.680612022-07-25T18:03:43.254055Z"Gjøsteen, Kristian"https://zbmath.org/authors/?q=ai:gjosteen.kristianSummary: We define security goals and attack models for disk encryption, and prove several results for the resulting security notions, as well as some relationships. We give concrete constructions for every security notion along with security proofs. We briefly discuss the security of some implementations and standards for disk encryption.
For the entire collection see [Zbl 1481.68012].Towards an information-theoretic framework for analyzing intrusion detection systemshttps://zbmath.org/1487.680622022-07-25T18:03:43.254055Z"Gu, Guofei"https://zbmath.org/authors/?q=ai:gu.guofei"Fogla, Prahlad"https://zbmath.org/authors/?q=ai:fogla.prahlad"Dagon, David"https://zbmath.org/authors/?q=ai:dagon.david"Lee, Wenke"https://zbmath.org/authors/?q=ai:lee.wenke"Skoric, Boris"https://zbmath.org/authors/?q=ai:skoric.borisSummary: IDS research still needs to strengthen mathematical foundations and theoretic guidelines. In this paper, we build a formal framework, based on information theory, for analyzing and quantifying the effectiveness of an IDS. We firstly present a formal IDS model, then analyze it following an information-theoretic approach. Thus, we propose a set of information-theoretic metrics that can quantitatively measure the effectiveness of an IDS in terms of feature representation capability, classification information loss, and overall intrusion detection capability. We establish a link to relate these metrics, and prove a fundamental upper bound on the intrusion detection capability of an IDS. Our framework is a \textit{practical} theory which is data trace driven and evaluation oriented in this area. In addition to grounding IDS research on a mathematical theory for formal study, this framework provides practical guidelines for IDS fine-tuning, evaluation and design, that is, the provided set of metrics greatly facilitates a static/dynamic fine-tuning of an IDS to achieve optimal operation and a fine-grained means to evaluate IDS performance and improve IDS design. We conduct experiments to demonstrate the utility of our framework in practice.
For the entire collection see [Zbl 1481.68014].A formalization of anonymity and onion routinghttps://zbmath.org/1487.680722022-07-25T18:03:43.254055Z"Mauw, S."https://zbmath.org/authors/?q=ai:mauw.sjouke"Verschuren, J. H. S."https://zbmath.org/authors/?q=ai:verschuren.j-h-s"de Vink, E. P."https://zbmath.org/authors/?q=ai:de-vink.erik-pSummary: The use of formal methods to verify security protocols with respect to secrecy and authentication has become standard practice. In contrast, the formalization of other security goals, such as privacy, has received less attention. Due to the increasing importance of privacy in the current society, formal methods will also become indispensable in this area. Therefore, we propose a formal definition of the notion of anonymity in presence of an observing intruder. We validate this definition by analyzing a well-known anonymity preserving protocol, viz. onion routing.
For the entire collection see [Zbl 1481.68022].Faster repetition-aware compressed suffix trees based on block treeshttps://zbmath.org/1487.680822022-07-25T18:03:43.254055Z"Cáceres, Manuel"https://zbmath.org/authors/?q=ai:caceres.manuel-osvaldo"Navarro, Gonzalo"https://zbmath.org/authors/?q=ai:navarro.gonzaloSummary: The suffix tree is a fundamental data structure in stringology, but its space usage, though linear, is an important problem in applications like Bioinformatics. We design and implement a new \textit{compressed suffix tree (CST)} targeted to highly repetitive texts, such as large genomic collections of the same species. Our first contribution is to enhance the Block Tree, a data structure that captures the repetitiveness of its input sequence, to represent the topology of trees with large repeated subtrees. Our so-called Block-Tree Compressed Topology (BT-CT) data structure augments the Block Tree nodes with data that speeds up tree navigation. Our Block-Tree CST (BT-CST), in turn, uses the BT-CT to compress the topology of the suffix tree, and also replaces the sampling of the suffix array and its inverse with grammar- and/or Block-Tree-based representations of those arrays.
Our experimental results show that BT-CTs reach navigation speeds comparable to compact tree representations that are insensitive to repetitiveness, while using 2--10 times less space on the topologies of the suffix trees of repetitive collections. Our BT-CST is slightly larger than previous repetition-aware suffix trees based on grammar-compressed topologies, but outperforms them in time, often by orders of magnitude.Upper and lower bounds for dynamic data structures on stringshttps://zbmath.org/1487.680832022-07-25T18:03:43.254055Z"Clifford, Raphael"https://zbmath.org/authors/?q=ai:clifford.raphael"Grønlund, Allan"https://zbmath.org/authors/?q=ai:gronlund.allan"Larsen, Kasper Green"https://zbmath.org/authors/?q=ai:larsen.kasper-green"Starikovskaya, Tatiana"https://zbmath.org/authors/?q=ai:starikovskaya.tatiana-aSummary: We consider a range of simply stated dynamic data structure problems on strings. An update changes one symbol in the input and a query asks us to compute some function of the pattern of length \(m\) and a substring of a longer text. We give both conditional and unconditional lower bounds for variants of exact matching with wildcards, inner product, and Hamming distance computation via a sequence of reductions. As an example, we show that there does not exist an \(O(m^{1/2-\epsilon})\) time algorithm for a large range of these problems unless the online Boolean matrix-vector multiplication conjecture is false. We also provide nearly matching upper bounds for most of the problems we consider.
For the entire collection see [Zbl 1381.68010].An improved bound for random binary search trees with concurrent insertionshttps://zbmath.org/1487.680842022-07-25T18:03:43.254055Z"Giakkoupis, George"https://zbmath.org/authors/?q=ai:giakkoupis.george"Woelfel, Philipp"https://zbmath.org/authors/?q=ai:woelfel.philippSummary: Recently, \textit{J. Aspnes} and \textit{E. Ruppert} [Lect. Notes Comput. Sci. 9888, 371--384 (2016; Zbl 1393.68044)] defined the following simple random experiment to determine the impact of concurrency on the performance of binary search trees: \(n\) randomly permuted keys arrive one at a time. When a new key arrives, it is first placed into a buffer of size \(c\). Whenever the buffer is full, or when all keys have arrived, an adversary chooses one key from the buffer and inserts it into the binary search tree.
The ability of the adversary to choose the next key to insert among \(c\) buffered keys, models a distributed system, where up to \(c\) processes try to insert keys concurrently. Aspnes and Ruppert showed that the expected average depth of nodes in the resulting tree is \(O(\log(n)+c)\) for a comparison-based adversary, which can only take the relative order of arrived keys into account. We generalize and strengthen this result. In particular, we allow an adversary that knows the actual values of all keys that have arrived, and show that the resulting expected average node depth is \(D_\mathrm{avg}(n)+O(c)\), where \(D_\mathrm{avg}(n)=2\ln(n)-\Theta(1)\) is the expected average node depth of a random tree obtained in the standard unbuffered version of this experiment. Extending the bound by Aspnes and Ruppert to this stronger adversary model answers one of their open questions.
For the entire collection see [Zbl 1381.68010].An insight review on Bloom filter and its variants with applications: an emerging hash based membership querying techniquehttps://zbmath.org/1487.680852022-07-25T18:03:43.254055Z"Saravanan, K."https://zbmath.org/authors/?q=ai:saravanan.kadirvel"Senthilkumar, A."https://zbmath.org/authors/?q=ai:senthilkumar.amutha(no abstract)Representation of ordered trees with a given degree distributionhttps://zbmath.org/1487.680862022-07-25T18:03:43.254055Z"Tsur, Dekel"https://zbmath.org/authors/?q=ai:tsur.dekelIn this article the author proposes a new succinct data structure that stores an ordered tree \(T\) with \(n\) nodes using \(\log \mathcal{N}(\overrightarrow{n})+O(n/\log^t n)\) bits for every constant \(t\), were \(\mathcal{N}(\overrightarrow{n})\) is the number of trees with degree distribution \(\overrightarrow{n}\).
This new structure is a generalization of the aB-tree structure introduced by M. Pătrașcu. The querying of the structure requires a constant time. The proposed structure uses less space compared to two other similar structures for storing ordered trees (first introduced by \textit{J. Jansson} et al. [J. Comput. Syst. Sci. 78, No. 2, 619--631 (2012; Zbl 1242.68083)] and second introduced by \textit{G. Navarro} and \textit{K. Sadakane} [ACM Trans. Algorithms 10, No. 3, Article No. 16, 39 p. (2014; Zbl 1333.68084)]).
Reviewer: Mihai Gabroveanu (Craiova)c-trie++: a dynamic trie tailored for fast prefix searcheshttps://zbmath.org/1487.680872022-07-25T18:03:43.254055Z"Tsuruta, Kazuya"https://zbmath.org/authors/?q=ai:tsuruta.kazuya"Köppl, Dominik"https://zbmath.org/authors/?q=ai:koppl.dominik"Kanda, Shunsuke"https://zbmath.org/authors/?q=ai:kanda.shunsuke"Nakashima, Yuto"https://zbmath.org/authors/?q=ai:nakashima.yuto"Inenaga, Shunsuke"https://zbmath.org/authors/?q=ai:inenaga.shunsuke"Bannai, Hideo"https://zbmath.org/authors/?q=ai:bannai.hideo"Takeda, Masayuki"https://zbmath.org/authors/?q=ai:takeda.masayukiSummary: Given a dynamic set \(\mathcal{K}\) of \(k\) strings of total length \(n\) whose characters are drawn from an alphabet of size \(\sigma\), a keyword dictionary is a data structure built on \(\mathcal{K}\) that provides lookup, prefix search, and update operations on \(\mathcal{K}\). Under the assumption that \(\alpha = w / \lg \sigma\) characters fit into a single machine word of \(w\) bits, we propose a keyword dictionary that represents \(\mathcal{K}\) in either \(n \lg \sigma + \Theta(k \lg n)\) or \(| T | \lg \sigma + \Theta(k w)\) bits of space, where \(| T |\) is the number of nodes of a trie representing \(\mathcal{K}\). It supports all operations in \(\mathcal{O}(m / \alpha + \lg \alpha)\) expected time on an input string of length \(m\) in the word RAM model. An evaluation of our implementation highlights the practical usefulness of the proposed data structure, especially for prefix searches -- one of the most essential keyword dictionary operations.Optimal dislocation with persistent errors in subquadratic timehttps://zbmath.org/1487.680882022-07-25T18:03:43.254055Z"Geissmann, Barbara"https://zbmath.org/authors/?q=ai:geissmann.barbara"Leucci, Stefano"https://zbmath.org/authors/?q=ai:leucci.stefano"Liu, Chih-Hung"https://zbmath.org/authors/?q=ai:liu.chih-hung"Penna, Paolo"https://zbmath.org/authors/?q=ai:penna.paoloSummary: We study the problem of sorting \(N\) elements in presence of persistent errors in comparisons: In this classical model, each comparison between two elements is wrong independently with some probability \(p\), but repeating the same comparison gives always the same result. The best known algorithms for this problem have running time \(O(N^2)\) and achieve an optimal maximum dislocation of \(O(\log N)\) for constant error probability. Note that no algorithm can achieve dislocation \(o(\log N)\), regardless of its running time.
In this work we present the first subquadratic time algorithm with optimal maximum dislocation: Our algorithm runs in \(\tilde{O}(N^{3/2})\) time and guarantees \(O(\log N)\) maximum dislocation with high probability. Though the first version of our algorithm is randomized, it can be derandomized by extracting the necessary random bits from the results of the comparisons (errors).
For the entire collection see [Zbl 1381.68010].Property testing for bounded degree databaseshttps://zbmath.org/1487.680892022-07-25T18:03:43.254055Z"Adler, Isolde"https://zbmath.org/authors/?q=ai:adler.isolde"Harwath, Frederik"https://zbmath.org/authors/?q=ai:harwath.frederikSummary: Aiming at extremely efficient algorithms for big data sets, we introduce property testing of relational databases of bounded degree. Our model generalises the bounded degree model for graphs [\textit{O. Goldreich} and \textit{D. Ron}, in: Proceedings of the 29th annual ACM symposium on theory of computing, STOC '97. New York, NY: ACM, Association for Computing Machinery. 406--415 (1999; Zbl 0963.68154)]. We prove that in this model, if the databases have bounded tree-width, then every query definable in monadic second-order logic with modulo counting is testable with a constant number of oracle queries and polylogarithmic running time. This is the first logical meta-theorem in property testing of sparse models. Furthermore, we discuss conditions for the existence of uniform and non-uniform testers.
For the entire collection see [Zbl 1381.68010].Algebraic operators for processing sets of temporal intervals in relational databaseshttps://zbmath.org/1487.680902022-07-25T18:03:43.254055Z"Dohr, Andreas"https://zbmath.org/authors/?q=ai:dohr.andreas"Engels, Christiane"https://zbmath.org/authors/?q=ai:engels.christiane"Behrend, Andreas"https://zbmath.org/authors/?q=ai:behrend.andreasSummary: The efficient management of temporal data has become increasingly important for many database applications. Most commercial systems already allow the management of temporal data but the operational support for processing this data is still rather limited. One particular reason is that many extension proposals typically require considerable modifications of the underlying database engine. In this paper, we propose a lightweight solution where temporal operators are realized using a library of user-defined functions. This way the complexity of temporal queries can be drastically reduced leading to more readable and less error-prone code without touching the database system. Our experiments show that the proposed operators significantly outperform temporal queries formulated in pure SQL. In addition, we investigate the possibility to incorporate algebraic optimization strategies directly into our operator definitions which allow for further performance improvements.
For the entire collection see [Zbl 1402.68016].Minimal disclosure in hierarchical Hippocratic databases with delegationhttps://zbmath.org/1487.680912022-07-25T18:03:43.254055Z"Massacci, Fabio"https://zbmath.org/authors/?q=ai:massacci.fabio"Mylopoulos, John"https://zbmath.org/authors/?q=ai:mylopoulos.john"Zannone, Nicola"https://zbmath.org/authors/?q=ai:zannone.nicolaSummary: Hippocratic Databases have been proposed as a mechanism to guarantee the respect of privacy principles in data management. We argue that three major principles are missing from the proposed mechanism: hierarchies of purposes, delegation of tasks and authorizations (i.e. outsourcing), and the minimal disclosure of private information.
In this paper, we propose a flexible framework for the negotiation of personal information among customers and (possibly virtual) enterprises based on user preferences when enterprises may adopt different processes to provide the same service. We use a goal-oriented approach to analyze the purposes of a Hippocratic system and derive a purpose and delegation hierarchy. Based on this hierarchy, effective algorithms are given to determine the minimum set of authorizations needed for a service. In this way, the minimal authorization table of a global business process can be automatically constructed from the collection of privacy policy tables associated with the collaborating enterprises. By using effective on-line algorithms, the derivation of such minimal information can also be done on-the-fly by the customer wishing to use the services of a virtual organization.
For the entire collection see [Zbl 1481.68012].XML access control with policy matching treehttps://zbmath.org/1487.680922022-07-25T18:03:43.254055Z"Qi, Naizhen"https://zbmath.org/authors/?q=ai:qi.naizhen"Kudo, Michiharu"https://zbmath.org/authors/?q=ai:kudo.michiharuSummary: XML documents are frequently used in applications such as business transactions and medical records involving sensitive information. Access control on the basis of data location or value in an XML document is therefore essential. However, current approaches to efficient access control over XML documents have suffered from scalability problems because they tend to work on individual documents. To resolve this problem, we proposed a table-based approach in
[the authors, Lect. Notes Comput. Sci. 3193, 17--32 (2004; Zbl 07485489)].
However, [loc. cit.] also imposed limitations on the expressiveness, and real-time access control updates were not supported. In this paper, we propose a novel approach to XML access control through a policy matching tree (PMT) which performs accessibility checks with an efficient matching algorithm, and is shared by all documents of the same document type. The expressiveness can be expanded and real-time updates are supported because of the PTM's flexible structure. Using synthetic and real data, we evaluate the performance and scalability to show it is efficient for checking accessibility for XML databases.
For the entire collection see [Zbl 1481.68012].Privacy-preserving queries on encrypted datahttps://zbmath.org/1487.680932022-07-25T18:03:43.254055Z"Yang, Zhiqiang"https://zbmath.org/authors/?q=ai:yang.zhiqiang"Zhong, Sheng"https://zbmath.org/authors/?q=ai:zhong.sheng"Wright, Rebecca N."https://zbmath.org/authors/?q=ai:wright.rebecca-nSummary: Data confidentiality is a major concern in database systems. Encryption is a useful tool for protecting the confidentiality of sensitive data. However, when data is encrypted, performing queries becomes more challenging. In this paper, we study efficient and provably secure methods for queries on encrypted data stored in an outsourced database that may be susceptible to compromise. Specifically, we show that, in our system, even if an intruder breaks into the database and observes some interactions between the database and its users, he only learns very little about the data stored in the database and the queries performed on the data.
Our work consists of several components. First, we consider databases in which each attribute has a finite domain and give a basic solution for certain kinds of queries on such databases. Then, we present two enhanced solutions, one with a stronger security guarantee and the other with accelerated queries. In addition to providing proofs of our security guarantees, we provide empirical performance evaluations. Our experiments demonstrate that our solutions are fast on large-sized real data.
For the entire collection see [Zbl 1481.68014].Private information retrieval using trusted hardwarehttps://zbmath.org/1487.680942022-07-25T18:03:43.254055Z"Wang, Shuhong"https://zbmath.org/authors/?q=ai:wang.shuhong"Ding, Xuhua"https://zbmath.org/authors/?q=ai:ding.xuhua"Deng, Robert H."https://zbmath.org/authors/?q=ai:deng.robert-huijie"Bao, Feng"https://zbmath.org/authors/?q=ai:bao.fengSummary: Many theoretical PIR (Private Information Retrieval) constructions have been proposed in the past years. Though information theoretically secure, most of them are impractical to deploy due to the prohibitively high communication and computation complexity. The recent trend in outsourcing databases fuels the research on practical PIR schemes. In this paper, we propose a new PIR system by making use of trusted hardware. Our system is proven to be information theoretically secure. Furthermore, we derive the computation complexity lower bound for hardware-based PIR schemes and show that our construction meets the lower bounds for both the communication and computation costs, respectively.
For the entire collection see [Zbl 1481.68014].The capacity of private information retrieval under arbitrary collusion patterns for replicated databaseshttps://zbmath.org/1487.680952022-07-25T18:03:43.254055Z"Yao, Xinyu"https://zbmath.org/authors/?q=ai:yao.xinyu"Liu, Nan"https://zbmath.org/authors/?q=ai:liu.nan"Kang, Wei"https://zbmath.org/authors/?q=ai:kang.weiEditorial remark: No review copy delivered.A reversible data hiding scheme using bit flipping strategyhttps://zbmath.org/1487.680962022-07-25T18:03:43.254055Z"Kumar, Rajeev"https://zbmath.org/authors/?q=ai:kumar.rajeev"Chand, Satish"https://zbmath.org/authors/?q=ai:chand.satish(no abstract)Succinct oblivious RAMhttps://zbmath.org/1487.680972022-07-25T18:03:43.254055Z"Onodera, Taku"https://zbmath.org/authors/?q=ai:onodera.taku"Shibuya, Tetsuo"https://zbmath.org/authors/?q=ai:shibuya.tetsuoSummary: As online storage services become increasingly common, it is important that users' private information is protected from database access pattern analyses. Oblivious RAM (ORAM) is a cryptographic primitive that enables users to perform arbitrary database accesses without revealing any information about the access pattern to the server. Previous ORAM studies focused mostly on reducing the access overhead. Consequently, the access overhead of the state-of-the-art ORAM constructions are almost at practical levels in certain application scenarios such as secure processors. However, we assume that the server space usage could become a new important issue in the coming big-data era. To enable large-scale computation in security-aware settings, it is necessary to rethink the ORAM server space cost using big-data standards.
In this paper, we introduce ``succinctness'' as a theoretically tractable and practically relevant criterion of the ORAM server space efficiency in the big-data era. We, then, propose two succinct ORAM constructions that also exhibit state-of-the-art performance in terms of the bandwidth blowup and the user space. We also give non-asymptotic analyses and simulation results which indicate that the proposed ORAM constructions are practically effective.
For the entire collection see [Zbl 1381.68010].An efficient scheme for joint compression and encryptionhttps://zbmath.org/1487.680982022-07-25T18:03:43.254055Z"Qiu, Lirong"https://zbmath.org/authors/?q=ai:qiu.lirong"Yu, Yang"https://zbmath.org/authors/?q=ai:yu.yang(no abstract)Leakage-resilient revocable certificateless encryption with an outsourced revocation authorityhttps://zbmath.org/1487.680992022-07-25T18:03:43.254055Z"Tseng, Yuh-Min"https://zbmath.org/authors/?q=ai:tseng.yuh-min"Huang, Sen-Shan"https://zbmath.org/authors/?q=ai:huang.sen-shan"Tsai, Tung-Tso"https://zbmath.org/authors/?q=ai:tsai.tung-tso"Chuang, Yun-Hsin"https://zbmath.org/authors/?q=ai:chuang.yun-hsin"Hung, Ying-Hao"https://zbmath.org/authors/?q=ai:hung.ying-hao(no abstract)An algebra for composing enterprise privacy policieshttps://zbmath.org/1487.681002022-07-25T18:03:43.254055Z"Backes, Michael"https://zbmath.org/authors/?q=ai:backes.michael"Dürmuth, Markus"https://zbmath.org/authors/?q=ai:durmuth.markus"Steinwandt, Rainer"https://zbmath.org/authors/?q=ai:steinwandt.rainerSummary: Enterprise privacy enforcement allows enterprises to internally enforce a privacy policy that the enterprise has decided to comply to. To facilitate the compliance with different privacy policies when several parts of an organization or different enterprises cooperate, it is crucial to have tools at hand that allow for a practical management of varying privacy requirements.
We propose an algebra providing various types of operators for composing and restricting enterprise privacy policies like conjunction, disjunction, and scoping, together with its formal semantics. We base our work on a superset of the syntax and semantics of IBM's Enterprise Privacy Authorization Language (EPAL), which recently has been submitted to W3C for standardization. However, a detailed analysis of the expressiveness of EPAL reveals that, somewhat surprisingly, EPAL is not closed under conjunction and disjunction. To circumvent this problem, we identified the subset of well-founded privacy policies which enjoy the property that the result of our algebraic operations can be turned into a coherent privacy policy again. This enables existing privacy policy enforcement mechanisms to deal with our algebraic expressions. We further show that our algebra fits together with the existing notions of privacy policy refinement and sequential composition of privacy policies in a natural way.
For the entire collection see [Zbl 1481.68022].Relations between greedy and bit-optimal LZ77 encodingshttps://zbmath.org/1487.681012022-07-25T18:03:43.254055Z"Kosolobov, Dmitry"https://zbmath.org/authors/?q=ai:kosolobov.dmitrySummary: This paper investigates the size in bits of the LZ77 encoding, which is the most popular and efficient variant of the Lempel-Ziv encodings used in data compression. We prove that, for a wide natural class of variable-length encoders for LZ77 phrases, the size of the greedily constructed LZ77 encoding on constant alphabets is within a factor \(O(\frac{\log n}{\log\log\log n})\) of the optimal LZ77 encoding, where \(n\) is the length of the processed string. We describe a series of examples showing that, surprisingly, this bound is tight, thus improving both the previously known upper and lower bounds. Further, we obtain a more detailed bound \(O(\min{z,\frac{\log n}{\log\log z}})\), which uses the number \(z\) of phrases in the greedy LZ77 encoding as a parameter, and construct a series of examples showing that this bound is tight even for binary alphabet. We then investigate the problem on non-constant alphabets: we show that the known \(O(\log n)\) bound is tight even for alphabets of logarithmic size, and provide tight bounds for some other important cases.
For the entire collection see [Zbl 1381.68010].LZRR: LZ77 parsing with right referencehttps://zbmath.org/1487.681022022-07-25T18:03:43.254055Z"Nishimoto, Takaaki"https://zbmath.org/authors/?q=ai:nishimoto.takaaki.1"Tabei, Yasuo"https://zbmath.org/authors/?q=ai:tabei.yasuoSummary: Lossless data compression has been widely studied in computer science. One of the most widely used lossless data compressions is \textit{Lempel-Ziv} (LZ) 77 parsing, which achieves a high compression ratio. \textit{Bidirectional} (a.k.a. \textit{macro}) parsing is a lossless data compression technique that computes a sequence of phrases copied from another substring (\textit{target phrase}) on either the left or the right position in an input string. Navarro et al. recently showed that a large gap may exist between the size of the smallest bidirectional parse of a given string and that of LZ77 parsing. In addition, finding the smallest bidirectional parse of a given text is NP-complete. Several variants of bidirectional parsing algorithm have been proposed thus far, but no prior work for bidirectional parsing algorithm has achieved compression that is at least as good as LZ77 parsing for any string. In this paper, we present the first practical bidirectional parsing algorithm named \textit{LZ77 parsing with right reference (LZRR)}, in which the number of LZRR phrases is theoretically guaranteed to be not larger than the number of LZ77 phrases. Experimental results using benchmark strings show that the number of LZRR phrases is approximately six percent smaller than that of LZ77 phrases.Recursive combinatorial structures: enumeration, probabilistic analysis and random generationhttps://zbmath.org/1487.681692022-07-25T18:03:43.254055Z"Salvy, Bruno"https://zbmath.org/authors/?q=ai:salvy.brunoSummary: In a probabilistic context, the main data structures of computer science are viewed as random combinatorial objects. Analytic combinatorics, as described in the book by \textit{P. Flajolet} and \textit{R. Sedgewick} [Analytic combinatorics. Cambridge: Cambridge University Press (2009; Zbl 1165.05001)], provides a set of high-level tools for their probabilistic analysis. Recursive combinatorial definitions lead to generating function equations from which efficient algorithms can be designed for enumeration, random generation and, to some extent, asymptotic analysis. With a focus on random generation, this tutorial first covers the basics of Analytic Combinatorics and then describes the idea of Boltzmann sampling and its realisation.
The tutorial addresses a broad TCS audience and no particular pre-knowledge on analytic combinatorics is expected.
For the entire collection see [Zbl 1381.68010].Edge minimization in de Bruijn graphshttps://zbmath.org/1487.681722022-07-25T18:03:43.254055Z"Baier, Uwe"https://zbmath.org/authors/?q=ai:baier.uwe"Büchler, Thomas"https://zbmath.org/authors/?q=ai:buchler.thomas"Ohlebusch, Enno"https://zbmath.org/authors/?q=ai:ohlebusch.enno"Weber, Pascal"https://zbmath.org/authors/?q=ai:weber.pascalSummary: This paper introduces the de Bruijn graph edge minimization problem, which is related to the compression of de Bruijn graphs: find the order-\(k\) de Bruijn graph with minimum edge count among all orders. We describe an efficient algorithm that solves this problem. Since the edge minimization problem is connected to the BWT compression technique called ``tunneling'', the paper also describes a way to minimize the length of a tunneled BWT in such a way that useful properties for sequence analysis are preserved. Thus, it provides significant progress towards a solution to the open problem of finding optimal disjoint blocks that minimize space, as stated
in [\textit{J. Alanko} et al., ``Tunneling on Wheeler graphs'', in: Proceedings of the data compression conference, DCC'19. Los Alamitos, CA: IEEE Computer Society. 122--131 (2019; \url{doi:10.1109/DCC.2019.00020})].Faster dynamic controllability checking for simple temporal networks with uncertaintyhttps://zbmath.org/1487.682072022-07-25T18:03:43.254055Z"Cairo, Massimo"https://zbmath.org/authors/?q=ai:cairo.massimo"Hunsberger, Luke"https://zbmath.org/authors/?q=ai:hunsberger.luke"Rizzi, Romeo"https://zbmath.org/authors/?q=ai:rizzi.romeoSummary: Simple Temporal Networks (STNs) are a well-studied model for representing and reasoning about time. An STN comprises a set of real-valued variables called time-points, together with a set of binary constraints, each of the form \(Y\le X+w\). The problem of finding a feasible schedule (i.e., an assignment of real numbers to time-points such that all of the constraints are satisfied) is equivalent to the Single Source Shortest Path problem (SSSP) in the STN graph.\par Simple Temporal Networks with Uncertainty (STNUs) augment STNs to include contingent links that can be used, for example, to represent actions with uncertain durations. The duration of a contingent link is not controlled by the planner, but is instead controlled by a (possibly adversarial) environment. Each contingent link has the form, \(\langle A,\ell,u,C\rangle\), where \(0<\ell\le u<\infty\). Once the planner executes the activation time-point \(A\), the environment must execute the contingent time-point \(C\) at some time \(A+\Delta\), where \(\Delta\in[\ell,u]\). Crucially, the planner does not know the value of \(\Delta\) in advance, but only discovers it when \(C\) executes. An STNU is dynamically controllable (DC) if there is a strategy that the planner can use to execute all of the non-contingent time-points, such that all of the constraints are guaranteed to be satisfied no matter which durations the environment chooses for the contingent links. The strategy can be dynamic in that it can react in real time to the contingent durations it observes. Recently, an upper bound of \(O(N^3)\) was given for the DC-checking problem for STNUs, where \(N\) is the number of time-points.\par This paper introduces a new algorithm, called the \(\mathit{RUL}^-\) algorithm, for solving the DC-checking problem for STNUs that improves on the \(O(N^3)\) bound. The worst-case complexity of the \(\mathit{RUL}^-\) algorithm is \(O(MN +K^2N +KN\log N)\), where \(N\) is the number of time-points, \(M\) is the number of constraints, and \(K\) is the number of contingent time-points. If \(M\) is \(O(N^2)\), then the complexity reduces to \(O(N^3)\); however, in sparse graphs the complexity can be much less. For example, if \(M\) is \(O(N\log N)\), and \(K\) is \(O(\sqrt{N})\), then the complexity of the \(\mathit{RUL}^-\) algorithm reduces to \(O(N^2\log N)\).\par The \(\mathit{RUL}^-\) algorithm begins by using the Bellman-Ford algorithm to compute a potential function. It then performs at most \(2K\) rounds of computations, interleaving novel applications of Dijkstra's algorithm to (1) generate new edges and (2) update the potential function in response to those new edges. The constraint-propagation/edge-generation rules used by the \(\mathit{RUL}^-\) algorithm are distinguished from related work in two ways. First, they only generate unlabeled edges. Second, their applicability conditions are more restrictive. As a result, the \(\mathit{RUL}^-\) algorithm requires only \(O(K)\) rounds of Dijkstra's algorithm, instead of the \(O(N)\) rounds required by other approaches. The paper proves that the \(\mathit{RUL}^-\) algorithm is sound and complete for the DC-checking problem for STNUs.
For the entire collection see [Zbl 1402.68016].Extending conditional simple temporal networks with partially shrinkable uncertaintyhttps://zbmath.org/1487.682102022-07-25T18:03:43.254055Z"Combi, Carlo"https://zbmath.org/authors/?q=ai:combi.carlo"Posenato, Roberto"https://zbmath.org/authors/?q=ai:posenato.robertoSummary: The proper handling of temporal constraints is crucial in many domains. As a particular challenge, temporal constraints must be also handled when different specific situations happen (conditional constraints) and when some event occurrences can be only observed at run time (contingent constraints). In this paper we introduce Conditional Simple Temporal Networks with Partially Shrinkable Uncertainty (CSTNPSUs), in which contingent constraints are made more flexible (guarded constraints) and they are also specified as conditional constraints. It turns out that guarded constraints require the ability to reason on both kinds of constraints in a seamless way. In particular, we discuss CSTNPSU features through a motivating example and, then, we introduce the concept of controllability for such networks and the related sound checking algorithm.
For the entire collection see [Zbl 1402.68016].Deciding the consistency of branching time interval networkshttps://zbmath.org/1487.682122022-07-25T18:03:43.254055Z"Gavanelli, Marco"https://zbmath.org/authors/?q=ai:gavanelli.marco"Passantino, Alessandro"https://zbmath.org/authors/?q=ai:passantino.alessandro"Sciavicco, Guido"https://zbmath.org/authors/?q=ai:sciavicco.guidoSummary: Allen's Interval Algebra (IA) is one of the most prominent formalisms in the area of qualitative temporal reasoning; however, its applications are naturally restricted to linear flows of time. When dealing with nonlinear time, Allen's algebra can be extended in several ways, and, as suggested by
\textit{M. Ragni} and \textit{S. Wölfl} [``Branching Allen'', Lect. Notes Comput. Sci. 3343, 323--343 (2004; \url{doi:10.1007/978-3-540-32255-9_19})],
a possible solution consists in defining the Branching Algebra (BA) as a set of 19 basic relations (13 basic linear relations plus 6 new basic nonlinear ones) in such a way that each basic relation between two intervals is completely defined by the relative position of the endpoints on a tree-like partial order. While the problem of deciding the consistency of a network of IA-constraints is well- studied, and every subset of the IA has been classified with respect to the tractability of its consistency problem, the fragments of the BA have received less attention. In this paper, we first define the notion of convex BA-relation, and, then, we prove that the consistency of a network of convex BA-relations can be decided via path consistency, and is therefore a polynomial problem. This is the first non-trivial tractable fragment of the BA; given the clear parallel with the linear case, our contribution poses the bases for a deeper study of fragments of BA towards their complete classification.
For the entire collection see [Zbl 1402.68016].Sound-and-complete algorithms for checking the dynamic controllability of conditional simple temporal networks with uncertaintyhttps://zbmath.org/1487.682142022-07-25T18:03:43.254055Z"Hunsberger, Luke"https://zbmath.org/authors/?q=ai:hunsberger.luke"Posenato, Roberto"https://zbmath.org/authors/?q=ai:posenato.robertoSummary: A Conditional Simple Temporal Network with Uncertainty (CSTNU) is a data structure for representing and reasoning about time. CSTNUs incorporate observation time-points from Conditional Simple Temporal Networks (CSTNs) and contingent links from Simple Temporal Networks with Uncertainty (STNUs). A CSTNU is dynamically controllable (DC) if there exists a strategy for executing its time-points that guarantees the satisfaction of all relevant constraints no matter how the uncertainty associated with its observation time-points and contingent links is resolved in real time. This paper presents the first sound-and-complete DC-checking algorithms for CSTNUs that are based on the propagation of labeled constraints and demonstrates their practicality.
For the entire collection see [Zbl 1402.68016].Reducing epsilon-DC checking for conditional simple temporal networks to DC checkinghttps://zbmath.org/1487.682152022-07-25T18:03:43.254055Z"Hunsberger, Luke"https://zbmath.org/authors/?q=ai:hunsberger.luke"Posenato, Roberto"https://zbmath.org/authors/?q=ai:posenato.robertoSummary: Recent work on Conditional Simple Temporal Networks (CSTNs) has introduced the problem of checking the dynamic consistency (DC) property for the case where the reaction time of an execution strategy to observations is bounded below by some fixed \(\varepsilon>0\), the so-called \(\varepsilon\)-DC-checking problem. This paper proves that the \(\varepsilon\)-DC-checking problem for CSTNs can be reduced to the standard DC-checking problem for CSTNs -- without incurring any computational cost. Given any CSTN \(\mathcal{S}\) with \(k\) observation time-points, the paper defines a new CSTN \(\mathcal{S}_0\) that is the same as \(\mathcal{S}\), except that for each observation time-point \(P\)? in \(\mathcal{S}\): (i) \(P\)? is denoted to a non-observation time-point in \(\mathcal{S}_0\); and (ii) a new observation time-point \(P_0\)?, constrained to occur exactly \(\varepsilon\) units after \(P\)?, is inserted into \(\mathcal{S}_0\). The paper proves that \(\mathcal{S}\) is \(\varepsilon\)-DC if and only if \(\mathcal{S}_0\) is (standard) DC, and that the application of the \(\varepsilon\)-DC-checking constraint-propagation rules to \(\mathcal{S}\) is equivalent to the application of the corresponding (standard) DC-checking constraint-propagation rules to \(\mathcal{S}_0\). Two versions of these results are presented that differ only in whether a dynamic strategy for \(\mathcal{S}_0\) can react instantaneously to observations, or only after some arbitrarily small, positive delay. Finally, the paper demonstrates empirically that building \(\mathcal{S}_0\) and DC-checking it incurs no computational cost as the sizes of the instances increase.
For the entire collection see [Zbl 1402.68016].Comparison of the representational power of random forests, binary decision diagrams, and neural networkshttps://zbmath.org/1487.682232022-07-25T18:03:43.254055Z"Kumano, So"https://zbmath.org/authors/?q=ai:kumano.so"Akutsu, Tatsuya"https://zbmath.org/authors/?q=ai:akutsu.tatsuyaSummary: In this letter, we compare the representational power of random forests, binary decision diagrams (BDDs), and neural networks in terms of the number of nodes. We assume that an axis-aligned function on a single variable is assigned to each edge in random forests and BDDs, and the activation functions of neural networks are sigmoid, rectified linear unit, or similar functions. Based on existing studies, we show that for any random forest, there exists an equivalent depth-3 neural network with a linear number of nodes. We also show that for any BDD with balanced width, there exists an equivalent shallow depth neural network with a polynomial number of nodes. These results suggest that even shallow neural networks have the same or higher representation power than deep random forests and deep BDDs. We also show that in some cases, an exponential number of nodes are required to express a given random forest by a random forest with a much fewer number of trees, which suggests that many trees are required for random forests to represent some specific knowledge efficiently.Space-efficient algorithms for longest increasing subsequencehttps://zbmath.org/1487.682612022-07-25T18:03:43.254055Z"Kiyomi, Masashi"https://zbmath.org/authors/?q=ai:kiyomi.masashi"Ono, Hirotaka"https://zbmath.org/authors/?q=ai:ono.hirotaka"Otachi, Yota"https://zbmath.org/authors/?q=ai:otachi.yota"Schweitzer, Pascal"https://zbmath.org/authors/?q=ai:schweitzer.pascal"Tarui, Jun"https://zbmath.org/authors/?q=ai:tarui.junSummary: Given a sequence of integers, we want to find a longest increasing subsequence of the sequence. It is known that this problem can be solved in \(O(n\log n)\) time and space. Our goal in this paper is to reduce the space consumption while keeping the time complexity small. For \(\sqrt(n)\leq s\leq n\), we present algorithms that use \(O(s\log n)\) bits and \(O(\frac{1}{s}\cdot n^2\cdot\log n)\) time for computing the length of a longest increasing subsequence, and \(O(\frac{1}{s}\cdot n^2\cdot\log^2 n)\) time for finding an actual subsequence. We also show that the time complexity of our algorithms is optimal up to polylogarithmic factors in the framework of sequential access algorithms with the prescribed amount of space.
For the entire collection see [Zbl 1381.68010].Round efficient secure multiparty quantum computation with identifiable aborthttps://zbmath.org/1487.810342022-07-25T18:03:43.254055Z"Alon, Bar"https://zbmath.org/authors/?q=ai:alon.bar"Chung, Hao"https://zbmath.org/authors/?q=ai:chung.hao"Chung, Kai-Min"https://zbmath.org/authors/?q=ai:chung.kai-min"Huang, Mi-Ying"https://zbmath.org/authors/?q=ai:huang.mi-ying"Lee, Yi"https://zbmath.org/authors/?q=ai:lee.yi"Shen, Yu-Ching"https://zbmath.org/authors/?q=ai:shen.yu-chingSummary: A recent result by \textit{Y. Dulek} et al. [Lect. Notes Comput. Sci. 12107, 729--758 (2020; Zbl 1480.81029)] showed a secure protocol for computing any quantum circuit even without the presence of an honest majority. Their protocol, however, is susceptible to a ``denial of service'' attack and allows even a single corrupted party to force an abort. We propose the first quantum protocol that admits \textit{security-with-identifiable-abort}, which allows the honest parties to agree on the identity of a corrupted party in case of an abort. Additionally, our protocol is the first to have the property that the number of rounds where quantum communication is required is \textit{independent of the circuit complexity}. Furthermore, if there exists a post-quantum secure classical protocol whose round complexity is independent of the circuit complexity, then our protocol has this property as well. Our protocol is secure under the assumption that classical quantum-resistant fully homomorphic encryption schemes with decryption circuit of logarithmic depth exist. Interestingly, our construction also admits a reduction from quantum fair secure computation to classical fair secure computation.
For the entire collection see [Zbl 1483.94004].Bifurcation curves of two-dimensional quantum walkshttps://zbmath.org/1487.810452022-07-25T18:03:43.254055Z"Kuklinski, Parker"https://zbmath.org/authors/?q=ai:kuklinski.parker"Kon, Mark"https://zbmath.org/authors/?q=ai:kon.mark-aSummary: The quantum walk differs fundamentally from the classical random walk in a number of ways, including its linear spreading and initial condition dependent asymmetries. Using stationary phase approximations, precise asymptotics have been derived for one-dimensional two-state quantum walks, one-dimensional three-state Grover walks, and two-dimensional four-state Grover walks. Other papers have investigated asymptotic behavior of a much larger set of two-dimensional quantum walks and it has been shown that in special cases the regions of polynomial decay can be parameterized. In this paper, we show that these regions of polynomial decay are bounded by algebraic curves which can be explicitly computed. We give examples of these bifurcation curves for a number of two-dimensional quantum walks.
For the entire collection see [Zbl 1466.81003].Impossibility of quantum virtual black-box obfuscation of classical circuitshttps://zbmath.org/1487.810592022-07-25T18:03:43.254055Z"Alagic, Gorjan"https://zbmath.org/authors/?q=ai:alagic.gorjan"Brakerski, Zvika"https://zbmath.org/authors/?q=ai:brakerski.zvika"Dulek, Yfke"https://zbmath.org/authors/?q=ai:dulek.yfke"Schaffner, Christian"https://zbmath.org/authors/?q=ai:schaffner.christianSummary: Virtual black-box obfuscation is a strong cryptographic primitive: it encrypts a circuit while maintaining its full input/output functionality. A remarkable result by \textit{B. Barak} et al. [Lect. Notes Comput. Sci. 2139, 1--18 (2001; Zbl 1001.68511)] shows that a general obfuscator that obfuscates classical circuits into classical circuits cannot exist. A promising direction that circumvents this impossibility result is to obfuscate classical circuits into quantum states, which would potentially be better capable of hiding information about the obfuscated circuit. We show that, under the assumption that Learning With Errors (LWE) is hard for quantum computers, this quantum variant of virtual black-box obfuscation of classical circuits is generally impossible. On the way, we show that under the presence of dependent classical auxiliary input, even the small class of classical point functions cannot be quantum virtual black-box obfuscated.
For the entire collection see [Zbl 1483.94004].Efficient quantum homomorphic encryption scheme with flexible evaluators and its simulationhttps://zbmath.org/1487.810682022-07-25T18:03:43.254055Z"Liu, Jiang"https://zbmath.org/authors/?q=ai:liu.jiang"Li, Qin"https://zbmath.org/authors/?q=ai:li.qin"Quan, Junyu"https://zbmath.org/authors/?q=ai:quan.junyu"Wang, Can"https://zbmath.org/authors/?q=ai:wang.can"Shi, Jinjing"https://zbmath.org/authors/?q=ai:shi.jinjing"Situ, Haozhen"https://zbmath.org/authors/?q=ai:situ.haozhenSummary: Quantum homomorphic encryption (QHE) allows computation on encrypted data by employing the principles of quantum mechanics. Usually, only one evaluator is chosen to complete such computation and it is easy to get overburdened in network. In addition, users sometimes do not trust only one evalutor. Recently, \textit{X.-B. Chen} et al. [Inf. Sci. 501, 172--181 (2019; Zbl 1453.81013)] proposed a very flexible QHE scheme based on the idea of \((k, n)\)-threshold quantum state sharing where \(d\) evaluators can finish the required operations by cooperating together as long as \(k \le d \le n\). But it can only calculate some of single-qubit unitary operations when \(k\ge 2\) and the quantum capability of each evaluator is a bit demanding. In this paper, we propose an improved flexible QHE scheme which extends the operations that can be computed in the QHE scheme proposed by Chen et al. [loc. cit.] to involve all single-qubit unitary operations even if \(k \ge 2\) and reduces the quantum capability of at least \(d-1\) evaluators. We also give an example to show the feasibility of the improved scheme and simulate it on the IBM's cloud quantum computing platform.Rational complexity of binary sequences, F\(\mathbb{Q}\)SRs, and pseudo-ultrametric continued fractions in \(\mathbb{R}\)https://zbmath.org/1487.940942022-07-25T18:03:43.254055Z"Vielhaber, Michael"https://zbmath.org/authors/?q=ai:vielhaber.michael"del Pilar Canales Chacón, Mónica"https://zbmath.org/authors/?q=ai:del-pilar-canales-chacon.monica"Ceballos, Sergio Jara"https://zbmath.org/authors/?q=ai:ceballos.sergio-jaraSummary: We introduce rational complexity, a new complexity measure for binary sequences. The sequence \(s \in B^{\omega}\) is considered as binary expansion of a real fraction \(s \equiv\sum_{k\in \mathbb{N}}s_k 2^{-k}\in [0,1] \subset \mathbb{R}\). We compute its continued fraction expansion (CFE) by the Binary CFE Algorithm, a bitwise approximation of \(s\) by binary search in the encoding space of partial denominators, obtaining rational approximations \(r\) of \(s\) with \(r \rightarrow s\). We introduce Feedback in \(\mathbb{Q}\) Shift Registers (F\(\mathbb{Q}\)SRs) as the analogue of Linear Feedback Shift Registers (LFSRs) for the linear complexity L, and Feedback with Carry Shift Registers (FCSRs) for the 2-adic complexity A. We show that there is a substantial subset of prefixes with ``typical'' linear and 2-adic complexities, around \(n/2\), but low rational complexity. Thus the three complexities sort out different sequences as non-random.On the concurrent composition of quantum zero-knowledgehttps://zbmath.org/1487.940982022-07-25T18:03:43.254055Z"Ananth, Prabhanjan"https://zbmath.org/authors/?q=ai:ananth.prabhanjan-vijendra"Chung, Kai-Min"https://zbmath.org/authors/?q=ai:chung.kai-min"Placa, Rolando L. La"https://zbmath.org/authors/?q=ai:la-placa.rolando-lQuantum zero-knowledge is zero-knowledge where the verifier is modeled as a quantum polynomial-time algorithm. Ever since the threat of quantum computer has become real, researchers have worked on quantum zero-knowledge, with an almost exclusive focus on standalone protocols, i.e. protocols that work in isolation. As noted by many authors, the mentioned scenario is not the most realistic. A more realistic one is indeed obtained assuming that the party can also play in other protocol executions; this can be modeled assuming that there is a single prover simultaneously interacting with multiple verifiers controlled by a single malicious quantum polynomial-time adversary. However, security in this relevant scenario, called concurrent composition, has remained unaddressed in the quantum setting. This paper is aimed at closing this gap. In particular, the authors' focus is on the bounded concurrent setting, where the prover can interact with a predetermined number of verifiers, the bound being fixed at the time of protocol specification.
In this regard, the authors show a quantum zero-knowledge proof system for each language in NP, which satisfy soundness. Moreover, they show that there exists a quantum zero-knowledge proof system satisfying the quantum proof of knowledge property, i.e. the classical proof of knowledge property adapted to the quantum case (cf. Definition 8). The proposed construction is inspired to the bounded concurrent (classical) zero-knowledge construction of \textit{R. Pass} et al. [Lect. Notes Comput. Sci. 5677, 160--176 (2009; Zbl 1252.94092)]. The quantum zero-knowledge property is proved by means of the use of a new classical simulation strategy, that the authors called block rewinding, combined with Watrous rewinding. The quantum proof of knowledge property is instead obtained by means of a novel extraction mechanism that uses oblivious transfer to extract a bit from a quantum adversary.
Similar results are obtained for the quantum version of MA protocols in the bounded concurrency setting.
For the entire collection see [Zbl 1483.94004].
Reviewer: Roberto Civino (L'Aquila)Analytical characteristics of the DEShttps://zbmath.org/1487.941092022-07-25T18:03:43.254055Z"Davio, Marc"https://zbmath.org/authors/?q=ai:davio.marc"Desmedt, Yvo"https://zbmath.org/authors/?q=ai:desmedt.yvo-g"Fosséprez, Marc"https://zbmath.org/authors/?q=ai:fosseprez.marc"Govaerts, René"https://zbmath.org/authors/?q=ai:govaerts.rene-j-m"Hulsbosch, Jan"https://zbmath.org/authors/?q=ai:hulsbosch.jan"Neutjens, Patrik"https://zbmath.org/authors/?q=ai:neutjens.patrik"Piret, Philippe"https://zbmath.org/authors/?q=ai:piret.philippe-m"Quisquater, Jean-Jacques"https://zbmath.org/authors/?q=ai:quisquater.jean-jacques"Vandewalle, Joos"https://zbmath.org/authors/?q=ai:vandewalle.joos-p"Wouters, Pascal"https://zbmath.org/authors/?q=ai:wouters.pascalFrom the introduction: The purpose of our paper is not to revive the DES controversy, but to explore the internal structures in DES. The basic observation here is that the standard, as described in the NBS publication, is defined by tables so that it is difficult to detect both the structure and the functional properties. There exist several reasons to explore the internal structure and the functional properties in the DES.
For the entire collection see [Zbl 0609.94003].Improved fault analysis on the block cipher SPECK by injecting faults in the same roundhttps://zbmath.org/1487.941142022-07-25T18:03:43.254055Z"Feng, Jingyi"https://zbmath.org/authors/?q=ai:feng.jingyi"Chen, Hua"https://zbmath.org/authors/?q=ai:chen.hua.1"Gao, Si"https://zbmath.org/authors/?q=ai:gao.si"Fan, Limin"https://zbmath.org/authors/?q=ai:fan.limin"Feng, Dengguo"https://zbmath.org/authors/?q=ai:feng.dengguoSummary: SPECK is a new family of lightweight block ciphers proposed by the U.S. National Security Agency in 2013. So far, there exist several fault analysis results on this family. In this paper, we propose an improved fault analysis on SPECK under the random byte fault model, which only needs to induce faults at one intermediate round to retrieve the whole master key. In this attack, the fault propagation properties of SPECK are fully utilized, not only to determine the locations and the values of the faults, but also to eliminate incorrect candidates of the key. Moreover, compared with the previous approaches, more characteristics of the nonlinear modular addition operation are exploited, and the relations between different pairs of ciphertexts are also taken into account, which greatly enhance the efficiency of the key recovery. Finally, the experimental results confirm the correctness and the effectiveness of our proposed attack.
For the entire collection see [Zbl 1358.68013].Secure multiparty computations in floating-point arithmetichttps://zbmath.org/1487.941172022-07-25T18:03:43.254055Z"Guo, Chuan"https://zbmath.org/authors/?q=ai:guo.chuan"Hannun, Awni"https://zbmath.org/authors/?q=ai:hannun.awni"Knott, Brian"https://zbmath.org/authors/?q=ai:knott.brian"van der Maaten, Laurens"https://zbmath.org/authors/?q=ai:van-der-maaten.laurens|van-der-maaten.laurens-j-p"Tygert, Mark"https://zbmath.org/authors/?q=ai:tygert.mark"Zhu, Ruiyu"https://zbmath.org/authors/?q=ai:zhu.ruiyuSummary: Secure multiparty computations enable the distribution of so-called shares of sensitive data to multiple parties such that the multiple parties can effectively process the data while being unable to glean much information about the data (at least not without collusion among all parties to put back together all the shares). Thus, the parties may conspire to send all their processed results to a trusted third party (perhaps the data providers) at the conclusion of the computations, with only the trusted third party being able to view the final results. Secure multiparty computations for privacy-preserving machine-learning turn out to be possible using solely standard floating-point arithmetic, at least with a carefully controlled leakage of information less than the loss of accuracy due to roundoff, all backed by rigorous mathematical proofs of worst-case bounds on information loss and numerical stability in finite-precision arithmetic. Numerical examples illustrate the high performance attained on commodity off-the-shelf hardware for generalized linear models, including ordinary linear least-squares regression, binary and multinomial logistic regression, probit regression and Poisson regression.Private proximity retrieval codeshttps://zbmath.org/1487.941972022-07-25T18:03:43.254055Z"Zhang, Yiwei"https://zbmath.org/authors/?q=ai:zhang.yiwei"Yaakobi, Eitan"https://zbmath.org/authors/?q=ai:yaakobi.eitan"Etzion, Tuvi"https://zbmath.org/authors/?q=ai:etzion.tuviEditorial remark: No review copy delivered.