I'm excited to dig into the paper! The result is really surprising. Does it imply that you could be key exchange concretely just using something like SHA and argue that its security is based on "standard assumptions" of SHA being an RO?
Or is the construction from the RO un-instantiable somehow?
Most schools have already finished accepting applications, but the door is still open to come to Stevens!! If you know anyone who already has their materials together, they have almost 2 more weeks to submit an application!
I'm looking for PhD students to join me at Stevens!! Please spread the word to anyone looking for an opportunity right across from NYC to research:
* secure data structures (e.g., PIR/ORAM)
* cryptography for AI-related applications (e.g., watermarking, steganography)
Are there good resources to understand concrete limits of steganography in terms of the entropy, false positive rates, support size, etc of both the covertext distribution and the steganographic output distribution?
Ideally, something which uses something like cryptographic syntax too
“When everything on the internet demands attention, paying attention to anything becomes impossible.” @yair-rosenberg.bsky.social unpacks one game creator’s quest to rescue the internet’s promise from its present:
What exactly is the debate over then? lol
What's the best way to get used to iO tricks in proofs? Just read a bunch of papers?
I've gotten used to some Sahai-Waters ideas, but I feel far away from being able to use iO creatively to prove something new
Is this latest achievement really such an impactful tipping point? I feel like we shouldn't consider completely shifting policy approaches until we move beyond language models as AGI candidates
I just meant the statement "Each iteration should have ~10% chance to find an unsorted pair," which I don't think it true.
My algorithm should work on that specific instance, though, because about 1/4 of the (i,j) pairs are unsorted. (I'm not picking them consecutively)
After reading the solution, I see why this doesn't work — the statement was not just not obvious, it was in fact false
Repeat k~log n times:
choose 2 random indices i < j
if a[i] > a[j] return "unsorted"
return "sorted"
I think the above would work? Each iteration should have ~10% chance to find an unsorted pair (maybe not obvious), so only error with .9^k < 1/poly(n)
If you’re curious about the design and analysis of encrypted algorithms and encrypted databases, I’m putting together a collection of resources at encryptedsystems.org
I’d be interested to see kills divided number of encounters - I feel like that’s a better gauge for what to be worried about
Abstract. In this paper, we construct new t-server Private Information Retrieval (PIR) schemes with communication complexity subpolynomial in the previously best known, for all but finitely many t. Our results are based on combining derivatives (in the spirit of Woodruff-Yekhanin) with the Matching Vector based PIRs of Yekhanin and Efremenko. Previously such a combination was achieved in an ingenious way by Dvir and Gopi, using polynomials and derivatives over certain exotic rings, en route to their fundamental result giving the first 2-server PIR with subpolynomial communication. Our improved PIRs are based on two ingredients: • We develop a new and direct approach to combine derivatives with Matching Vector based PIRs. This approach is much simpler than that of Dvir-Gopi: it works over the same field as the original PIRs, and only uses elementary properties of polynomials and derivatives. • A key subproblem that arises in the above approach is a higher-order polynomial interpolation problem. We show how “sparse S-decoding polynomials”, a powerful tool from the original constructions of Matching Vector PIRs, can be used to solve this higher-order polynomial interpolation problem using surprisingly few higer-order evaluations. Using the known sparse S-decoding polynomials in combination with our ideas leads to our improved PIRs. Notably, we get a 3-server PIR scheme with communication 2^(O^(∼)((logn)^(1/3))), improving upon the previously best known communication of $2^{O^\sim( \sqrt{\log n})}$ due to Efremenko.
Image showing part 2 of abstract.
Improved PIR Schemes using Matching Vectors and Derivatives (Fatemeh Ghasemi, Swastik Kopparty, Madhu Sudan) ia.cr/2024/1885
Are these from public posts on Venmo? I didn't think they reveal the amount of money transferred
"For decades, technologists have been making the point that the strongest and best form of communications security is provided by end-to-end encryption; it is well past time for law enforcement to embrace its widespread public use," writes Susan Landau.
That’s a cool result! Is there a bound on the runtime of the simulator in terms of the runtime of A?
i started refactoring a bunch of code and then halfway through i changed my mind - i hadn't commited 💀
👋🏻
I just recently started cryptology.city!
I think it could be a useful resource for the cryptology-curious! I drew a lot of inspiration from the Complexity Zoo, which I have personally liked.
Happy to hear ideas on how to tailor the site for crypto though!
Abstract. A zero-bit watermarked language model produces text that is indistinguishable from that of the underlying model, but which can be detected as machine-generated using a secret key. Unfortunately, merely detecting AI-generated spam, say, as watermarked may not prevent future abuses. If we could additionally trace the text to a spammer’s API token or account, we could then cut off their access or pursue legal action. We introduce multi-user watermarks, which allow tracing model-generated text to individual users or to groups of colluding users. We construct multi-user watermarking schemes from undetectable zero-bit watermarking schemes. Importantly, our schemes provide both zero-bit and multi-user assurances at the same time: detecting shorter snippets just as well as the original scheme, and tracing longer excerpts to individuals. Along the way, we give a generic construction of a watermarking scheme that embeds long messages into generated text. Ours are the first black-box reductions between watermarking schemes for language models. A major challenge for black-box reductions is the lack of a unified abstraction for robustness — that marked text is detectable even after edits. Existing works give incomparable robustness guarantees, based on bespoke requirements on the language model’s outputs and the users’ edits. We introduce a new abstraction to overcome this challenge, called AEB-robustness. AEB-robustness provides that the watermark is detectable whenever the edited text “approximates enough blocks” of model-generated output. Specifying the robustness condition amounts to defining approximates, enough, and blocks. Using our new abstraction, we relate the robustness properties of our message-embedding and multi-user schemes to that of the underlying zero-bit scheme, in a black-box way. Whereas prior works only guarantee robustness for a single text generated in response to a single prompt, our schemes are robust against adaptive prompting, a stronger and more natural adversarial model.
Image showing part 2 of abstract.
Enhancing Watermarked Language Models to Identify Users (Aloni Cohen, Alexander Hoover, Gabe Schoenbach) ia.cr/2024/759
I think proofs are great! Even from uncertain assumptions, reductions give us a better understanding of what maybe true and lets us build cool new things
If we were truly stuck waiting for proofs, cryptography wouldn't exist as it does today
Abstract. Structured Encryption (StE) enables a client to securely store and query data stored on an untrusted server. Recent constructions of StE have moved beyond basic queries, and now support large subsets of SQL. However, the security of these constructions is poorly understood, and no systematic analysis has been performed. We address this by providing the first leakage-abuse attacks against StE for SQL schemes. Our attacks can be run by a passive adversary on a server with access to some information about the distribution of underlying data, a common model in prior work. They achieve partial query recovery against select operations and partial plaintext recovery against join operations. We prove the optimality and near-optimality of two new attacks, in a Bayesian inference framework. We complement our theoretical results with an empirical investigation testing the performance of our attacks against real-world data and show they can successfully recover a substantial proportion of queries and plaintexts. In addition to our new attacks, we provide proofs showing that the conditional optimality of a previously proposed leakage-abuse attack and that inference against join operations is NP-hard in general.
Image showing part 2 of abstract.
Leakage-Abuse Attacks Against Structured Encryption for SQL (Alexander Hoover, Ruth Ng, Daren Khu, Yao'an Li, Joelle Lim, Derrick Ng, Jed Lim, Yiyang Song) ia.cr/2024/554
Exactly! The comments like the above are what came up when I was searching, but it’s not what I mean by “a signed pun”
Do users of signed languages use/have a concept similar to the spoken notion of puns? Like mixing or replacing similar signs as a joke
#linguistics
This was a cool paper to see posted! I’ve been curious about this problem for a while now, and it seems like it’s mostly solved
Abstract. We study single-server private information retrieval (PIR) where a client wishes to privately retrieve the x-th entry from a database held by a server without revealing the index x. In our work, we focus on PIR with client pre-processing where the client may compute hints during an offline phase. The hints are then leveraged during queries to obtain sub-linear online time. We present Plinko that is the first single-server PIR with client pre-processing that obtains optimal trade-offs between client storage and query time for all parameters. Our scheme uses t = Õ(n/r) query time for any client storage size r. This matches known lower bounds of r ⋅ t = Ω(n) up to logarithmic factors for all parameterizations whereas prior works could only match the lower bound when $r = \tilde{O}(\sqrt{n})$. Moreover, Plinko is also the first updateable PIR scheme where an entry can be updated in worst-case Õ(1) time. As our main technical tool, we define the notion of an invertible pseudorandom function (iPRF) that generalizes standard PRFs to be equipped with an efficient inversion algorithm. We present a construction of an iPRF from one-way functions where forward evaluation runs in Õ(1) time and inversion runs in time linear in the inverse set (output) size. Furthermore, our iPRF construction is the first that remains efficient and secure for arbitrary domain and range sizes (including small domains and ranges). In the context of single-server PIR, we show that iPRFs may be used to construct the first hint set representation where finding a hint containing an entry x may be done in Õ(1) time.
Image showing part 2 of abstract.
Plinko: Single-Server PIR with Efficient Updates via Invertible PRFs (Alexander Hoover, Sarvar Patel, Giuseppe Persiano, Kevin Yeo) ia.cr/2024/318
STOC Accepted Papers
http://acm-stoc.org/
