Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

Free, publiclyaccessible full text available July 1, 2023

Locally Decodable Codes (LDCs) are errorcorrecting codes for which individual message symbols can be quickly recovered despite errors in the codeword. LDCs for Hamming errors have been studied extensively in the past few decades, where a major goal is to understand the amount of redundancy that is necessary and sufficient to decode from large amounts of error, with small query complexity. Despite exciting progress, we still don't have satisfactory answers in several important parameter regimes. For example, in the case of 3query LDCs, the gap between existing constructions and lower bounds is superpolynomial in the message length. In this work we study LDCs for insertion and deletion errors, called Insdel LDCs. Their study was initiated by Ostrovsky and PaskinCherniavsky (Information Theoretic Security, 2015), who gave a reduction from Hamming LDCs to Insdel LDCs with a small blowup in the code parameters. On the other hand, the only known lower bounds for Insdel LDCs come from those for Hamming LDCs, thus there is no separation between them. Here we prove new, strong lower bounds for the existence of Insdel LDCs. In particular, we show that 2query linear Insdel LDCs do not exist, and give an exponential lower bound for the lengthmore »

Berenbrink, Petra and (Ed.)A directed acyclic graph G = (V,E) is said to be (e,d)depth robust if for every subset S ⊆ V of S ≤ e nodes the graph GS still contains a directed path of length d. If the graph is (e,d)depthrobust for any e,d such that e+d ≤ (1ε)V then the graph is said to be εextreme depthrobust. In the field of cryptography, (extremely) depthrobust graphs with low indegree have found numerous applications including the design of sidechannel resistant MemoryHard Functions, Proofs of Space and Replication and in the design of Computationally Relaxed Locally Correctable Codes. In these applications, it is desirable to ensure the graphs are locally navigable, i.e., there is an efficient algorithm GetParents running in time polylogV which takes as input a node v ∈ V and returns the set of v’s parents. We give the first explicit construction of locally navigable εextreme depthrobust graphs with indegree O(log V). Previous constructions of εextreme depthrobust graphs either had indegree ω̃(log² V) or were not explicit.

The Schnorr signature scheme is an efficient digital signature scheme with short signature lengths, i.e., $4k$bit signatures for $k$ bits of security. A Schnorr signature $\sigma$ over a group of size $p\approx 2^{2k}$ consists of a tuple $(s,e)$, where $e \in \{0,1\}^{2k}$ is a hash output and $s\in \mathbb{Z}_p$ must be computed using the secret key. While the hash output $e$ requires $2k$ bits to encode, Schnorr proposed that it might be possible to truncate the hash value without adversely impacting security. In this paper, we prove that \emph{short} Schnorr signatures of length $3k$ bits provide $k$ bits of multiuser security in the (Shoup's) generic group model and the programmable random oracle model. We further analyze the multiuser security of keyprefixed short Schnorr signatures against preprocessing attacks, showing that it is possible to obtain secure signatures of length $3k + \log S + \log N$ bits. Here, $N$ denotes the number of users and $S$ denotes the size of the hint generated by our preprocessing attacker, e.g., if $S=2^{k/2}$, then we would obtain secure $3.75k$bit signatures for groups of up to $N \leq 2^{k/4}$ users. Our techniques easily generalize to several other FiatShamirbased signature schemes, allowing us to establish analogousmore »

Mikołaj Boja´nczyk, Emanuela Merelli (Ed.)We initiate a systematic study of algorithms that are both differentiallyprivate and run in sublinear time for several problems in which the goal is to estimate natural graph parameters. Our main result is a differentiallyprivate $(1+\rho)$approximation algorithm for the problem of computing the average degree of a graph, for every $\rho>0$. The running time of the algorithm is roughly the same (for sparse graphs) as its nonprivate version proposed by Goldreich and Ron (Sublinear Algorithms, 2005). We also obtain the first differentiallyprivate sublineartime approximation algorithms for the maximum matching size and the minimum vertex cover size of a graph. An overarching technique we employ is the notion of \emph{coupled global sensitivity} of randomized algorithms. Related variants of this notion of sensitivity have been used in the literature in adhoc ways. Here we formalize the notion and develop it as a unifying framework for privacy analysis of randomized approximation algorithms.

We formally introduce, define, and construct {\em memoryhard puzzles}. Intuitively, for a difficulty parameter $t$, a cryptographic puzzle is memoryhard if any parallel random access machine (PRAM) algorithm with ``small'' cumulative memory complexity ($\ll t^2$) cannot solve the puzzle; moreover, such puzzles should be both ``easy'' to generate and be solvable by a sequential RAM algorithm running in time $t$. Our definitions and constructions of memoryhard puzzles are in the standard model, assuming the existence of indistinguishability obfuscation (\iO) and oneway functions (OWFs), and additionally assuming the existence of a {\em memoryhard language}. Intuitively, a language is memoryhard if it is undecidable by any PRAM algorithm with ``small'' cumulative memory complexity, while a sequential RAM algorithm running in time $t$ can decide the language. Our definitions and constructions of memoryhard objects are the first such definitions and constructions in the standard model without relying on idealized assumptions (such as random oracles). We give two applications which highlight the utility of memoryhard puzzles. For our first application, we give a construction of a (onetime) {\em memoryhard function} (MHF) in the standard model, using memoryhard puzzles and additionally assuming \iO and OWFs. For our second application, we show any cryptographic puzzle (\eg,more »

We construct locally decodable codes (LDCs) to correct insertiondeletion errors in the setting where the sender and receiver share a secret key or where the channel is resourcebounded. Our constructions rely on a socalled ``HammingtoInsDel'' compiler (Ostrovsky and PaskinCherniavsky, ITS '15 \& Block et al., FSTTCS '20), which compiles any locally decodable Hamming code into a locally decodable code resilient to insertiondeletion (InsDel) errors. While the compilers were designed for the classical coding setting, we show that the compilers still work in a secret key or resourcebounded setting. Applying our results to the private key Hamming LDC of Ostrovsky, Pandey, and Sahai (ICALP '07), we obtain a private key InsDel LDC with constant rate and polylogarithmic locality. Applying our results to the construction of Blocki, Kulkarni, and Zhou (ITC '20), we obtain similar results for resourcebounded channels; i.e., a channel where computation is constrained by resources such as space or time.