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.

Filter by
Sorted by
Tagged with
2
votes
1answer
1k 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 ...
0
votes
1answer
41 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 ...
2
votes
1answer
95 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 ...
0
votes
0answers
18 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 ...
3
votes
1answer
108 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 ...
0
votes
1answer
69 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 ...
-1
votes
1answer
99 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
2answers
190 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 ...
0
votes
0answers
71 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). ...
4
votes
3answers
214 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
3answers
307 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
1answer
222 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 ...
0
votes
1answer
84 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 ...
2
votes
1answer
211 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 ...
2
votes
1answer
136 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 ...
2
votes
1answer
128 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 ...
1
vote
1answer
240 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/...
0
votes
1answer
122 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
0answers
52 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
0
votes
2answers
193 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
vote
3answers
147 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 ...
1
vote
0answers
55 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 ...
0
votes
2answers
197 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 ...
2
votes
1answer
184 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.)
1
vote
2answers
122 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 ...
1
vote
0answers
30 views

Computationally indistinguishably vs Perfect Indistinguishably [duplicate]

I know that perfect security means absolutely no information about the plaintext is leaked to the adversary while computational secrecy is okay with a tiny amount of leak. But, what is the difference ...
2
votes
1answer
277 views

Almost (epsilon) perfect secrecy - lower bound of keyspace size

As a newcomer to cryptography, I'm working on Exercise 2.12 in the book, Introduction to Modern Cryptography. Using the proof of the theorem that says if $E$ is a perfectly secret encryption scheme, ...
3
votes
5answers
934 views

Read-once memory

So I've been reading about cryptography and one-time pads, which seem to provide theoretically perfect secrecy. My question is does any form of technology today allow data to be stored in a practical ...
0
votes
1answer
171 views

Why perfectly secrecy needs the key space to be as large as the message space?

Why perfectly secrecy needs the key space to be as large as the message space? I think the definition (1) $\Pr[M=m\mathrel|C=c]= Pr[M=m]$ still holds. Let $M(c)$ be the set of messages that can be ...
0
votes
1answer
178 views

If we know the pre-shared key of an IPSec tunnel, can PFS help us to stay encrypted?

Or if the "attacker" has the pre-shared key, then PFS won't help? Ex.: Heard something about China that it blocks IPSec and only allows it when you give them your pre-shared key, thus they can see ...
1
vote
1answer
168 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 ...
1
vote
1answer
124 views

Are there any classical proven secure cryptographic algorithms other than OTP? [duplicate]

Boiled down to the core as I understand it: A cryptographic algorithm has provable security if it's unbreakable, even if an adversary has unlimited computational power / time. If my understanding ...
6
votes
2answers
2k views

Why is PerfectForwardSecrecy considered OK, when it has same defects as salt-less password hashing?

PFS suites suffer from the same defects as any other salt-less password hashing scheme. Why is everyone promoting Perfect Forward Secrecy (PFS) ciphersuites so fiercely? Namely, when the group/hash ...
6
votes
2answers
1k 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 ...
4
votes
2answers
335 views

When does multiple OTP encryption become insecure if new keys are permuted? ​

I understand that OTP encryption fulfils perfect secrecy, meaning you can't decrypt the encrypted text to it's original plaintext (and know that this plaintext is indeed the original plaintext) unless ...
2
votes
2answers
220 views

Is OTP with homomorphic encryption trivial?

If my key size is as large as the data I'm encoding, is it trivial to devise a theoretically secure homomorphic encryption scheme for integers (or else any finite/infinite group with order) that ...
7
votes
1answer
632 views

Does Shannon perfect secrecy imply a deterministic encryption algorithm?

Consider an encryption scheme $(Gen,Enc,Dec)$ where $Gen$ is the key generation algorithm, $Enc$ is the encryption algorithm, where $c \leftarrow Enc_{k}(m) $ is taken to mean that the message $m$ in ...
1
vote
1answer
299 views

Find Lower bound on key space with relaxed definiton of perfect secrecy

Consider a relaxed definition of security. Let $\epsilon < 1$ be a constant and say we only require that for any distribution over $M$ ,any $m \in M $, and any $ c \in C$ $$ |Pr[M=m|C=c] - Pr[M=m]|...
3
votes
2answers
473 views

An unbreakable Hill cipher?

Why don't we use a Hill cipher of 100 × 100? Or even bigger? That would be close to unbreakable. The number of possible keys in a 2 × 2 Hill cipher is 157248. For 100 × 100 the number is beyond limits....
1
vote
1answer
261 views

flaw in perfect secrecy of shift cipher?

Why do we say shift cipher is perfectly secure when it is easy to break it (source)? Let's say I have a plaintext. "Australia is a big country"; I encrypt it using a shift of 2; That ciphertext can be ...
4
votes
2answers
233 views

Generate one-time-pad with pre-shared key and public randomness

I know very little about cryptography, so I apologize if the question does not make sense. Let's say we design a function $F(P, X) \rightarrow K$ that takes in a pre-shared private key $P$ and a ...
1
vote
1answer
2k views

What is Perfect forward secrecy?

I have read that when a user contacts an entity like a bank, it creates a pre-master key and then selects a master key for subsequent communications. Can the lack of PFS, create a security flaw if ...
1
vote
1answer
305 views

Proof one-time pad is perfectly secret with eavesdropping game definition

I have the following definition of perfect secrecy (please assume that the probabilistic version is not available): If we consider the eavesdropping game given by: $$\begin{array}{|r | r|} \hline ...
0
votes
1answer
184 views

Shamir Scheme: Whats the problem of not using random x-coordinates?

i would like to know why there is a problem of not using random x-coordinates in shamir secret sharing schemes. I consider that after evaluating the points in a polynomial $f(x)$, the share is ...
3
votes
3answers
4k views

What is perfect secrecy?

I read some similar questions like Simply put, what does “perfect secrecy” mean? (This one defines perfect secrecy as ciphertext conveys no information about the content of the plaintext. Now, ...
1
vote
1answer
693 views

In perfectly secret scheme, if key and message space are uniformly distributed, is ciphertext space always uniform as well?

Following up on a similar question, Does perfect secrecy imply uniform ciphertext distribution?, the answer seems to be that in a perfectly secret encryption scheme, the distribution of the ciphertext ...
0
votes
2answers
468 views

Why does the key for a one-time pad have to be uniformly distributed? [duplicate]

I would like an intuitive argument for what goes wrong in the proof that that a one-time pad provides perfect secrecy, if the key $K$ is not chosen uniformly at random from the entire key space.
1
vote
3answers
104 views

Non-interactive public sum of private values

Suppose there is a large number of participants each with a secret value. The secret values are very large (e.g. 256-bit integers). Each participant has published a public commitment to their secret ...
1
vote
2answers
480 views

For perfect secrecy, does the keyspace need to be uniform?

The definition of perfect security is just that: $Pr(M =m | C=c) = Pr(M=m)$. We can prove that one time pad is perfectly secure for any distribution on a message space $M$, and it happens to be that ...
1
vote
1answer
235 views

Please prove distinguishability given a non-perfectly secure cipher

I'm trying to prove that a perfectly secure cipher yields indistinguishability. I already know and can prove that a perfect cipher => indistinguishability by the following proof: \begin{align} \Pr(...