Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [information-theory]

Information theory is concerned with sending messages via electronic signals in the most efficient and error-free way.

3
votes
0answers
33 views

Equivalents of Yao's Xor lemma to rounds, or other hardness amplification methods?

Simple question: I just learn the existence of the great Yao's Xor lemma (see a quick sum-up at the end of this post). I'd like to use a similar argument, but instead of a simple function, I've a two ...
4
votes
1answer
67 views

Under what conditions is broadcast possible? (Cryptographically, and in the model of Maurer 2006)

In this paper, Ueli Maurer uses a very cool model to generalize a number of results about broadcast, secret sharing and secure multiparty computation. Rather than talking about an adversary being ...
2
votes
1answer
83 views

How well is it understood mathematically why encryption schemes are hard to crack?

I have read some intro material into cryptography. It mainly goes into the current encryption schemes like AES, but not very deeply into the mathematics of why they are secure. I know that encryption ...
7
votes
2answers
127 views

Information theoretical lower limit on the size of public and private keys

When we consider public key algorithms, those usually require keys that are much longer than their security level. According to the Crypto++ Security Level page, for example, integer factorisation ...
0
votes
1answer
122 views

Brute-force attack on OAEP

Assume $M_1$ is $\operatorname{OAEP}$ padded and encrypted and the ciphertext is 1024 bytes as an example. If an adversary somehow gets around the encryption and manages to get half of the bits of $\...
0
votes
2answers
90 views

Difference between $F_2^n$ and $\Bbb F_2^n$ for a field

I am confused between the notation $F_2^n$ and $\Bbb F_2^n$ for a field in regards to codes. I thought that $F_2^n$ and $\Bbb F_2^n$ were both fields composed by codes of length n and entries in mod ...
3
votes
0answers
72 views

Entropy of the union of two sources

I am given that $S_1=(S_1,P_1)$ and $S_2=(S_2,P_2)$ are sources, where $S_1=\{s_1,...,s_n\}$, $P_1(x_i)=p_i$ and $S_2=\{y_1,...,s_m\}$, $P_2(y_j)=q_j$. I have to find the entropy of $S_{\lambda}=(S_i ...
7
votes
1answer
372 views

Security of Carter-Wegman polynomial authenticators, and their concatenation?

Carter-Wegman polynomial authenticators For a given finite field $(\mathbb F,+,\times)$ of $f$ elements, define a Carter-Wegman polynomial authenticator for a message $M=m_1\|m_2\|\dots\|m_l$ of $l$ ...
-1
votes
2answers
258 views

Is it possible that the entropy of a cipher system to be zero or infinite?

Entropy defined in cipher system as a measure of information or uncertainty. Is it possible to be zero or infinite? What would it mean based on Entropy formula: $$H(X)=-\sum_{x \in X} P(x) \log_2{P(...
1
vote
0answers
56 views

relationship between share size and entropy in secret sharing

In an $(s,r,n)$-ramp scheme, we require that any subset of at least $r$ parties can recover the secret, while any subset of size at most $s$ cannot learn anything about the secret. In Bogdanov et al.'...
3
votes
0answers
102 views

Information-theoretically provable Privacy Amplification?

In Quantum Key Distribution, the distributed key is produced by Privacy Amplification (also known as key distillation). An ID Quantique whitepaper introduces it with a Rudimentary Privacy ...
3
votes
2answers
798 views

Does information theoretical security definition imply DDH, RSA, QR does not hold?

Assuming we are in the information theoretical setting, whereby there is no bound on the computational power of an adversary. Does this mean that the standard definitions for DDH, RSA or QR do no hold ...
3
votes
2answers
306 views

what is the motivation behind quantum key distribution with Continuous variable?

Quantum Key Distribution protocol is a technique that allow two parties to share common secret key for cryptographic purpose and defined as being secure, by definition. But I am still wondering what ...
1
vote
2answers
152 views

Fuzzy Extractor for Binary Sequence

I was implementing Fuzzy Extractor on two close (noisy data). It's straight forward to use it to reconcile two close sets as per implementation given in https://www.cs.bu.edu/~reyzin/code/fuzzy.html, ...
-1
votes
1answer
73 views

How to find breaking complexity of N bit sequence?

I do have a secret generation source with very low bit rate. In order to guarantee secrecy I need to wait till I have say 128 samples. How do I justify regarding brute force breaking in for $N$ bit ...
-1
votes
1answer
62 views

Value of $t$ in Fuzzy Exractor

Is there a defined method to choose value of $t$ when using fuzzy extractor to reconcile two close secrets? I did try with multiple values ranging from 5 to close to half of the sequence. I ...
0
votes
1answer
133 views

Fortuna: With Single entropy source

Coincidently the design I was working out turned out to pretty close to a case of fortuna with single source. I was wondering how it affects the performance and claims of Fortuna as RNG in this ...
3
votes
1answer
229 views

Fortuna: Reseeding

It is recommended that a new seed file be generated approximately every ten minutes by seed file manager in FORTUNA,though it depends on the application and on the rate of the accumulation of entropy. ...
0
votes
1answer
50 views

Fuzzy Extractor constructor for sequence reconciliation

The famous works on Fuzzy Extraction considers $set$ of inputs. I am interested in reconciliation for sequence of close data. Here order of elements are important unlike in previous one. Are there ...
1
vote
2answers
474 views

Machine learning to break imperfect randomness

I have a shared randomness between two user. But to make situation worse Eve can listen to exchanges and guess noisy or error prone version of shared randomness, whose correlation varies depending on ...
3
votes
2answers
1k views

How long to wait to feed hashing using SHA 256?

I have a source which generates secrets at $8-10 bits $ per second. I need to use this secret to feed another generator every second. I am wondering how long should I wait while I am concatenating 8 ...
9
votes
3answers
742 views

Is Poly1305 an information-theoretically secure MAC?

I have heard some people say that the Poly1305 authenticator is a "nuclear" MAC i.e. it is information-theoretically secure. After reading the paper I see it is based on the Wegman-Carter MAC which is ...
1
vote
0answers
49 views

Fuzzy Extractor: Order of elements in set

Does order of elements in two sets matters to authenticate using Fuzzy Extractor? Using extractor as proposed in https://www.cs.bu.edu/~reyzin/fuzzy.html it seems the set difference is zero for this ...
0
votes
1answer
43 views

Formal Information-Theoretic Key Expansion Definition

Is there a formal definition for a protocol that expands keys that are pre-shared among 2 or more parties? How about an informal definition? Example: Alice and Bob pre-share a $n$-bit string $k$. ...
1
vote
2answers
193 views

Distributing shares in a particular monotone access structure

Consider 6 people, $A,B,C,D,E,F$ and a secret. Construct a scheme which enables the following subsets of people to retrieve the secret: three players from the set $\{A,B,C,D\}$ two players from the ...
2
votes
1answer
296 views

How to securely combine multiple sources of entropy?

Suppose that I have $n$ secure 32-bit keys that were generated separately using methods that are known to be secure. For example, one of them might have been generated by using a proven CSPRNG. ...
6
votes
1answer
277 views

Proof that any key exchange protocol is vulnerable to MitM attacks in the absence of shared information or trust

Today I realised that every key exchange protocol I know, without a priori any shared information or trust relations (i.e. any ability to sign anything), is utterly broken by an active man in the ...
3
votes
1answer
101 views

PRNG output with truly random noise

I am considering a situation where an adversary does not have access to the $n$-bit output string of a PRNG, but instead receives a noisy version of it, where each bit of the string is flipped with ...
7
votes
2answers
395 views

Secure entropy extractor for thermal noise collected from camera input?

I have read this paper (pdf) which talks about measuring the entropy of thermal noise collected from camera input. They estimate the minimum entropy at about 4 bits per pixel. Probably estimating 1 ...
1
vote
0answers
131 views

Weighted secret sharing scheme?

Is there a secret sharing scheme where secrets can be weighted, and that you need a total weight of $1$ to unlock the secret? I know that you could, of course, just figure out every subset that has ...
0
votes
2answers
63 views

Can we share an n-bit string by using shamir's secret sharing n times?

For Shamir's Secret Sharing, with a secret of size $n$, instead of having a finite field of order $n$, can we just use Shamir's Secret Sharing $n$ times, once for each bit, using a field of order 2? ...
1
vote
0answers
47 views

Is Shamir's Secret Sharing Scheme insecure for larger field? [duplicate]

According to wikipedia, if you are using shamir's secret sharing scheme with a field of order $p$, "High values of $p$ are risky because Eve knows that the chance for $f(x)\pmod{p}=f(x)$ increases ...
2
votes
1answer
95 views

Has there been any research on entropy efficient information-theoretically secure PRNGs?

I have an idea for an research project, but I am first wondering if it has been researched or implemented before. I think I have a way to come up with a set of PRNG algorithms which have the ...
2
votes
0answers
33 views

Quantitatively measure the private information revealed by a matrix?

Suppose I have a private matrix $A$ that I want to conceal. I do the matrix multiplication $A^\prime =AK$ and $A^\prime$ is public. How can I quantitatively measure "how well" the matrix $A$ is ...
4
votes
1answer
492 views

SHA512 vs HKDF key expansion

I'm working on a secure file storage server. This server allows users to upload and download files based on a "seed". This "seed" is a 128-bit value. From this 128-bit seed, we run SHA512 to derive a ...
4
votes
1answer
158 views

Is this transposition cipher information-theoretically secure for 1 message?

Given: $m = \{0,1\}^{n}$; a plaintext message of length $n$ encoded in binary $k = randomshuffle([0, 1, ..., 2n-1])$; A secret key consisting out of unique numbers between 0 and $2n-1$ in a true ...
1
vote
2answers
8k views

How can a cryptosystem be unconditionally secure?

The definition of an unconditionally secure cryptosystem states that the cryptosystem cannot be broken even with infinitely computational ressources and time. However, since most books define the ...
4
votes
1answer
356 views

Are all binary-additive stream ciphers reciprocal?

I'm writing a thesis focused on Maurer's provably-secure stream cipher. Long story short, this cipher works by expanding a short key into a long keystream and then XORring this keystream with the ...
9
votes
1answer
1k views

For a one-time pad, which MAC method is information-theoretically secure?

In the the main post about MAC methods it mentions a few methods: Authenticate And Encrypt: The sender computes a MAC of the plaintext, encrypts the plaintext, and then appends the MAC to the ...
4
votes
3answers
351 views

Would a symmetric cipher with a keylength a big as the data length be information theoretically secure?

One-Time-Pad is information theoretically secure as long as the random number stream is evenly long or longer than the data stream it encrypts, for a "deciphered" message could have been any message ...
5
votes
1answer
700 views

Why does a perfect secrecy can be achieved when decryption correctness is not totally required?

By Shanon theorem, a perfect secrecy encryption scheme must use a key space of equal size as the message space. But when the correctness requirement is weakened such that $Pr[Dec_k(Enc_k(m))=m]=1/2$ ...
3
votes
0answers
441 views

What aspects of information theory are used in modern cryptography? [closed]

In studying modern (and classical) cryptography, many notions from information theory crop up. Unicity distance, min-entropy, compression, encoding, etc. What parts of information theory should be ...