1,720,958 research outputs found
Optimal Oblivious RAM with Integrity
No full textOblivious RAM (ORAM), introduced by Goldreich and Ostrovsky (J. ACM ’96), is a protocol that allows a client to perform RAM computations on a server without revealing any information about the underlying data, even via the access pattern. For a memory of size N, well-known lower bounds show that a multiplicative overhead of Ω(log N) in the number of RAM operations is necessary. A long sequence of works culminated in the asymptotically optimal construction of Asharov, Komargodski, Lin, and Shi (CRYPTO 2021) with O(log N) worst-case overhead and O(1) client storage.
However, this optimal ORAM construction is only known to be secure in the semi-honest setting, where an adversary is allowed to observe the access patterns but not modify the contents of the memory. If an adversary is allowed to tamper with the database, this construction, as well as many existing ORAM constructions, in fact become insecure.
In this work, we construct an ORAM protocol with worst-case O(log N) overhead and O(1) client storage that also protects against tampering adversaries. This matches the efficiency of the best known ORAM constructions while additionally providing security against tampering. We achieve this by adapting the construction of Asharov et al. in a non-black-box way by using a combination of online and offline memory checking techniques, as introduced by Blum et al. (Algorithmica, 1994).S.M
Succinct Cryptography via Propositional Proofs
No full textThe goal in modern cryptography is to obtain security while minimizing the use of computational resources. In recent years, we have been incredibly successful in our pursuit for efficiency, even for cryptographic tasks that were thought to be “science fiction”. For example, we have constructions of fully homomorphic encryption and private information retrieval from standard, cryptographic assumptions which achieve the ideal levels of succinctness. However, there are still some tasks in cryptography where achieving the “ideal” efficiency from standard assumptions has evaded us. In this thesis, we study the problem of achieving succinctness in two such settings: • Can we construct succinct indistinguishability obfuscation (IO) for Turing machines? In particular, can we construct an obfuscated program whose size is independent of the input length? • Can we construct succinct non-interactive arguments (SNARGs) for all of NP? While the problems seem unrelated at first glance, the root difficulty seems to stem from a similar place: both primitives have non-falsifiable security definitions. In fact, this type of barrier exists for many other cryptographic primitives, including witness encryption. This leads to a central question which we refer to as the “non-falsifiability barrier”: how can we construct non-falsifiable primitives from falsifiable assumptions? In this thesis, we show how to leverage propositional proofs to overcome the non-falsifiability barrier, and make substantial progress in the goal of achieving succinctness in both settings. Our main result is universal construction of both SNARGs and succinct IO for Turing machines from standard assumptions using propositional proofs. We then show several applications, including rate-1 IO for many programs, the first succinct secret sharin schemes for monotone circuits, and many more. Our results establish propositional proofs as a foundational tool for achieving succinctness across a broad range of cryptographic settings.Ph.D
Going Beyond Counting First Authors in Author Co-citation Analysis
Get PDFThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Variations on the Author
Get PDF“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
Appropriate Similarity Measures for Author Cocitation Analysis
Get PDFWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
Dispelling the Myths Behind First-author Citation Counts
Get PDFWe conducted a full-scale evaluative citation analysis study of scholars in the XML research field to explore just how different from each other author rankings resulting from different citation counting methods actually are, and to demonstrate the capability of emerging data and tools on the Web in supporting more realistic citation counting methods. Our results contest some common arguments for the continued
use of first-author citation counts in the evaluation of scholars, such as high correlations between author rankings by first-author citation counts and other citation
counting methods, and high costs of using more realistic citation counting methods that are not well-supported by the ISI databases. It is argued that increasingly available digital full text research papers make it possible for citation analysis studies to go beyond what the ISI databases have directly supported and to employ more
sophisticated methods
koamabayili/VECTRON-author-checklist: VECTRON author checklist
No full textWe have done our best to complete the author checklist relating to the use of animals in the hut study. Note that the objective for the hut study was to evaluate the IRS treatment applications for residual efficacy against Anopheles mosquitoes, including the local An. coluzzii mosquito population. Cows were only used to attract mosquitoes into the huts and no tests were carried out directly on the cows. The author checklist is intended for use with studies where experiments are carried out on animals, which is why we have had such difficulty in completing this for the hut study, as many of the questions do not relate to how the cows were used
A Note on the Conditional Optimality of Chiba and Nishizeki\u27s Algorithms
Get PDFIn a seminal work, Chiba and Nishizeki [SIAM J. Comput. `85] developed subgraph listing algorithms for triangles, 4-cycle and -cliques, where The runtimes of their algorithms are parameterized by the number of edges and the arboricity of a graph. The arboricity of a graph is the minimum number of spanning forests required to cover it. Their work introduces: * A triangle listing algorithm that runs in time. * An output-sensitive 4-Cycle-Listing algorithm that lists all 4-cycles in time, where is the number of 4-cycles in the graph. * A k-Clique-Listing algorithm that runs in time, for
Despite the widespread use of these algorithms in practice, no improvements have been made over them in the past few decades. Therefore, recent work has gone into studying lower bounds for subgraph listing problems. The works of Kopelowitz, Pettie and Porat [SODA `16] and Vassilevska W. and Xu [FOCS `20] showed that the triangle-listing algorithm of Chiba and Nishizeki is optimal under the and hypotheses respectively. However, it remained open whether the remaining algorithms were optimal.
In this note, we show that in fact all the above algorithms are optimal under popular hardness conjectures. First, we show that the algorithm is tight under the hypothesis following the techniques of Jin and Xu [STOC `23], and Abboud, Bringmann and Fishcher [STOC `23] . Additionally, we show that the algorithm is essentially tight under the exact -clique hypothesis by following the techniques of Dalirooyfard, Mathialagan, Vassilevska W. and Xu [STOC `24]. These hardness results hold even when the number of 4-cycles or -cliques in the graph is small
- …
