# 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.

135 questions
Filter by
Sorted by
Tagged with
73 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 ...
41 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 ...
77 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 ...
94 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.)
83 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 ...
21 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 ...
57 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, ...
758 views

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 ...
51 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 ...
71 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 ...
52 views

### What is the “single-letter characterization of the secrecy capacity”?

I'm reading a paper  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 ...
82 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 ...
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 ...
94 views

### Perfect Secrecy for Message Subset

In "Introduction to Modern Cryptography" by Jonathan Katz exercise 2.6 goes like this: "Say encryption scheme (Gen, Enc, Dec) satisfies DEFINITION 2.1 for all distributions over ℳ that assign non-zero ...
202 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 ...
132 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 ...
521 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 ...
138 views

130 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 ...
3k 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, ...
420 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 ...
225 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.
68 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 ...
198 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 ...
160 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(...
159 views

### Perfect Indistinguishability in shift cipher

I have the following question: Which of the following attackers can be used to demonstrate that the shift cipher for 3-character messages does not satisfy perfect indistinguishability? ...
102 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 ...
944 views

### Practical perfect security in bitwise XOR vs integer addition/subtraction cipher

XOR already provides perfect security in theory but it's hard to apply it in practice due to strict requirements. I was thinking about whether simple addition/subtraction in integer format would not ...
381 views

### Is perfect forward secrecy (PFS) possible without public key cryptography

I have an understanding of PFS as used in most key agreement algorithms as well as things like TextSecure protocol and ratchets. My undestanding is that PFS is not possible without asymmetric (public ...
421 views

### Perfect Secrecy prove

There was a question on my final exam, but I could not get a point. I really want to know the right answer. Question is: Suppose a cryptosystem has perfect secrecy. Prove that H(P|C) = H(P) H(...
157 views

### Why a public key encryption scheme cannot be considered perfect according to Shannon?

I'm looking for a proof of this theorem
128 views

### Is perfectly secret key exchange provably impossible?

We know that perfect secrecy in encryption is possible (one-time pad). Now, the concept of key exchange like Diffie-Hellman is that we can establish a shared key without an interceptor knowing, and ...
154 views

### (Im)perfect Secrecy: |K| < |M|

I have a basic understanding of perfect secrecy. In the case where |K| == |M|, I see that there is only one key to encrypt a given m to a given c. Therefore each m is equally likely with same ...
60 views

### Necessity of Randomness when Privately Computing a Sum

I want to show that no 1-private deterministic protocol exists for calculating a sum of $n \geq 3$ parties (within the realms of Perfect rather than Computational Security). I'm having trouble showing ...
583 views

### Proving one time pad is perfectly secret

I'm reading about one-time pad in "Introduction to Modern Cryptography" by Katz and Lindell. I can understand the definition of perfect secrecy. However, how is OTP proven to be perfectly secure ? I'm ...
477 views

### Proving that there is no scheme which would be perfectly CPA-secure

A private-key encryption scheme Π = (Gen, Enc, Dec) has perfectly indistinguishable encryptions under a chosen-plaintext attack, if for all probabilistic polynomial-time adversaries A it holds that Pr[...
424 views

### Is the one-time pad still perfectly secret if all-zero keys are excluded?

I'm trying to solve this question related to one-time pads and perfect secrecy: My solution is: I assumed that the current message space is $M = \left\{ 0,1 \right\}^l$ and the new keyspace after ...
138 views

### Perfect Secrecy for some distribution implies perfect secrecy for any distribution

I'm quite thrilled about this question I got for homework, even though we were given the answer to the problem. It goes like this: Let $\mathcal{M}$ be the set of plaintexts of a symmetric encryption ...
88 views

### One-time pad and Perfect secrecy

Consider the following property of one-time symmetric encryption scheme $(\mathsf{Enc}, \mathsf{Dec}, \mathsf{K})$. For Every message distribution $M$, every pair of messages $m_0,m_1$ belonging to $M$...
105 views

### Question on probability distribution

I computed $\Pr[\mathsf{CT} = 1] = \Pr[\mathsf{CT} = 2] = \Pr[\mathsf{CT} = 4] = 2/9$ and $\Pr[\mathsf{CT} = 3] = 1/3$. When I calculate the first entry in the table, I get 1/2 not 1/9. Is my ...
Following the same definition in this question for perfect secrecy for two messages $m,m' \in \mathcal{M}$. I don't understand how the accepted answer produces a secure system? I mean The adversary ...