Crypto rebuttal maximum word count: 1000 words

total word count of detailed review text from the three reviews: 386 words.

Why do we even care?

Partition V into sets A and B as follows: for each vertex v, independently toss a coin, put it in A if head (v in A w.p. 1/2). So for each edge (x,y), Prob[(x,y) is a cut edge]=1/2. Hence expected number of cut edge would be |E|/2. This implies, there exists a partitioning which achieves this.

A very polite reminder. Please consider a post on the lower bound technique, when you have time.

Abstract. A recent work by Boneh, Partap, and Rotem [Crypto’24] introduced the concept of traceable threshold encryption, in that if t or more parties collude to construct a decryption box, which performs decryptions, then at least one party’s identity can be traced by making a few black-box queries to the box. This has important applications, e.g., in blockchain mempool privacy, where collusion yields high financial gain through MEVs without any consequence - the possibility of tracing discourages collusion. Nevertheless, their definitions leave room for exploitation as they only achieve CPA security and do not consider inconsistency in decryption via different participating sets. This paper proposes stronger definitions of traceable threshold encryption, which supports CCA-security and consistency. Our main approach considers identity-based variants of traceable encryption (which we also define). It converts that to a CCA-secure construction, adapting two generic transformations, first using a one-time signature and then a fingerprinting code. We put forward two efficient instantiations of our identity-based scheme with different merits: our first construction is based on Boneh-Franklin IBE [Crypto’01] and has constant size ciphertexts but quadratic size public keys - this is proven secure based on XDH and BDDH. Our second construction is based on Boneh-Boyen IBE [Eurocrypt’04]. It supports both constant-size ciphertexts and constant-size public keys - this is proven secure based on a variant of the uber assumption over bilinear pairings. Our concrete analysis shows that the first construction’s ciphertext is much (~6x) smaller than the second construction. Finally, we extend the definitions to support consistency and achieve it by adjoining an efficient, non-interactive proof of correct encryption.

Image showing part 2 of abstract.

CCA-Secure Traceable Threshold (ID-based) Encryption and Application (Rishiraj Bhattacharyya, Jan Bormet, Sebastian Faust, Pratyay Mukherjee, Hussien Othman) ia.cr/2025/341

oops! :-)

Find the median (O(n)) set the two halfs (O(n)), and recurse on the appropriate half (T(n/2)) with adjusted total capacity.

there should be an ATM betweem exit 3 and exit 4 inside the terminal..near the red dots. Please ask a security person at the gates, and they should let you in.

I remember, I had a scary introduction to real analysis that made me question my calculus understanding, prompting me to avoid them whenever I could. Perhaps similar things happened to them?