Fully homomorphic encryption (FHE) is a powerful and widely used primitive in lots of real-world applications. Recently, Li and Micciancio [Eurocrypt'21] introduced IND-CPA-D security, which strengthens the standard IND-CPA security by allowing the attacker to access a decryption oracle for honestly generated ciphertexts. Recently, Jung et al. [CCS'24] and Checri et al. [Crypto'24] have shown that even exact FHE schemes like FHEW/TFHE/BGV/BFV may still not be IND-CPA-D secure, by exploiting the bootstrapping failure. However, such attacks can be mitigated by setting negligible bootstrapping failure probability. On the other hand, Liu and Wang [Asiacrypt'24] proposed relaxed functional bootstrapping, which has orders of magnitude performance improvement and furthermore allows a free function evaluation during bootstrapping. These efficiency advantages make it a competitive choice in many applications. In this work, we show that the underlying secret key could be recovered within 10 minutes against all existing relaxed functional bootstrapping constructions, and even within 1 minute for some of them. Moreover, our attack works even with a negligible bootstrapping failure probability. Additionally, we propose a general fix that mitigates all the existing modulus-switching-error-based attacks in the IND-CPA-D model. This is achieved by constructing a new modulus switching procedure with essentially no overhead. Lastly, we show that IND-CPA-D may not be sufficient even for passive adversary model. Thus, we extend this model to IND-CPA-D with randomness (IND-CPA-DR).

Verifiable Computation over encrypted data (VCoed) has two popular paradigms: SNARK-FHE (applying SNARKs to prove FHE operations) and FHE-SNARK (homomorphically evaluating SNARK proofs). For the existing works, FHE-SNARK has a much better efficiency compared to SNARK-FHE.

Private messaging systems that use a bulletin board, like privacy-preserving blockchains, have been a popular topic during the last couple of years. In these systems, a private message is typically posted on the board for a recipient and the privacy requirement is that no one can determine the sender and recipient of the message. Until recently, the efficiency of these recipients was not considered, and the party had to perform a naive scan of the board to retrieve their messages. More recently, works like Fuzzy Message Detection (FMD), Private Signaling (PS), and Oblivious Message Retrieval (OMR) have studied the problem of securely outsourcing the message retrieval process to an untrusted server. However, FMD only provides limited privacy guarantees, and PS and OMR greatly lack scalability. In this work, we present a new construction for private signaling which is both asymptotically superior and concretely orders of magnitude faster than all prior work while providing full privacy. Our construction makes use of a trusted execution environment (TEE) and an Oblivious RAM (ORAM) to improve the computation complexity of the server. We also improve the privacy guarantees by keeping the recipient hidden even during the retrieval of signals from the server. Furthermore, we implement a side-channel resistant prototype and show that for a server with a million recipients and ten million messages, the prototype takes less than 70 milliseconds to process a sent message and less than 6 seconds to process a retrieval request (for 100 signals) from a recipient.

Rollups are special applications on distributed state machines (aka blockchains) for which the underlying state machine only logs, but does not execute, transactions. Rollups scale throughput by using auxiliary machines that have higher throughput and lower cost of executing transactions than the underlying blockchain. State updates are periodically posted to the underlying blockchain and either verified directly through succinct cryptographic proofs (zk rollups) or can be challenged for a defined period of time in a verifiable way by third parties (optimistic rollups). However, once computation is reduced, communication quickly becomes the new bottleneck. The critical service that the underlying blockchain provides, in addition to verification, is data availability: that necessary data can always be recovered upon request. However, directly broadcasting data requires communication per participant that is linear in the data size. Verifiable information dispersal (VID) systems achieve sublinear blowup in the Ethereum's security and same participation model, where all nodes have a strong public-key identity. However, it is not known how to do so in the permissionless model (the Bitcoin model), where participants are unauthenticated and participation is dynamic. We construct a VID system that is secure under the same model as Bitcoin, with one minimal additional requirement on the existence of reliable participants. Our system uses a state machine replication (SMR) protocol (e.g., Bitcoin) as a black box, and is therefore backward compatible. We implemented the system on top of Bitcoin core with the Regression Test Network (regtest), and our analysis shows that it can reduce communication costs and latency up to more than$1, 000\times$and$10\times$, respectively, for certain parameter choices.

Private Information Retrieval (PIR) is a two player protocol where the client, given some query x ε [N], interacts with the server, which holds a N-bit string DB, in order to privately retrieve DB[x]. In this work, we focus on the single-server client-preprocessing model, initially proposed by Corrigan-Gibbs and Kogan (EUROCRYPT 2020), where the client and server first run a joint preprocessing algorithm, after which the client can retrieve elements from DB privately in time sublinear in N. Most known constructions of single-server client-preprocessing PIR follow one of two paradigms: They feature either (1) a linear-bandwidth offline phase where the client downloads the whole database from the server, or (2) a sublinear-bandwidth offline phase where however the server has to compute a large-depth (Ωλ(N)) circuit under fully-homomorphic encryption (FHE) in order to execute the preprocessing phase.

Anonymous message delivery, as in private communication and privacy-preserving blockchain applications, ought to protect recipient metadata: a message should not be inadvertently linkable to its destination. But how can messages then be delivered to each recipient, without each recipient scanning all messages? Recent work constructed Oblivious Message Retrieval (OMR) protocols that outsource this job to untrusted servers in a privacy-preserving manner.We consider the case of group messaging, where each message may have multiple recipients (e.g., in a group chat or blockchain transaction). Direct use of prior OMR protocols in the group setting increases the servers’ work linearly in the group size, rendering it prohibitively costly for large groups.We thus devise new protocols where the servers’ cost grows very slowly with the group size, while recipients’ cost is low and independent of the group size. Our approach uses Fully Homomorphic Encryption and other lattice-based techniques, building on and improving on prior work. The efficient handling of groups is attained by encoding multiple recipient-specific clues into a single polynomial or multilinear function that can be efficiently evaluated under FHE, and via preprocessing and amortization techniques.We formally study Group Oblivious Message Retrieval (GOMR) and describe corresponding GOMR protocols. Our implementation and benchmarks show, for parameters of interest, cost reductions of orders of magnitude compared to prior schemes. For example, the servers’ cost is ~$3.36 per million messages scanned, where each message may address up to 15 recipients.