This paper investigates an adversarial model in the scenario of private information retrieval (PIR) from n coded storage servers, called Byzantine adversary. The Byzantine adversary is defined as the one altering b server responses and erasing u server responses to a user's query. In this paper, two types of Byzantine adversaries are considered; 1) the classic omniscient type that has the full knowledge on n servers as considered in existing literature, and 2) the reasonable limited-knowledge type that has information on only b+u servers, i.e., servers under the adversary's control. For these two types, this paper reveals that the resistance of a PIR scheme, i.e., the condition of b and u to correctly obtain the desired message, can be expressed in terms of a code parameter called the coset distance of linear codes employed in the scheme. For the omniscient type, the derived condition expressed by the coset distance is tighter and more precise than the estimation of the resistance by the minimum Hamming weight of the codes considered in existing researches. Furthermore, this paper also clarifies that if the adversary is limited-knowledge, the resistance of a PIR scheme could exceed that for the case of the omniscient type. Namely, PIR schemes can increase their resistance to Byzantine adversaries by allowing the limitation on adversary's knowledge.

We introduce two cheater identifiable secret sharing (CISS) schemes with efficient reconstruction, tolerating t

We show that, in practice, a network adversary can achieve decidedly non-negligible advantage in attacking provable key-protection properties; e.g., the “existential key recovery” security and “multi-key hiding” property of typical nonce-based symmetric encryption schemes whenever these schemes are implemented with standard block ciphers. We also show that if a probabilistic encryption scheme uses certain standard block ciphers (e.g., two-key 3DES), then enforcing the security bounds necessary to protect against network adversary attacks will render the scheme impractical for network applications that share group keys amongst many peers. The attacks presented here have three noteworthy implications. First, they help identify key-protection properties that separate the notion of indistinguishability from random bits (IND$) from the strictly weaker notion of indistinguishability of ciphertexts (IND); also, they help establish new relationships among these properties. Second, they show that nonce-based symmetric encryption schemes are typically weaker than probabilistic ones. Third, they illustrate the need to account for the Internet-level growth of adversary capabilities when establishing the useful lifetime of standard block-cipher parameters.

For an arbitrary set B of Boolean functions satisfying a certain condition, we give a general method of constructing a class CB of read-once Boolean formulas over the basis B that has the following property: For any F in CB, F can be transformed to an optimal formula (i.e., a simplest formula over the standard basis {AND, OR, NOT}) by replacing each occurrence of a basis function h ∈ B in F with an optimal formula for h. For a particular set of basis functions B* = {AND,OR,NOT,XOR,MUX}, we give a canonical form representation for CB* so that the set of canonical form formulas consists of only NPN-representatives in CB*.

We introduce a complexity measure r for the class F of read-once formulas over the basis {AND,OR,NOT, XOR, MUX} and show that for any Boolean formula F in the class F, r(F) is a lower bound on the quantum query complexity of the Boolean function that F represents. We also show that for any Boolean function f represented by a formula in F, the deterministic query complexity of f is only quadratically larger than the quantum query complexity of f. Thus, the paper gives further evidence for the conjecture that there is an only quadratic gap for all functions.

We present a distributed protocol for achieving totally unbiased global coin flipping in the presence of an adversary. We consider a synchronous system of n processors at most t of which may be corrupted and manipulated by a malicious adversary, and assume a complete network where every two processors are connected via a private channel. Our protocol is deterministic and assumes a very powerful adversary. Although the adversary cannot eavesdrop, it is computationally unbounded, capable of rushing and dynamic. This is the same model that is adopted in Yao's global coin flipping protocol, which we use as the base of our protocol. Our protocol tolerates almost n/3 processor failures and terminates in t+4 rounds. The resilience of our protocol is greatly improved from that of Yao's protocol at the slight expense of running time, which is only added just two rounds.