References

A

[CP07] Y. Chen and J. Flum. On parameterized path and chordless path problems., Proceedings of the IEEE Conference on Computational Complexity 2007, 250-263.

B

[BMZ19] J. Bartusek, F. Ma, and M. Zhandry. The Distinction Between Fixed and Random Generators in Group-Based Assumptions, CRYPTO, 2019. https://www.iacr.org/archive/crypto2019/116940274/116940274.pdf

C

[CDH20] D. Cash, A. Drucker, and A. Hoover. A Lower Bound for One-Round Oblivious RAM, TCC, 2020. https://eprint.iacr.org/2020/1195

[CHNVW16] A. Cohen, J. Holmgren, R. Nishimaki, V. Vaikuntanathan, and D. Wichs. Watermarking Cryptographic Capabilities, STOC, Pages 1115--1127, 2016. https://doi.org/10.1145/2897518.2897651

[CHS24] S. Cohen, A. Hoover, and G. Schoenbach. Watermarking Language Models for Many Adaptive Users, Preprint, . https://eprint.iacr.org/2024/759

D

[DH76] W. Diffie and M. E. Hellman. New Directions in Cryptography, IEEE Transactions on Information Theory, . https://ieeexplore.ieee.org/document/1055638

[DMO00] G. Di Crescenzo, T. Malkin, and R. Ostrovsky. Single Database Private Information Retrieval Implies Oblivious Transfer, EUROCRYPT, Pages 122--138, 2000. https://doi.org/10.1007/3-540-45539-6_10

E

[Elg85] T. ElGamal. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithm, IEEE Transactions on Information Theory, . https://ieeexplore.ieee.org/abstract/document/1057074

G

[GGM84] O. Goldreich, S. Goldwasser, and S. Micali. How to Construct Random Functions (Extended Abstract), FOCS, Pages 464--479, 1984. https://dl.acm.org/doi/abs/10.1145/6490.6503

[GO96] O. Goldreich and R. Ostrovsky. Software Protection and Simulation on Oblivious RAMs, Journal of the ACM (JACM), Volume 43, Number 3, Pages 431--473, 1996. https://doi.org/10.1145/233551.233553

H

[HILL99] J. Håstad, R. Impagliazzo, L. A. Levin, and M. Luby. A Pseudorandom Generator from any One-way Function, SIAM Journal on Computing, Volume 28, Number 4, Pages 1364--1396, 1999.

[HPPY24] A. Hoover, S. Patel, G. Persiano, and K. Yeo. Plinko: Single-Server PIR with Efficient Updates via Invertible PRFs, Preprint, . https://eprint.iacr.org/2024/318

K

[KO00] E. Kushilevitz and R. Ostrovsky. One-Way Trapdoor Permutations Are Sufficient for Non-trivial Single-Server Private Information Retrieval, EUROCRYPT, Pages 104--121, 2000. https://doi.org/10.1007/3-540-45539-6_9

L

[LR88] M. Luby and C. Rackoff. How to Construct Pseudorandom Permutations from Pseudorandom Functions, SIAM Journal on Computing, Volume 17, Number 2, 1988.

R

[RSA78] R. L. Rivest, A. Shamir, and L. M. Adleman. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, Communications of the ACM, Volume 21, Issue 2, . https://dl.acm.org/doi/10.1145/359340.359342

S

[Sho94] P. W. Shor. Algorithms for quantum computation: discrete logarithms and factoring, Proceedings 35th annual symposium on foundations of computer science, . https://ieeexplore.ieee.org/abstract/document/365700

[Sho97] V. Shoup. Lower Bounds for Discrete Logarithms and Related Problems, EUROCRYPT, 1997. https://link.springer.com/chapter/10.1007/3-540-69053-0_18