One of the central questions in Cryptography today is proving security of the protocols ``on the Internet'', i.e., in a concurrent setting where there are multiple interactions between players, and where the adversary can play so called ``man-in-the-middle'' attacks, forwarding and modifying messages between two or more unsuspecting players. Indeed, ... more >>>

Boolean satisfiability problems are an important benchmark for questions about complexity, algorithms, heuristics and threshold phenomena. Recent work on heuristics, and the satisfiability threshold has centered around the structure and connectivity of the solution space. Motivated by this work, we study structural and connectivity-related properties of the space of solutions ... more >>>

We explicitly show the upper bound on the round complexity for perfectly concealing bit commitment schemes based on the general computational assumption. The best known scheme in the literature is the one-way permutation based scheme due to Naor, Ostrovsky, Venkatesan and Yung and its round complexity is O(n). We consider ... more >>>