About

Jeremiah M. Blocki is an Associate Professor of Computer Science at Purdue University. He describes himself as a theoretical computer scientist interested in applying fundamental ideas from computer science to address practical problems in usable privacy and security. His research focuses on developing usable authentication protocols for humans, exploring ways for humans to create and remember multiple strong passwords easily, and designing secure cryptographic protocols that are simple enough to be run by humans. Additionally, he has developed algorithms for conducting privacy-preserving data analysis in various application settings, including social networks and password data. Professor Blocki completed his PhD at Carnegie Mellon University in 2014, where he worked on Usable Human Authentication under the supervision of Manuel Blum and Anupam Datta. He also spent a year as a postdoctoral researcher at Microsoft Research New England. His research contributions include work on data-independent memory hard functions, the economics of offline password cracking, and privacy-preserving data analysis, among others.

Research topics

• Computer science
• Computer security
• Theoretical computer science
• Mathematics
• Discrete mathematics

Selected publications

• Exponential Lower Bounds for 2-query Relaxed Locally Decodable Codes

  ArXiv.org · 2026-02-23

  articleOpen access

  Locally Decodable Codes (LDCs) are error-correcting codes $C\colonΣ^n\rightarrow Σ^m,$ encoding \emph{messages} in $Σ^n$ to \emph{codewords} in $Σ^m$, with super-fast decoding algorithms. They are important mathematical objects in many areas of theoretical computer science, yet the best constructions so far have codeword length $m$ that is super-polynomial in $n$, for codes with constant query complexity and constant alphabet size. In a very surprising result, Ben-Sasson, Goldreich, Harsha, Sudan, and Vadhan (SICOMP 2006) show how to construct a relaxed version of LDCs (RLDCs) with constant query complexity and almost linear codeword length over the binary alphabet, and used them to obtain significantly-improved constructions of Probabilistically Checkable Proofs. In this work, we study RLDCs in the standard Hamming-error setting. We prove an exponential lower bound on the length of Hamming RLDCs making $2$ queries (even adaptively) over the binary alphabet. This answers a question explicitly raised by Gur and Lachish (SICOMP 2021) and is the first exponential lower bound for RLDCs. Combined with the results of Ben-Sasson et al., our result exhibits a ``phase-transition''-type behavior on the codeword length for some constant-query complexity. We achieve these lower bounds via a transformation of RLDCs to standard Hamming LDCs, using a careful analysis of restrictions of message bits that fix codeword bits.

  PublisherOA PDF

• Exponential Lower Bounds for 2-query Relaxed Locally Decodable Codes

  Open MIND · 2026-02-23

  preprint

  Locally Decodable Codes (LDCs) are error-correcting codes $C\colonΣ^n\rightarrow Σ^m,$ encoding \emph{messages} in $Σ^n$ to \emph{codewords} in $Σ^m$, with super-fast decoding algorithms. They are important mathematical objects in many areas of theoretical computer science, yet the best constructions so far have codeword length $m$ that is super-polynomial in $n$, for codes with constant query complexity and constant alphabet size. In a very surprising result, Ben-Sasson, Goldreich, Harsha, Sudan, and Vadhan (SICOMP 2006) show how to construct a relaxed version of LDCs (RLDCs) with constant query complexity and almost linear codeword length over the binary alphabet, and used them to obtain significantly-improved constructions of Probabilistically Checkable Proofs. In this work, we study RLDCs in the standard Hamming-error setting. We prove an exponential lower bound on the length of Hamming RLDCs making $2$ queries (even adaptively) over the binary alphabet. This answers a question explicitly raised by Gur and Lachish (SICOMP 2021) and is the first exponential lower bound for RLDCs. Combined with the results of Ben-Sasson et al., our result exhibits a ``phase-transition''-type behavior on the codeword length for some constant-query complexity. We achieve these lower bounds via a transformation of RLDCs to standard Hamming LDCs, using a careful analysis of restrictions of message bits that fix codeword bits.

  DOI

• Amortized Locally Decodable Codes for Insertions and Deletions

  ArXiv.org · 2025-01-01

  preprintOpen access1st authorCorresponding

  Locally Decodable Codes (LDCs) are error correcting codes which permit the recovery of any single message symbol with a low number of queries to the codeword (the locality). Traditional LDC tradeoffs between the rate, locality, and error tolerance are undesirable even in relaxed settings where the encoder/decoder share randomness or where the channel is resource-bounded. Recent work by Blocki and Zhang initiated the study of Hamming amortized Locally Decodable Codes (aLDCs), which allow the local decoder to amortize their number of queries over the recovery of a small subset of message symbols. Surprisingly, Blocki and Zhang construct asymptotically ideal (constant rate, constant amortized locality, and constant error tolerance) Hamming aLDCs in private-key and resource-bounded settings. While this result overcame previous barriers and impossibility results for Hamming LDCs, it is not clear whether the techniques extend to Insdel LDCs. Constructing Insdel LDCs which are resilient to insertion and/or deletion errors is known to be even more challenging. For example, Gupta (STOC'24) proved that no Insdel LDC with constant rate and error tolerance exists even in relaxed settings. Our first contribution is to provide a Hamming-to-Insdel compiler which transforms any amortized Hamming LDC that satisfies a particular property (consecutive interval querying) to amortized Insdel LDC while asymptotically preserving the rate, error tolerance and amortized locality. Prior Hamming-to-Insdel compilers of Ostrovsky and Paskin-Cherniavsky (ICITS'15) and Block et al. (FSTTCS'20) worked for arbitrary Hamming LDCs, but incurred an undesirable polylogarithmic blow-up in the locality. Our second contribution is a construction of an ideal amortized Hamming LDC which satisfies our special property (consecutive interval querying) in the relaxed settings where the sender/receiver share randomness or where the channel is resource bounded. Taken together, we obtain ideal Insdel aLDCs in private-key and resource-bounded settings with constant amortized locality, constant rate and constant error tolerance. This result is surprising in light of Gupta’s (STOC'24) impossibility result which demonstrates a strong separation between locality and amortized locality for Insdel LDCs.

  PublisherOA PDFDOI

• The Impact of Reversibility on Parallel Pebbling

  Lecture notes in computer science · 2025-01-01

  book-chapter1st authorCorresponding
  PublisherDOI

• Amortized Locally Decodable Codes

  arXiv (Cornell University) · 2025-02-14

  preprintOpen access1st authorCorresponding

  Locally Decodable Codes (LDCs) are error correcting codes that admit efficient decoding of individual message symbols without decoding the entire message. Unfortunately, known LDC constructions offer a sub-optimal trade-off between rate, error tolerance and locality, the number of queries that the decoder must make to the received codeword $\tilde {y}$ to recovered a particular symbol from the original message $x$, even in relaxed settings where the encoder/decoder share randomness or where the channel is resource bounded. We initiate the study of Amortized Locally Decodable Codes where the local decoder wants to recover multiple symbols of the original message $x$ and the total number of queries to the received codeword $y$ can be amortized by the total number of message symbols recovered. We demonstrate that amortization allows us to overcome prior barriers and impossibility results. We first demonstrate that the Hadamard code achieves amortized locality below $2$ -- a result that is known to be impossible without amortization. Second, we study amortized locally decodable codes in cryptographic settings where the sender and receiver share a secret key or where the channel is resource-bounded and where the decoder wants to recover a consecutive subset of message symbols $[L,R]$. In these settings we show that it is possible to achieve a trifecta: constant rate, error tolerance and constant amortized locality.

  PublisherOA PDFDOI

• A Tight Lower Bound on the TdScrypt Trapdoor Memory-Hard Function

  IACR Communications in Cryptology · 2025-10-06 · 1 citations

  articleOpen access1st authorCorresponding

  A trapdoor Memory-Hard Function is a function that is memory-hard to evaluate for any party who does not have a trapdoor, but is substantially less expensive to evaluate with the trapdoor. Biryukov and Perrin (Asiacrypt 2017) introduced the first candidate trapdoor Memory-Hard Function called Diodon, which modifies a Memory-Hard Function called Scrypt by replacing a hash chain with repeated squaring modulo a composite number N=pq. The trapdoor, which consists of the prime factors p and q, allows one to compute the function with significantly reduced cumulative memory cost (CMC) O(n*log n*(log N)^2) where n denotes the running time parameter, e.g., the length of the hash chain or repeated squaring chain. By contrast, the best-known algorithm to compute Diodon without the trapdoor has the CMC O(n^2*log N). Auerbach et al. (Eurocrypt 2024) provided the first provable lower bound on the CMC of TdScrypt — a specific instantiation of Diodon. In particular, in idealized models, they proved that the CMC of TdScrypt is Omega(n^2*log N/(log n)) which almost matches the upper bound O(n^2*log N) but is off by a multiplicative log n factor. In this work, we show how to tighten the analysis of Auerbach et al. (Eurocrypt 2024) and eliminate the gap. In particular, our results imply that TdScrypt has the CMC at least Omega(n^2*log N).

  PublisherOA PDFDOI

• Differentially Private Compression and the Sensitivity of LZ77

  Lecture notes in computer science · 2025-12-04

  book-chapter1st authorCorresponding
  PublisherDOI

• Differentially Private Compression and the Sensitivity of LZ77

  ArXiv.org · 2025-02-13 · 1 citations

  preprintOpen access1st authorCorresponding

  We initiate the study of differentially private data-compression schemes motivated by the insecurity of the popular "Compress-Then-Encrypt" framework. Data compression is a useful tool which exploits redundancy in data to reduce storage/bandwidth when files are stored or transmitted. However, if the contents of a file are confidential then the length of a compressed file might leak confidential information about the content of the file itself. Encrypting a compressed file does not eliminate this leakage as data encryption schemes are only designed to hide the content of confidential message instead of the length of the message. In our proposed Differentially Private Compress-Then-Encrypt framework, we add a random positive amount of padding to the compressed file to ensure that any leakage satisfies the rigorous privacy guarantee of $(ε,δ)$-differential privacy. The amount of padding that needs to be added depends on the sensitivity of the compression scheme to small changes in the input, i.e., to what degree can changing a single character of the input message impact the length of the compressed file. While some popular compression schemes are highly sensitive to small changes in the input, we argue that effective data compression schemes do not necessarily have high sensitivity. Our primary technical contribution is analyzing the fine-grained sensitivity of the LZ77 compression scheme (IEEE Trans. Inf. Theory 1977) which is one of the most common compression schemes used in practice. We show that the global sensitivity of the LZ77 compression scheme has the upper bound $O(W^{2/3}\log n)$ where $W\leq n$ denotes the size of the sliding window. When $W=n$, we show the lower bound $Ω(n^{2/3}\log^{1/3}n)$ for the global sensitivity of the LZ77 compression scheme which is tight up to a sublogarithmic factor.

  PublisherOA PDFDOI

• Provably Memory-Hard Proofs of Work with Memory-Easy Verification

  Lecture notes in computer science · 2025-12-04

  book-chapter1st authorCorresponding
  PublisherDOI

• Towards Practical Data-Dependent Memory-Hard Functions with Optimal Sustained Space Trade-offs in the Parallel Random Oracle Model

  ArXiv.org · 2025-08-09

  preprintOpen access1st authorCorresponding

  Memory-Hard Functions (MHF) are a useful cryptographic primitive to build egalitarian proofs-of-work and to help protect low entropy secrets (e.g., user passwords) against brute-forces attacks. Ideally, we would like for a MHF to have the property that (1) an honest party can evaluate the function in sequential time $Ω(N)$, and (2) any parallel party that evaluates the function is forced to lockup $Ω(N)$ memory for $Ω(N)$ sequential steps. Unfortunately, this goal is not quite achievable, so prior work of Blocki and Holman [BH22] focused on designing MHFs with strong tradeoff guarantees between sustained-space complexity (SSC) and cumulative memory costs (CMC). However, their theoretical construction is not suitable for practical deployment due to the reliance on expensive constructions of combinatorial graphs. Furthermore, there is no formal justification for the heuristic use of the dynamic pebbling game in MHF analysis so we cannot rule out the possibility that there are more efficient attacks in the Parallel Random Oracle Model (PROM). Towards the goal of developing a practical MHF with provably strong SSC/CMC tradeoffs we develop a new MHF called EGSample which does not rely on expensive combinatorial constructions like [BH22]. In the dynamic pebbling model, we prove equivalent SSC/CMC tradeoffs for EGSample i.e., any the dynamic pebbling strategy either (1) locks up $Ω(N)$ memory for $Ω(N)$ steps, or (2) incurs cumulative memory cost at least $Ω(N^{3-ε})$. We also develop new techniques to directly establish SSC/CMC tradeoffs in the parallel random oracle model. In particular, we prove that {\em any} PROM algorithm evaluating our MHF either (1) locks up $Ω(N)$ blocks of memory for $Ω(N)$ steps or (2) incurs cumulative memory cost at least $Ω(N^{2.5-ε})$.

  PublisherOA PDFDOI

Recent grants

• CRII: SaTC: Towards the Development of Stronger Memory-Hard Functions for Secure Password Hashing

  NSF · $183k · 2018–2020

• CAREER: Cryptographic Tools for Usable Human Authentication

  NSF · $592k · 2021–2027

Frequent coauthors

• Anupam Datta

  37 shared

• Samson Zhou

  24 shared

• Arunesh Sinha

  Rutgers, The State University of New Jersey

  19 shared

• Nicolas Christin

  Carnegie Mellon University

  17 shared

• Elena Grigorescu

  Purdue University West Lafayette

  14 shared

• Seunghoon Lee

  13 shared

• Joël Alwen

  12 shared

• Benjamin Harsha

  11 shared

Education

• PhD, Computer Science Department

  Carnegie Mellon University

  2014