Skip to main content

Questions tagged [information-theory]

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

Filter by
Sorted by
Tagged with
2 votes
2 answers
106 views

Can you use ChaCha20 as one-time pad?

My knowledge of cryptography nothing beyond basic so I am by no means an expert, but I do know a bit of undergraduate mathematics including number theory. I know that stream ciphers like ChaCha20 is ...
cryptobro's user avatar
0 votes
0 answers
34 views

Implementing Secret Sharing Among Multiple Parties

I'm working on a scenario where a safe has a lock code '42', and this code needs to be shared securely among four individuals. The goal is to set up a system where at least two out of these four ...
Iman Mohammadi's user avatar
0 votes
0 answers
68 views

Key-dependent cipher generation

Is there any cryptanalysis possible if the cipher itself is deterministically derived from key material? For example, suppose you have n building blocks (ARX primitives, AES ops, other primitives) and ...
user avatar
14 votes
5 answers
10k views

Does Grover's algorithm really threaten symmetric security proofs?

By Shannon's theorem of perfect security, if I give you a ciphertext 'LOUPL', you can do a brute-force attack and then you would find plaintexts like 'HELLO', 'APPLE', 'SPOON', but you can't ...
Victor Espinoza's user avatar
2 votes
1 answer
125 views

Statistics-heavy crypto papers

I'm currently taking a course in which we choose a stats-heavy paper and analyse it, summarising our work in the form of a written report and presentation. I have tried to find such a paper in crypto, ...
smoking_big_ole_doinks's user avatar
2 votes
1 answer
110 views

Defining the random variables $K,M,C$ and Perfect Secrecy

In many books on Cryptography, we refer to probability distributions over the key space $\mathcal{K}$, over the plaintext space $\mathcal{M}$ and over the ciphertext space $\mathcal{C}$. Then, we let $...
Chris's user avatar
  • 236
5 votes
2 answers
127 views

Coin flipping without commitments or random oracles

It's well known that two parties, Alice and Bob, can flip a fair coin using commitments. Alice picks a random number $a \in \mathbb{Z}_q$ and computes $c_a = Com(a, r_a)$ where $r_a \xleftarrow{R} \...
Ari's user avatar
  • 178
1 vote
0 answers
54 views

Adversary's advantages against mode of operation instantiated with random permutation and block cipher relation

I'm reading an article "A Tweakable Enciphering Mode" by Halevi and Rogavay and wondering about one statement. On page 6 there are 3 inequalities: $$ \begin{equation} \begin{split} \...
Georgy Firsov's user avatar
0 votes
2 answers
265 views

Isn't an asymmetric cipher (like RSA) algorithm sufficient for all basic needs, when speed is irrelevant?

Why I care: I want to implement some secure sessions for communicating over internet and since I am a complete amateur in this and don't want to spend a lot of time learning about cryptography or ...
donaastor's user avatar
  • 125
2 votes
1 answer
121 views

What is the methodology for selecting symbol bit length and window size when performing Shannon Entropy Analysis?

When performing Shannon Entropy analysis on something like an RNG or a file, you must: Select a symbol bit length and number of samples would will perform analysis on at a time (IE: windows size) ...
Liam Kelly's user avatar
1 vote
1 answer
112 views

What's the probability of cracking this cipher using partial information about the private key obtained from $k$ public keys?

For the following cipher, what is the probability of someone without the private key generating a valid public key, using only information from a list of $k$ public keys previously generated with the ...
virtuolie's user avatar
  • 139
3 votes
2 answers
446 views

What exactly does "Extension of a polynomial" mean?

This from the manuscript of a book on Zero Knowledge Proofs - https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf 3.5 Low Degree and Multilinear Extensions Let $\mathbb F$ be any finite ...
user93353's user avatar
  • 2,245
2 votes
2 answers
281 views

What's bad about idea of public-key/one-time-pad hybrid cryptosystem?

As i know, generally nowadays hybrid protocols are more widely used than either symmetric or public key cryptosystems separately. I read that public key system is used to exchange and share secret via ...
nimrodel's user avatar
1 vote
0 answers
63 views

If a different plaintext may produce the same ciphertext, is the system perfectly secure?

Define the injective map $\phi: \Omega\rightarrow \mathbb{N}$, such that $\Omega=\mathcal{A}^n$ denotes the set of all strings of length $n\in\mathbb{N}^*$ from an alphabet $\mathcal{A}$ of elements $...
UNOwen's user avatar
  • 11
8 votes
5 answers
2k views

Computational Complexity Of Breaking Information Theoretic Security

Wikipedia mentions that Shamir's secret sharing(SSS) for example, has information theoretic security. While I understand the concept that the adversary would just not have enough information to break ...
QuestionEverything's user avatar
4 votes
3 answers
311 views

Can you have perfect secrecy with countable message/key spaces by dropping countable additivity?

This classic paper by Chor and Kushilevitz shows that if the key space and the message space are both countably infinite, then it is impossible to have a perfectly secure private-key encryption scheme....
Keshav Srinivasan's user avatar
4 votes
1 answer
104 views

Oblivious transfer impossible from noiseless channels

If computationally unbounded parties $A$ and $B$ have only a noiseless channel between them, why is information-theoretic oblivious transfer impossible even for the passive cheating setting? ...
Curious Cat's user avatar
1 vote
0 answers
25 views

Are the receivers in stateless broadcast encryption assumed to be computationally bounded?

I started to read about the broadcast encryption problem, specifically, the first, seminal work of FN93 followed by the subset cover technique presented at NNL01, and something really trivial and ...
Bartolinio's user avatar
2 votes
2 answers
286 views

Doubt about Shannon entropy

Let's consider a random variable X that can produce the output $c$ with probability $1/4$. I was told that $-\log_{2}(\frac{1}{4})$ represents the number of bits needed to represent $c$. But, imagine ...
AleWolf's user avatar
  • 461
4 votes
1 answer
326 views

How can a public-key encryption scheme be used to construct a commitment scheme in the CRS model?

For a PKE scheme $(Gen, Enc, Dec)$, the most 'obvious' idea is to commit to an encryption of a bit and in the reveal phase maybe send $r_g$, $r_e$ where $r_g$ is the randomness of $Gen$ and $r_e$ is ...
Andy Dienes's user avatar
2 votes
1 answer
394 views

Does an information-theoretically secure hash function exist?

Does an information theoretically secure hash function exist? (By exist I mean is discovered/invented and implemented, not whether it could exist.)
09182736471890's user avatar
2 votes
0 answers
121 views

What is the intuition behind the strength of unstructured symmetric cryptography?

Consider a single round of a cryptographic permutation, what is so special about it that lacking some bits of information that either get mixed into it as a subkey or omitted at the end (sponge ...
user avatar
1 vote
1 answer
333 views

What is the "single-letter characterization of the secrecy capacity"?

I'm reading a paper [1] in which secrecy capacity are being discussed under the following terms: A single-letter characterization of the secrecy capacity that holds for the general case remains ...
Nino Filiu's user avatar
2 votes
1 answer
186 views

Block cipher information leakage using same key

This is from a previous exam question and I'm not really sure how to approach this properly We're using a block-cipher mode that encrypts $C_i$ = $E_k$ ($P_i$ $\oplus$ $C_{i-1}$ $\oplus$ $P_{...
Dario Blair's user avatar
1 vote
1 answer
158 views

Understanding $\varepsilon$-advantage in cryptographically secure deterministic RNG

In Efficient and Secure Pseudo-Random Number Generation by Vazirani & Vazirani, it is stated that every pseudorandom number generator which satisfies the XOR Condition can securely output $\log n$ ...
Antonio Frighetto's user avatar
1 vote
0 answers
1k views

ECC with 512bit compatible curves

I understand that given solutions for solving a discrete logarithm problem are on the order of 𝑂(2𝑛/2), ergo, 256bit private keys based on 25519 or secp256k1 have an effective bit strength of ...
Woodstock's user avatar
  • 1,424
3 votes
0 answers
608 views

On average conditional min-entropy

The average conditional min-entropy of X given Y, $\tilde H_\infty( X | Y)$, measures, roughly speaking, the amount of randomness that is in $X$ given as side information $Y$. (for the formal def, ...
AntonioFa's user avatar
  • 448
8 votes
2 answers
3k views

What is the difference between information-theoretic and perfect types of security?

I'm having a hard time pinning down an exact definition of the difference between information-theoretic and perfect types of security. A rigorous definition seems elusive... A. Wikipedia puts the ...
Paul Uszak's user avatar
  • 15.5k
2 votes
2 answers
196 views

Monotonicity of min-entropy

Let $Z^t = (Y_1,\ldots,Y_t)$ be a sequence of random variables each taking values in $Y$. The random variables are not necessarily i.i.d but we know the joint distributions. i.e for every $z = (z_1,......
Marc Ilunga's user avatar
  • 3,338
3 votes
0 answers
165 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 ...
Léo Colisson's user avatar
4 votes
1 answer
108 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 ...
danxinnoble's user avatar
2 votes
1 answer
220 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 ...
user56834's user avatar
  • 155
8 votes
2 answers
206 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 ...
Ruben De Smet's user avatar
0 votes
1 answer
191 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 $\...
Ruan Sunkel's user avatar
0 votes
2 answers
1k 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 ...
Silvia Rossi's user avatar
2 votes
0 answers
122 views

Entropy of the union of two sources [closed]

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 ...
Silvia Rossi's user avatar
8 votes
1 answer
619 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$ ...
fgrieu's user avatar
  • 142k
-1 votes
2 answers
719 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(...
partizanos's user avatar
1 vote
0 answers
137 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.'...
Lwins's user avatar
  • 111
3 votes
0 answers
176 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 ...
fgrieu's user avatar
  • 142k
3 votes
2 answers
896 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 ...
curious's user avatar
  • 6,180
3 votes
2 answers
616 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 ...
Nabil Khossossi's user avatar
0 votes
2 answers
305 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, ...
Jay's user avatar
  • 195
-1 votes
1 answer
98 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 ...
Jay's user avatar
  • 195
-1 votes
1 answer
75 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 ...
Jay's user avatar
  • 195
1 vote
1 answer
378 views

Fortuna: With a Single Entropy Source

I have worked on a random number generator that has turned out to give results pretty close to those of Fortuna with a single source. I was wondering how it affects the performance and claims of ...
Jay's user avatar
  • 195
3 votes
1 answer
347 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. ...
Jay's user avatar
  • 195
0 votes
1 answer
70 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 ...
Jay's user avatar
  • 195
1 vote
2 answers
758 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 ...
Jay's user avatar
  • 195
3 votes
2 answers
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 ...
Jay's user avatar
  • 195