1,720,963 research outputs found
MacORAMa: Optimal Oblivious RAM with Integrity
Get PDFOblivious RAM (ORAM), introduced by Goldreich and Ostrovsky (J. ACM `96), is a primitive that allows a client to perform RAM computations on an external database without revealing any information through the access pattern. For a database of size , well-known lower bounds show that a multiplicative overhead of in the number of RAM queries is necessary assuming client storage. A long sequence of works culminated in the asymptotically optimal construction of Asharov, Komargodski, Lin, and Shi (CRYPTO `21) with worst-case overhead and client storage. However, this optimal ORAM is known to be secure only in the honest-but-curious setting, where an adversary is allowed to observe the access patterns but not modify the contents of the database. In the malicious setting, where an adversary is additionally allowed to tamper with the database, this construction and many others in fact become insecure.
In this work, we construct the first maliciously secure ORAM with worst-case overhead and client storage assuming one-way functions, which are also necessary. By the lower bound, our construction is asymptotically optimal. To attain this overhead, we develop techniques to intricately interleave online and offline memory checking for malicious security. Furthermore, we complement our positive result by showing the impossibility of a generic overhead-preserving compiler from honest-but-curious to malicious security, barring a breakthrough in memory checking
Symmetric Perceptrons, Number Partitioning and Lattices
Get PDFThe symmetric binary perceptron () problem with parameter is an average-case search problem defined as follows: given a random Gaussian matrix as input where , output a vector such that
The number partitioning problem () corresponds to the special case of setting . There is considerable evidence that both problems exhibit large computational-statistical gaps.
In this work, we show (nearly) tight average-case hardness for these problems, assuming the worst-case hardness of standard approximate shortest vector problems on lattices.
For , statistically, solutions exist with (Aubin, Perkins and Zdeborova, Journal of Physics 2019). For large , the best that efficient algorithms have been able to achieve is a far cry from the statistical bound, namely (Bansal and Spencer, Random Structures and Algorithms 2020). The problem has been extensively studied in the TCS and statistics communities, and Gamarnik, Kizildag, Perkins and Xu (FOCS 2022) conjecture that Bansal-Spencer is tight: namely, is the optimal value achieved by computationally efficient algorithms.
We prove their conjecture assuming the worst-case hardness of approximating the shortest vector problem on lattices.
For , statistically, solutions exist with (Karmarkar, Karp, Lueker and Odlyzko, Journal of Applied Probability 1986). Karmarkar and Karp\u27s classical differencing algorithm achieves
We prove that Karmarkar-Karp is nearly tight: namely, no polynomial-time algorithm can achieve , once again assuming the worst-case subexponential hardness of approximating the shortest vector problem on lattices to within a subexponential factor.
Our hardness results are versatile, and hold with respect to different distributions of the matrix (e.g., i.i.d. uniform entries from ) and weaker requirements on the solution vector
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
Average-Case Hardness of NP and PH from Worst-Case Fine-Grained Assumptions
Get PDFWhat is a minimal worst-case complexity assumption that implies non-trivial average-case hardness of NP or PH? This question is well motivated by the theory of fine-grained average-case complexity and fine-grained cryptography. In this paper, we show that several standard worst-case complexity assumptions are sufficient to imply non-trivial average-case hardness of NP or PH:
- NTIME[n] cannot be solved in quasi-linear time on average if UP ̸ ⊆ DTIME[2^{Õ(√n)}].
- Σ₂TIME[n] cannot be solved in quasi-linear time on average if Σ_kSAT cannot be solved in time 2^{Õ(√n)} for some constant k. Previously, it was not known if even average-case hardness of Σ₃SAT implies the average-case hardness of Σ₂TIME[n].
- Under the Exponential-Time Hypothesis (ETH), there is no average-case n^{1+ε}-time algorithm for NTIME[n] whose running time can be estimated in time n^{1+ε} for some constant ε > 0.
Our results are given by generalizing the non-black-box worst-case-to-average-case connections presented by Hirahara (STOC 2021) to the settings of fine-grained complexity. To do so, we construct quite efficient complexity-theoretic pseudorandom generators under the assumption that the nondeterministic linear time is easy on average, which may be of independent interest
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
Memory Checking Requires Logarithmic Overhead
Get PDFWe study the complexity of memory checkers with computational security and prove the first general tight lower bound.
Memory checkers, first introduced over 30 years ago by Blum, Evans, Gemmel, Kannan, and Naor (FOCS \u2791, Algorithmica \u2794), allow a user to store and maintain a large memory on a remote and unreliable server by using small trusted local storage. The user can issue instructions to the server and after every instruction, obtain either the correct value or a failure (but not an incorrect answer) with high probability. The main complexity measure of interest is the size of the local storage and the number of queries the memory checker makes upon every logical instruction. The most efficient known construction has query complexity and local space proportional to a computational security parameter, assuming one-way functions, where is the logical memory size. Dwork, Naor, Rothblum, and Vaikuntanathan (TCC \u2709) showed that for a restricted class of ``deterministic and non-adaptive\u27\u27 memory checkers, this construction is optimal, up to constant factors. However, going beyond the small class of deterministic and non-adaptive constructions has remained a major open problem.
In this work, we fully resolve the complexity of memory checkers by showing that any construction with local space and query complexity must satisfy
This implies, as a special case, that in any scheme, assuming that for . The bound applies to any scheme with computational security, completeness , and inverse polynomial in soundness (all of which make our lower bound only stronger). We further extend the lower bound to schemes where the read complexity and write complexity differ. For instance, we show the tight bound that if and for , then . This is the first lower bound, for any non-trivial class of constructions, showing a read-write query complexity trade-off.
Our proof is via a delicate compression argument showing that a ``too good to be true\u27\u27 memory checker can be used to compress random bits of information. We draw inspiration from tools recently developed for lower bounds for relaxed locally decodable codes. However, our proof itself significantly departs from these works, necessitated by the differences between settings
Indistinguishability Obfuscation from Bilinear Maps and LPN Variants
Get PDFWe construct an indistinguishability obfuscation (IO) scheme from the sub-exponential hardness of the decisional linear problem on bilinear groups together with two variants of the learning parity with noise (LPN) problem, namely large-field LPN and (binary-field) sparse LPN. This removes the need to assume the existence pseudorandom generators (PRGs) in with polynomial stretch from the state-of-the-art construction of IO (Jain, Lin, and Sahai, EUROCRYPT 2022). As an intermediate step in our construction, we abstract away a notion of structured-seed polynomial-stretch PRGs in which suffices for IO and is implied by both sparse LPN and the existence of polynomial-stretch PRGs in .
As immediate applications, from the sub-exponential hardness of the decisional linear assumption on bilinear groups, large-field LPN, and sparse LPN, we get alternative constructions of (a) fully homomorphic encryption (FHE) without lattices or circular security assumptions (Canetti, Lin, Tessaro, and Vaikuntanathan, TCC 2015), and (b) perfect zero-knowledge adaptively-sound succinct non-interactive arguments (SNARGs) for NP (Waters and Wu, STOC 2024)
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
- …
