15

Here's an simpler but analogous problem that may illustrate what's going on: Given that $X=Y+Z$ and $Y=5$, compute $X$. The problem isn't that the answer is difficult to compute, the problem is that there isn't enough information there to give you any idea (any information about) what the answer is. That's what's meant by information-theoretic security. (...


14

This is about the Theory of Computability not the Theory of Complexity. The halting problem is a decision problem in CS. From Wikipedia's introduction; In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run ...


9

As others have noted, information-theoretic security really has no connection to computational complexity. Yes, with sufficient computing power, you could enumerate all the solutions (including the right one). But without enough information (e.g. the key in OTP, or enough shares in SSS) you would still have no way of telling which of the solutions is the ...


4

There is no point multiplication operation on secure elliptic curves*, there is only scalar multiplication apart from the point addition of the group. Scalar multiplication Scalar multiplication with a scalar $t$ is adding a point $P$ it self $t$-times $$ [t]P : = \underbrace{P + P + \cdots + P}_{t-times}$$ and it is well defined operation since the group is ...


3

For the discrete case, you can just use any zk-SNARK that generalizes over arithmetic circuits. There is no direct way to do a zero-knowledge proof over the reals. However, you can map linear operations over real numbers to operations in the field you are working in by first proving an upper bound on your inputs. Since the circuit is public the verifier can ...


3

To me the key mental image with information theoretic security is that given a ciphertext ($c$), for any possible plaintext ($p$) there will be a key ($k$) to decrypt the ciphertext to it. So given a $c$ we have $$\forall p: \exists k: Dec_k(c) = p$$ Which means that even if you brute-force try all the keys, you can get any output you might want and you will ...


2

Perhaps Attribute-based Encryption is what you are looking for. From the two schemes (KP-ABE, CP-ABE), CP-ABE can solve your problem. You can set the attributes of each identity according to their domain set and encrypt the file with policy using OR. The example you have given, Msg(D1,D3) can use (D1 OR D3) as a policy to encrypt. For more detailed ...


2

Information-theoretic security means that knowing the ciphertext doesn't help you find the plaintext. Knowing all $b$ bits of a single Shamir share tells you as much about the secret as knowing $0$ of the bits. You can still try to find the secret, and you could even succeed, but whatever you did would have worked just as well without the Shamir share. As ...


1

I'm not an expert but I will try to answer from my understanding. LSS allows you to divide the secret to many shares and it does not limit you to give only one share to a person. In the example you have given, the secret is divided into 5 shares and gave to 4 people. In this case, P_2 receives 2 shares. Having r_2 in two different rows doesn't help much in ...


1

You'd use a KBKDF on the clients, using the earlier secret as Input Keying Material (IKM) using the random as salt or Info input. KDF's generally have an output size parameter as well. Currently HKDF is considered a good KDF, and if you use the full function it supports a salt. Basically you would be implementing a so-called ratchet, where each key depends ...


Only top voted, non community-wiki answers of a minimum length are eligible