Hapening now! Charles River Crypto Day on Friday, March 10 @ BU
Ran Canetti
https://bostonu.zoom.us/j/94422838785?pwd=M1F3K0lBU0d0RExRQ2RXQjVLK3liZz09 <https://www.google.com/url?q=https://bostonu.zoom.us/j/94422838785?pwd%3DM1F3K0lBU0d0RExRQ2RXQjVLK3liZz09&sa=D&source=calendar&ust=1678825014698954&usg=AOvVaw1XhitzO1kZEAZCMLChJ61U>
Ran
When: Friday, Mar 10.
Where: 17th floor seminar room at BU’s new Center for Computing and Data Sciences, 665 Commonwealth Ave, Boston MA 02215.
Organizers: Ran Canetti, Henry Corrigan-Gibbs, Yael Kalai, Vinod Vaikuntanathan and Daniel Wichs
Program:
| 9:30 – 10:00 | Welcome and Breakfast |
| 10:00 – 11:00 | Eran Tromer (Columbia) Oblivious Message Retrieval |
| 11:30 – 12:20 | Noga Amit (Weizmann) Constant-round Arguments from One-way Functions |
| 12:30 – 2:00 | Lunch (provided) |
| 2:00 – 3:00 | Jiahui Liu (UT Austin) Collusion-Resistant Copy-Protection for Watermarkable Functionalities |
| 3:30 – 4:30 | James Bartusek (UC Berkeley) Obfuscation of Pseudo-Deterministic Quantum Circuits |
Speaker: Eran Tromer (Columbia)
Title: Oblivious Message Retrieval
Abstract:
Anonymous message delivery systems, such as private messaging services and privacy-preserving blockchains, need a mechanism for recipients to retrieve the messages addressed to them, without leaking metadata or letting their messages be linked. Recipients could download all posted messages and scan for those addressed to them, but communication and computation costs are excessive at scale.
We show how untrusted servers can detect messages on behalf of recipients, and summarize these into a compact encrypted digest that recipients can easily decrypt. These servers operate obliviously and do not learn anything about which messages are addressed to which recipients. Privacy, soundness, and completeness hold even if everyone but the recipient is adversarial and colluding.
Furthermore, the model and constructions generalize to the setting of group messaging or mailing lists: senders can generate messages that would be efficiently detected by multiple recipients of their choice.
Our starting point is an asymptotically-efficient approach, using Fully Homomorphic Encryption and homomorphically-encoded Sparse Random Linear Codes. We then address the concrete performance using bespoke tailoring of lattice-based cryptographic components, alongside various algebraic and algorithmic optimizations. This reduces the digest size to a few bits per message scanned. Concretely, the servers’ cost is ~$1 per million messages scanned, and the resulting digests can be decoded by recipients in ~20ms. Our schemes can thus practically attain the strongest form of receiver privacy for current applications such as privacy-preserving cryptocurrencies.
(Covers https://eprint.iacr.org/2021/1256 and ongoing work.)
Speaker: Noga Amit (Weizmann)
Title: Constant-round Arguments from One-way Functions
Abstract: We study the following question: what cryptographic assumptions are needed for obtaining constant-round computationally-sound argument systems? We focus on argument systems with almost-linear verification time for subclasses of P, such as depth-bounded computations. Kilian’s celebrated work [STOC 1992] provides such 4-message arguments for P (actually, for NP) using collision-resistant hash functions. We show that one-way functions suffice for obtaining constant-round arguments of almost-linear verification time for languages in P that have log-space uniform circuits of linear depth and polynomial size. More generally, the complexity of the verifier scales with the circuit depth. Furthermore, our argument systems (like Kilian’s) are doubly-efficient; that is, the honest prover strategy can be implemented in polynomial-time. Unconditionally sound interactive proofs for this class of computations do not rely on any cryptographic assumptions, but they require a linear number of rounds [Goldwasser, Kalai and Rothblum, STOC 2008]. Constant-round interactive proof systems of linear communication (or verification) complexity are not known even for NC (indeed, even for AC^1).
Based on joint work with Guy Rothblum.
Speaker: Jiahui Liu (UT Austin)
Title: Collusion-Resistant Copy-Protection for Watermarkable Functionalities
Abstract: Copy-protection is the task of encoding a program into a quantum state to prevent illegal duplications. A line of recent works studied copy-protection schemes under “1 -> 2 attacks”: the adversary receiving one program copy can not produce two valid copies. However, under most circumstances, vendors need to sell more than one copy of a program and still ensure that no duplicates can be generated. In this work, we initiate the study of collusion resistant copy-protection in the plain model. Our results are twofold:
(*) The feasibility of copy-protecting all watermarkable functionalities is an open question raised by Aaronson et al. (CRYPTO’ 21). In the literature, watermarking decryption, digital signature schemes and PRFs have been extensively studied. For the first time, we show that digital signature schemes can be copy-protected. Together with the previous work on copy-protection of decryption and PRFs by Coladangelo et al. (CRYPTO’ 21), it suggests that many watermarkable functionalities can be copy-protected, partially answering the above open question by Aaronson et al.
(*) We make all the above schemes (copy-protection of decryption, digital signatures, and PRFs) k bounded collusion resistant for any polynomial k, giving the first bounded collusion resistant copy-protection for various functionalities in the plain model.
Speaker: James Bartusek (UC Berkeley)
Title: Obfuscation of Pseudo-Deterministic Quantum Circuits
Abstract: We will show how to obfuscate pseudo-deterministic quantum circuits in the classical oracle model, assuming the quantum hardness of learning with errors. Instantiating the classical oracle with a candidate post-quantum indistinguishability obfuscator, we obtain the first candidate construction of indistinguishability obfuscation for a class of circuits that is powerful enough to implement Shor’s algorithm.
Along the way, we construct a publicly-verifiable classical verification of quantum computation scheme for quantum “partitioning” circuits, which can be used to verify the evaluation procedure of Mahadev’s quantum fully-homomorphic encryption scheme. We achieve this by constructing a type of publicly-decodable “Pauli functional commitment” scheme, which must satisfy a notion of binding against committers that have access to both of the receiver’s standard and Hadamard basis decoding functionalities.
Based on joint work with Fuyuki Kitagawa, Ryo Nishimaki, and Takashi Yamakawa.
You received this message because you are subscribed to the Google Groups "Charles River Crypto Day" group.
To unsubscribe from this group and stop receiving emails from it, send an email to charles-river-cryp...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/charles-river-crypto-day/CAHpnE7Y2Cbou5Ekg2nUmbT%2B_hg3%2BdA%3DjKcDUv7zCL2iMRTO90A%40mail.gmail.com.
_______________________________________________
Busec mailing list
Bu...@cs-mailman.bu.edu
https://cs-mailman.bu.edu/mailman/listinfo/busec