Questions tagged [perfect-secrecy]
Confidentiality in a very strong sense. Ciphers reaching perfect-secrecy can't be broken to disclose informations over the plaintext from the ciphertext, even with unlimited computing power. The most known example cipher reaching perfect screcy is the one-time-pad.
180
questions
0
votes
0
answers
55
views
Proving if two samples hides a value?
Given two values
$r'-r \mod q$
$i - r \mod q$
Where
$r',r$ sampled randomly from $Z_q$
while i is pick arbitrarily from $Z_q$ and a secret
Can we claim that this hides $i$?
Here is my sketch:
...
2
votes
2
answers
135
views
Perfect Secrecy other than One-time Pad
The most known example cipher reaching perfect secrecy is One-time Pad, which employs modulus addition for encryption and decryption.
Is there any other well-known cipher no less practical than OTP ...
- 153
1
vote
1
answer
413
views
Does CCA security imply perfect secrecy?
Can any encryption scheme that is CCA (Chosen Ciphertext Attack) secure be considered to achieve perfect secrecy?
2
votes
1
answer
93
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 $...
- 206
1
vote
0
answers
74
views
prove of disprove the modified shannon's theorem when the correctness requirement is relaxed
Suppose the correctness requirement of private-key encryption scheme is now relaxed to require only that
$$
\Pr[Dec_k(Enc_k(m)) = m] \ge \frac{1}{2} + \epsilon.
$$
Prove of disprove that if an ...
- 21
1
vote
1
answer
53
views
Is it necessary keys to have equal propabillities for the system to have perfect secrecy?
Shannon's theorem for perfect secrecy states that
$$\forall x \in M, y \in C:\quad P[x|y]=P[x] $$
I know we need $|M|\leq |C| \leq |K|$.
If $|Μ|=|C|=|K|$ all keys should have equal probs.
If $|Μ|<|...
- 173
4
votes
6
answers
2k
views
why XOR is recommended/Used in every paper I read for encryption and decryption stream cipher?
Stream ciphers use a deceptively simple mechanism: you combine the plaintext data, bit by bit, with “key” bits, using the exclusive or operation.
Why can't I use other opeartions such as NAND, AND, ...
1
vote
0
answers
69
views
What is the simplest way to implement data encryption for Raspberry PI project that communicate through Bluetooth? [closed]
I have developed a project based on Raspberry Pi that communicates through Bluetooth with Android application, My idea is to enhance its privacy through encryption. So, I've tried ...
0
votes
1
answer
2k
views
Is 7-Zip Encryption really secure? [duplicate]
Is 7-Zip really a good encryption tool? I wonder what kind of encryption is used in 7-zip. I see most people using 7-Zip. Just curious about what extent it is safe.
0
votes
0
answers
191
views
Relation between the size of key space and message for an encryption scheme that is not perfectly secure
I have been trying to solve the following:
Given a scheme that is perfectly correct but not perfect secrecy. It satisfies computational security, however, in that, if Q = Pr[Adv wins no query semantic ...
1
vote
1
answer
60
views
How can I distribute a set of anonymous tokens digitally among a known limited population to do anonymous voting?
TL:DR
How can I give a population of N people the chance to randomly pick one token each person guaranteeing those:
Nobody knows noone else's token.
Noone can pick more than one token.
Every person ...
- 113
3
votes
1
answer
170
views
Information Theoretic Security for Public Key Encryption
Do there exist information theoretic secure public key crypto-systems? Are they useful in any way, or are they just mathematical curiosities?
- 155
1
vote
1
answer
81
views
What is the Work Factor of the one time pad?
Work Factor is defined as the minimum amount of work (can be the length of the key) to determine the secret key of an cryptosystem (HAC, Menezes, Alfred J. et al).
And One time pad have unconditional ...
- 143
2
votes
1
answer
229
views
Proving two definitions of perfect security are equivalent
I'm trying to prove that the following two definitions are equivalent:
$\forall m\in M $ and $c\in C$ $\Pr[C=c \mid M=m]=\Pr[C=c]$
$\forall m_1,m_2 \in M $, $E_k(m_1)=E_k(m_2)$, where $E_k(m_i)$ ...
- 383
0
votes
0
answers
126
views
Perfect security - is this definition correct?
I have this definition:
each ciphertext is equally probable for a given plaintext and key
chosen at random
I know that perfect security can be defined as
$$\forall c \in \mathcal{C} \ \forall m_1,...
- 123
2
votes
2
answers
249
views
Ideal cipher vs Ideal encryption scheme
Ideal cipher is a random permutation for every key in its key space.
And, ideal encryption scheme is the one which has perfect secrecy/indistinguishability.
For an encryption scheme, random ...
- 63
0
votes
0
answers
96
views
difference between unconditionally sure, perfect confidentiality, and semantically sure, adversary-wise and advatnage-wise?
can anyone please tell me the difference between unconditionally secure, perfect confidentiality and semantically secure? I know that for perfect confidentiality, we have an adversary A that has an ...
- 11
1
vote
1
answer
148
views
Katz/Lindell - 2.10: Is exhaustive search over the key-space allowed in perfect indistinguishability?
I am self studying using "Introduction to Modern Cryptography (2nd edition)"
I am trying to understand how the solution to the following problem is valid:
Prove that a scheme satisfying ...
- 247
2
votes
1
answer
229
views
Katz/Lindell 2.4 - Generalizing from 2 messages to any message space?
I'm trying to solve problem 2.4 in "Introduction to Modern Cryptography" (2nd edition) for self-study.
The problem asks to prove that perfect secrecy
$$
Pr[M = m | C = c] = Pr[M = m]
$$
...
- 247
2
votes
1
answer
460
views
Perfect Secrecy for Shift Cipher
I've read the definition of perfect secrecy as the following:
A cryptosystem has perfect secrecy if $\Pr(x | y) = \Pr(x)$, for all $x \in P$ and $y \in C$, where $P,C$ are respectively the set of ...
- 211
0
votes
1
answer
327
views
Why are stream ciphers computationally secure?
In case multiple stream ciphers exist, I'm refering to this specific instance in which you generate a key that is just as long as the msg, M, as a function of a nonce and a smaller key K.
My textbook ...
1
vote
1
answer
69
views
Secret sharing is based in random variables that are uniformly distributed?
In Rabin and Ben-Or, their basic assumption is that each participant can broadcast a message to all other participants and that each pair of participants can communicate secretly. Hence, they design a ...
- 279
2
votes
0
answers
39
views
Equivalent conditions for perfect secrecy of a symmetric crypto system
I've been reading about perfect secrecy in crypto systems and I've ran across two definitions which turn out to be equivalent.
The first is Shannon secrecy:
A crypto system $(\cal K, \cal M$, $\text{...
- 121
0
votes
1
answer
167
views
One-time pad without zero: proof check
I started learning cryptography and tried to work through this problem: consider one-time pad where $\mathcal{M}=\mathcal{C}=\{0,1\}^n$ and $\mathcal{K}=\{0,1\}^n\setminus 0^n$ (call this scheme $\Pi$)...
- 21
2
votes
0
answers
183
views
An exercise from a textbook
Let $\varepsilon>0$ be a constant. Say an encryption scheme is $\varepsilon$-perfectly secret if for every adversary $\mathcal{A}$ it holds that
$$
\operatorname{Pr}\left[\operatorname{PrivK}_{\...
- 39
2
votes
1
answer
2k
views
Is OTP still perfectly secure if we limit message and key space
If we have a message space M {0,1,2,3,4,5,6} and likewise keyspace is K = {0,1,2,3,4,5,6} (generator choosen uniform keys k)
We define our encryption to be the XOR of their bitwise rep on K and M ...
- 43
1
vote
2
answers
250
views
Question on double-asymmetric encryption and split knowledge
Moin moin,
Let‘s assume there are two keypairs (d1,e1) and (d2,e2), where d1 and ...
- 19
2
votes
1
answer
704
views
Proving that a scheme is $\epsilon$-perfectly secret
I am currently trying to solve the following problem (2.18) from the book "Introduction to Modern Cryptography (3rd edition)" by Katz and Lindell:
Let $\epsilon > 0$ be a constant. Say an ...
- 23
1
vote
1
answer
57
views
AKE using Noise_NNpsk2 vs Noise_NKpsk2
I am working on an implementation based on the Disco library, which itself is based on Noise and strobe framework. The goal is to do bilaterally entity-authenticated key agreement with perfect forward ...
- 111
4
votes
1
answer
496
views
perfectly secret with key chosen uniformly
Prove or refute: Every encryption scheme for which the size of the keyspace equals the size of the message space, and for which the key is chosen uniformly from the keyspace, is perfectly secret.
My ...
- 51
0
votes
1
answer
304
views
How to solve this decryption algorithm given the encryption algorithm?
Consider the following cryptosystem with plaintexts from the set $M$ and ciphertexts from the set $S$ with $M = S = \{0, 1\}^4$ . A plaintext $P = (P_1, P_2, P_3, P_4)$ is encrypted to a ciphertext $C ...
- 101
-1
votes
1
answer
112
views
Advantage of existing Cryptosystems
I have read about the concept of perfect secrecy and statistical distance. The perfect secrecy is impossible to be implemented on real world scenario. So the cryptosystems used at various websites ...
1
vote
2
answers
1k
views
Perfect Secrecy and Message distribution
I have been trying to come up with a proof of the following statement,
Suppose a cryptosystem achieves perfect secrecy for a particular plaintext probability
distribution then Prove that perfect ...
- 31
0
votes
0
answers
165
views
Formal proof that the following definitions of perfect secrecy are equivalent
I've seen the following two definitions of perfect secrecy for an encryption scheme (Gen, Enc, Dec).
...
- 1
4
votes
3
answers
289
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....
2
votes
3
answers
637
views
Is it possible to have perfectly secure public-key cryptography with oracles?
It is a basic theorem of cryptography that it is impossible to have a perfectly secure public-key encryption scheme. That’s because the adversary can search through all possible private keys.
But I’m ...
1
vote
1
answer
562
views
Why don't most encryption algorithms use perfect secrecy?
Isn't it possible to make algorithms that are both computationally complex and have many possible answers if you try to crack them without knowing the password?
Why aren't many popular algorithms like ...
- 739
0
votes
1
answer
156
views
Using HMAC with AES modes that do NOT require padding [closed]
I'm trying to use HMAC with AES modes that do not require any sort of padding.
Although I am aware that modes like AES-GCM and ...
- 105
2
votes
1
answer
611
views
A generalisation of Shannon's theorem of perfect secrecy
The proof I'm struggling with is the following:
Let $\mathcal{E}$ be a cipher defined over $(K, M, C)$. Suppose that $SSadv[A, \mathcal{E}] ≤ \epsilon$ for all adversaries $A$, even including ...
user80306
2
votes
1
answer
256
views
Perfect secrecy and block ciphers
Consider a block cipher that encrypts bit strings of length $n$, where the key-space of the block cipher is of size $2^{kn}$, $k \geq 1$. My understanding of perfect secrecy is that a system is ...
- 526
2
votes
1
answer
235
views
How many perfect secrecy systems are there?
How many non-trivial*, interesting perfect secrecy systems are there other than the one-time-pad? Does it seem that the one-time-pad and perfect secrecy are synonymous, but are there any other ...
- 526
2
votes
1
answer
508
views
Proving equivalency of two security definitions of symmetric encryption schemes
how to prove definition 3.8 and 3.9 are equivalence ?
picture is from book an introduction to modern cryptography (2nd edition) by j. katz and y. lindell pdf
and https://repo.zenk-security.com/...
- 41
0
votes
1
answer
257
views
Adding the same noise to all element of a vector is Differential privacy
In Differential privacy, if we add a $N$-dimension private vector with $N$-dimension Laplace or Gauss noise, we obtain differential privacy. However, if we only generate a 1-dimension noise to add it ...
0
votes
0
answers
76
views
Perfectly secure cryptosystem as many keys as plaintexts
Is a cryptosystem perfectly secure if there are at least as many keys as there are plaintexts?
My guess is yes but I am not sure, new to cyptosystems
- 1
0
votes
2
answers
349
views
ISAKMP 'master key' PFS (phase I) vs Ipsec session key PFS (Phase II)
A question for the crypto-experts to help out a somewhat confused guy: why does PFS (perfect forward secrecy) also exist in phase II as well as in phase I?
Rationale:
In phase I ISAKMP, the result ...
- 1
1
vote
3
answers
246
views
Why use an OTP if you already have a secure channel
Let's say I have some sensitive information, and I want to encrypt it with a OTP and send it to the FBI or something. Now, in order for the recipient to successfully decrypt the message, he needs to ...
- 337
1
vote
0
answers
82
views
One Time Pad proof for Perfect Secrecy
In the book "Introduction to Cryptography with Coding Theory" by Trappe, in the paragraph about the security of the One Time Pad, is it told that given the set of possible plaintexts $P$, the set of ...
- 461
0
votes
2
answers
322
views
What operations provide perfect secrecy other than modulo addition
As far as I know OTP is the only algorithm proven to provide perfect secrecy. It can work with XOR which is addition modulo 2 and obviously it can work with additions modulo N. What other operations ...
- 103
2
votes
1
answer
353
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.)
- 516
1
vote
2
answers
170
views
Is it possible to use an algorithm to generate an OTP?
I am a software developer, not a cryptologist.
I like the idea of perfect secrecy and would like to use a one-time pad (OTP) to encrypt/decrypt files up to, say, 50Mb. Is there a way that I can use ...
- 127