Information Theoretic Security

Shannon’s definition of perfect secrecy captures the strongest notion of security for an encryption system and requires that the ciphertext leaks no information about the plaintext to an eavesdropper with unbounded computational power. The only known system with perfect secrecy in this model is one-time pad. Two important limitations of one-time pad in practice are, (i) the size of key space must not be less than the size of plaintext space, and (ii) the key must be chosen uniformly at random for each message to be encrypted. A number of follow up work attempt to relax these limitations by introducing relaxed or new definitions of secrecy.

In this paper we propose a new relaxation of secrecy that we call perfect guessing secrecy, or guessing secrecy for short. This is a natural definition that requires that the adversary’s success chance of the plaintext using his best guessing strategy does not change after seeing the ciphertext. Unlike perfect secrecy, guessing secrecy does allow some leakage of information but requires that the best guess of the plaintext remain the same after seeing the ciphertext. We define guessing secrecy and prove a number of results. We show that similar to perfect secrecy, in guessing secrecy the size of the key space can not be less than the size of plaintext space. Moreover, when the two sets are of equal size, one can find two families of distributions on the plaintext space and key space, such that perfect guessing secrecy is guaranteed for any pair of distributions, one from each family. In other words, perfect guessing secrecy can be guaranteed with non-uniform keys also. We also show the relation between perfect secrecy and perfect guessing secrecy. We discuss our results and propose direction of future research.

We improve on the classical results in information-theoreti- cally secure multiparty computation among a set of n participants, by considering the special case of the computation of the addition function over binary inputs in the secure channels model with a simultaneous broadcast channel. This simple function is a useful building block for other applications. The classical results in multiparty computation show that in this model, every function can be computed with information-theoretic security if and only if less than n/2 participants are corrupt. In this article we show that, under certain conditions, this bound can be overcome.

More precisely, let t ^(p), t ^(r) and t ^(c) be the privacy, robustness and correctness thresholds; that is, the minimum number of participants that must be actively corrupted in order for privacy, robustness or correctness, respectively, to be compromised. We show a series of novel tradeoffs applicable to the multiparty computation of f(x ₁, …,x _n ) = x ₁ + … + x _n for x _i  ∈ {0,1}, culminating in the most general tradeoff: t ^(p) + t ^(r) = n + 1 and t ^(c) + t ^(r) = n + 1. These tradeoffs are applicable as long as t ^(r) < n/2, which implies that, at the cost of reducing robustness, privacy and correctness are achievable despite a dishonest majority (as an example, setting the robustness threshold to n/3 yields privacy and correctness thresholds of 2n/3 + 1).

We give applications to information-theoretically secure voting and anonymous message transmission, yielding protocols with the same tradeoffs.

Consider a weak client that wishes to delegate computation to an untrusted server and be able to succinctly verify the correctness of the result. We present protocols in two relaxed variants of this problem.

We first consider a model where the client delegates the computation to two or more servers, and is guaranteed to output the correct answer as long as even a single server is honest. In this model, we show a 1-round statistically sound protocol for any log-space uniform \(\mathcal{NC}\,\)circuit. In contrast, in the single server setting all known one-round succinct delegation protocols are computationally sound. The protocol extends the arithemetization techniques of [Goldwasser-Kalai-Rothblum, STOC 08] and [Feige-Kilian, STOC 97].

Next we consider a simplified view of the protocol of [Goldwasser-Kalai-Rothblum, STOC 08] in the single-server model with a non-succinct, but public, offline stage. Using this simplification we construct two computationally sound protocols for delegation of computation of any circuit C with depth d and input length n, even a non-uniform one, such that the client runs in time n·poly(log(|C|), d). The first protocol is potentially practical and easier to implement for general computations than the full protocol of [Goldwasser-Kalai-Rothblum, STOC 08], and the second is a 1-round protocol with similar complexity, but less efficient server.

We present a protocol that allows to prove in zero-knowledge that committed values x _i , y _i , z _i , i = 1,…,l satisfy x _i y _i  = z _i , where the values are taken from a finite field. For error probability 2^− u the size of the proof is linear in u and only logarithmic in l. Therefore, for any fixed error probability, the amortized complexity vanishes as we increase l. In particular, when the committed values are from a field of small constant size, we improve complexity of previous solutions by a factor of l. Assuming preprocessing, we can make the commitments (and hence the protocol itself) be information theoretically secure. Using this type of commitments we obtain, in the preprocessing model, a perfect zero-knowledge interactive proof for circuit satisfiability of circuit C where the proof has size O(|C|). We then generalize our basic scheme to a protocol that verifies l instances of an algebraic circuit D over K with v inputs, in the following sense: given committed values x _i,j and z _i , with i = 1,…,l and j = 1,…,v, the prover shows that D(x _i,1,…,x _i,v ) = z _i for i = 1,…,l. The interesting property is that the amortized complexity of verifying one circuit only depends on the multiplicative depth of the circuit and not the size. So for circuits with small multiplicative depth, the amortized cost can be asymptotically smaller than the number of multiplications in D. Finally we look at commitments to integers, and we show how to implement information theoretically secure homomorphic commitments to integer values, based on preprocessing. After preprocessing, they require only a constant number of multiplications per commitment. We also show a variant of our basic protocol, which can verify l integer multiplications with low amortized complexity. This protocol also works for standard computationally secure commitments and in this case we improve on security: whereas previous solutions with similar efficiency require the strong RSA assumption, we only need the assumption required by the commitment scheme itself, namely factoring.

Oblivious transfer (OT) is a primitive of great importance in two-party and multi-party computation. We introduce a general construction of universally composable (UC) oblivious transfer protocols based on lossy cryptosystems in the common reference string (CRS) model, yielding protocols under several assumptions. In order to achieve this, we show that for most known lossy encryption constructions it is possible to distinguish between lossy and injective public keys given the corresponding secret key, similarly to dual-mode encryption in messy mode.

Furthermore, we adapt the techniques of our general construction to obtain the first UC secure OT protocol based on the McEliece assumptions, which are coding theory based assumptions that until now have resisted quantum attacks, thus introducing the first UC secure OT protocol based on coding assumptions.

However, differently from previous results based on dual-mode encryption, our scheme does not require a trapdoor for opening lossy ciphertexts, relying instead on CRS manipulation and cut-and-choose techniques to construct the simulators. In both constructions we circumvent the need for universally composable string commitment schemes, which are required by previous black-box compilers.

In this note we revisit the famous result of Shannon [Sha49] stating that any encryption scheme with perfect security against computationally unbounded attackers must have a secret key as long as the message. This result motivated the introduction of modern encryption schemes, which are secure only against a computationally bounded attacker, and allow some small (negligible) advantage to such an attacker. It is a well known folklore that both such relaxations — limiting the power of the attacker and allowing for some small advantage — are necessary to overcome Shannon’s result. To our surprise, we could not find a clean and well documented proof of this folklore belief. (In fact, two proofs are required, each showing that only one of the two relaxations above is not sufficient.) Most proofs we saw either made some limiting assumptions (e.g., encryption is deterministic), or proved a much more complicated statement (e.g., beating Shannon’s bound implies the existence of one-way functions [IL89].)

Consider the following natural generalization of the well-known Oblivious Transfer (OT) primitive, which we call Oblivious Affine Function Evaluation (OAFE): Given some finite vector space \({\mathbb F}_q^k\), a designated sender party can specify an arbitrary affine function \(f:{\mathbb F}_q\to{\mathbb F}_q^k\), such that a designated receiver party learns f(x) for a single argument \(x\in{\mathbb F}_q\) of its choice. This primitive is of particular interest, since analogously to the construction of garbled boolean circuits based on OT one can construct garbled arithmetic circuits based on OAFE.

In this work we treat the quite natural question, if general \({\mathbb F}_q^k\)-OAFE can be efficiently reduced to \({\mathbb F}_q\)-OAFE (i.e. the sender only inputs an affine function \(f:{\mathbb F}_q\to{\mathbb F}_q\)). The analogous question for OT has previously been answered positively, but the respective construction turns out to be not applicable to OAFE due to an unobvious, yet non-artificial security problem. Nonetheless, we are able to provide an efficient, information-theoretically secure reduction along with a formal security proof based on some specific algebraic properties of random \({\mathbb F}_q\)-matrices.

The goal of Multi-Party Computation (MPC) is to perform an arbitrary computation in a distributed, private, and fault-tolerant way. For this purpose, a fixed set of n parties runs a protocol that tolerates an adversary corrupting a subset of the parties, preserving certain security guarantees like correctness, secrecy, robustness, and fairness. Corruptions can be either passive or active: A passively corrupted party follows the protocol correctly, but the adversary learns the entire internal state of this party. An actively corrupted party is completely controlled by the adversary, and may deviate arbitrarily from the protocol. A mixed adversary may at the same time corrupt some parties actively and some additional parties passively.

In this work, we consider the statistical setting with mixed adversaries and study the exact consequences of active and passive corruptions on secrecy, correctness, robustness, and fairness separately (i.e., hybrid security). Clearly, the number of passive corruptions affects the thresholds for secrecy, while the number of active corruptions affects all thresholds. It turns out that in the statistical setting, the number of passive corruptions in particular also affects the threshold for correctness, i.e., in all protocols there are (tolerated) adversaries for which a single additional passive corruption is sufficient to break correctness. This is in contrast to both the perfect and the computational setting, where such an influence cannot be observed. Apparently, this effect arises from the use of information-theoretic signatures, which are part of most (if not all) statistical protocols.

In this paper, we investigate on threshold proofs, a framework for distributing the prover’s side of interactive proofs of knowledge over multiple parties. Interactive proofs of knowledge (PoK) are widely used primitives of cryptographic protocols, including important user-centric protocols, such as identification schemes, electronic cash (e-cash), and anonymous credentials.

We present a security model for threshold proofs of knowledge and develop threshold versions of well-known primitives such as range proofs, zero-knowledge proofs for preimages of homomorphisms (which generalizes PoKs of discrete logarithms, representations, p-th roots, etc.), as well as OR statements. These building blocks are proven secure in our model.

The distributed versions of the protocols we propose in this paper are relatively efficient (when compared to a general MPC approach). In comparison to the original protocols only the prover’s (or user’s) side is modified while the other side stays untouched. In particular, it is oblivious to the other party whether it interacts with a distributed prover (or user) or one as defined in the original protocol.

In this paper, we study timed-release cryptography with information-theoretic security. As fundamental cryptographic primitives with information-theoretic security, we can consider key-agreement, encryption, and authentication codes. Therefore, in this paper, we deal with information-theoretic timed-release security for all those primitives. Specifically, we propose models and formalizations of security for information-theoretic timed-release key-agreement, encryption, and authentication codes, and we present constructions of those ones. In particular, information-theoretic timed-release encryption and authentication codes can be constructed from information-theoretic timed-release key-agreement in a generic and simple way. Also, we derive tight lower bounds of sizes of secret-keys and show an optimal construction for information-theoretic timed-release key-agreement. Furthermore, we investigate a relationship of mechanisms between information-theoretic timed-release key-agreement and information-theoretic key-insulated key-agreement. It turns out that there exists a simple algorithm which converts the former into the latter, and vice versa. In the sense, we conclude that these two mechanisms are essentially close.

An important issue of threshold secret sharing (TSS) schemes is to minimize the size of shares. This issue is resolved for the simpler classes called (k,n)-TSS and (k,L,n)-threshold ramp secret sharing (TRSS). That is, for each of these two classes, an optimum construction which minimizes the share size was presented. The goal of this paper is to develop an optimum construction for a more general threshold class where the mutual information between the secret and a set of shares is defined by a discrete function which monotonically increases from zero to one with the number of shares. A tight lower bound of the entropy of shares is first derived and then an optimum construction is presented. The derived lower bound is larger than the previous one except for special functions such as convex and concave functions. The optimum construction encodes the secret by using one or more optimum TRSS schemes independently. The optimality is shown by devising a combination of TRSS schemes which achieves the new lower bound.