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

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 ...
0
votes
0answers
64 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 ...
2
votes
2answers
137 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
92 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 ...
6
votes
1answer
427 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
79 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]|...
2
votes
1answer
126 views

Unbreakable Hill cipher

Why don't we use hill cipher of 100 × 100? or even bigger. That would be closely unbreakable. The number of keys possible 2 × 2 hill cipher is 157248. for 100 × 100 number is beyond limits.
1
vote
1answer
79 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
116 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 ...
0
votes
1answer
346 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 ...
0
votes
0answers
49 views

Show that adversary indistinguishability is equivalent to specific perfect secrecy definition

How can I show that adversary indistinguishability (AI) is equivalent to the following deifinition of perfect secrecy (PS)?: $P[Enc_k(m_0) = c] = P[Enc_k(m_1) = c]$ for all $m_0,m_1 \in \mathcal{M},c ...
1
vote
1answer
91 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|} \...
0
votes
1answer
78 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 ...
2
votes
3answers
2k 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
215 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
140 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
57 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 ...
2
votes
1answer
140 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
129 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(...
2
votes
1answer
130 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? ...
2
votes
1answer
86 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 ...
-3
votes
3answers
626 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 ...
1
vote
3answers
234 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 ...
1
vote
1answer
311 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(...
-1
votes
1answer
112 views
1
vote
2answers
109 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 ...
1
vote
1answer
111 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 ...
2
votes
0answers
59 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 ...
3
votes
1answer
403 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 ...
3
votes
2answers
340 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[...
4
votes
1answer
266 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 ...
1
vote
0answers
108 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 ...
0
votes
1answer
76 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$...
-1
votes
1answer
72 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 ...
1
vote
0answers
230 views

Perfectly secret scheme for two distinct messages

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 ...
3
votes
0answers
258 views

Epsilon Perfect Secrecy: Size of Key Space

I am solving a homework problem which defines $(1-\epsilon)$-perfect secrecy as the secrecy satisfied by the encryption scheme when the following inequality holds $\Pr[M=m\mathrel|C=c]\leq (1+\...
1
vote
2answers
169 views

clarify perfect secrecy definition

One of the notes defined perfect secrecy (PS) as Let E = (E,D) be a Shannon cipher defined over (K,M, C). Consider a ...
11
votes
2answers
2k views

Can one claim that AES has perfect secrecy for a key size and message size of 128 bits?

While looking at this question I discovered the following here (question 5), and wanted to ask it as a separate question. Alice knows that she will want to send a single 128-bit message to Bob ...
1
vote
1answer
301 views

How Shannon’s concept of perfect secrecy is linked with mutual information?

For a system to be unconditionally secure $H(K) \geq H(M)$, i.e entropy of the secret key must be at least as great as the entropy of the plaintext The mutual information is: $I(X;Y)=H(X)-H(X\...
2
votes
1answer
215 views

Secure multiparty sum computation corruption bound

In Section 3.4 of the book Secure Multiparty Computation and Secret Sharing, it is claimed that for a secure multiparty computation problem with $n$ parties, the optimal corruption bound (concerning ...
0
votes
1answer
70 views

secure system in the perfect sense

a secure system in the perfect sense verifies the definition of perfect security. My question is as follows: There is always a way to check for perfect security by solving the first degree equation by ...
6
votes
2answers
376 views

Manual secret sharing?

What are feasible options for an equivalent of Shamir Secret Sharing using small tables, preferably usable with pen-and-paper? We want to share a secret $K$ into $n\ge2$ shares, so that $m$ shares ($2\...
2
votes
2answers
389 views

Is there such a thing as perfect CPA security?

Consider the following experiment. If we require that $$\operatorname{P}\left( \mathcal A \text{ succeeds} \right) = \frac{1}{2}$$ for any adversary $\mathcal A$ in order to call the scheme $\Pi$ ...
0
votes
1answer
251 views

Perfect secrecy of block ciphers

Is it right that all block ciphers don't provide perfect secrecy like AES? If it's true, how can we prove that? If it's not true can you tell me a sample? Any reference or guidance would be ...
1
vote
3answers
224 views

Generating OTP using Digital Dead Drop

I've had a thought and I'm wondering if this would be a useful way to devise and distribute a one-time pad. It relies on a digital dead drop and a hash function. The digital dead drop could take a ...
1
vote
1answer
903 views

Understanding how to proof an encryption scheme is perfectly secret

Consider each of the following encryption schemes and state whether the scheme is perfectly secret or not. Justify your answer by giving a detailed proof if your answer is Yes, and a ...
1
vote
1answer
112 views

Corruption bound of MPC when n>2

In the book titled "Secure Multiparty Computation and Secret Sharing" stated that MPC protocol is not secure when the adversary $t>n/2$. This was proved by using a 2 party protocol, but I can't ...
0
votes
1answer
133 views

Multi-Embedded Xor for Perfect OTP

I am looking for a perfect OTP design, so let's see if this design is good. There are 2 issues when it comes to a good OTP system, the key and the plaintext, we will use XOR as cypher: If the ...
1
vote
2answers
52 views

Does High Frequency Randomisation of valid and dummy messages in a high volume channel add security?

This was originally posed as this question: "Does randomisation of valid and dummy messages in a high volume channel add security?" But due to the reformulation based on answers provided, Tylo (https:...
0
votes
1answer
333 views

Perfect secrecy with some considerartion

According to eavesdropping indistinguishability experiment $PrivK_{A,\Pi}^{eav}$ from page 34 of this book, I define $\varepsilon$-perfect secrecy as this($\varepsilon>0)$: For every adversary $A$ ...