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
1
vote
1answer
371 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
278 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
81 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 ...
7
votes
2answers
425 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
480 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
339 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
271 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
1k 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
122 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
152 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
59 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
381 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$ ...
1
vote
3answers
772 views

What are the vulnerabilities of XOR in the following scenario?

What are the security vulnerabilities of the XOR operator in the following scenario: The Key, The Cyphertext and the Plaintext are the same size in bits. The Key is only used once and it's secret The ...
1
vote
1answer
45 views

Equivalance Operator - Perfect Secrecy

The equivalance operator is the inverse of the XOR operator, it's symmetric. Would this mean that it would also provide theoretical perfect secrecy just like XOR? XOR ...
18
votes
12answers
14k views

Are one-time pads crackable in theory?

I've been taught that one-time pads are the only perfect encryption, since the only way to recover the message is by knowing the key. For example, for a target bitstring of 100 bits, I cannot scan ...
0
votes
3answers
142 views

Perfect Secrecy with 1 Time Complex Secret Cypher

Is it possible to achieve perfect secrecy, unbreakable, unguessable, uncrackable by using a totally secret cypher? The following conditions must apply: Using the secret cypher only 1 time, so that ...
0
votes
0answers
86 views

Interpretation of message space distribution in the definition of perfect secrecy of encryption schemes

I am a beginner to cryptography, and have started reading Katz and Lindell's book titled "Introduction to Modern Cryptography". I'm unable to understand what the probability distribution over the ...
0
votes
2answers
1k views

Perfect secrecy with XOR & SHIFT?

I have read that XOR provides perfect secrecy, when the key is perfectly random. However it's technically hard to generate truly random numbers, especially on computers, so that is why people use AES, ...
4
votes
1answer
481 views

Can AKE keys provide PFS

Can the channel keys that are derived from an AKE (authenticated key exchange) protocol be used in a secure channel that wants to have perfect forward secrecy? If the goal of AKE is to establish ...
1
vote
2answers
217 views

Distributing shares in a particular monotone access structure

Consider 6 people, $A,B,C,D,E,F$ and a secret. Construct a scheme which enables the following subsets of people to retrieve the secret: three players from the set $\{A,B,C,D\}$ two players from the ...
1
vote
2answers
224 views

A perfect $(2; 2)$-threshold scheme

Given a symmetric encryption scheme with $|K| = |C| = |M|$ that provides perfect secrecy, it is possible to share a secret $s ∈ M$ between two players by giving one player a key $k ∈ K$ and the other ...
1
vote
1answer
353 views

AES function with 128 bit key and 128 bit input size - does it have perfect secrecy?

If I look at the version of AES that gets key of size 128 bit and encrypts messages of size 128 bits. If I get some random key for the function, can I say it has a perfect secrecy and why? After a ...
4
votes
2answers
1k views

Prove Vigenere cipher isn't perfectly secret

As part of a homework assignment I have to prove/disprove that a Vigenère Cipher with a key of length n, uniformly distributed in the alphabet, on a plain text of length 2n, also uniformly distributed ...
0
votes
1answer
4k views

Prove that a given encryption scheme is perfectly secret

I'm studying for an upcoming test and I can't figure out the following sample question: Let $\Pi = (\operatorname{Gen}, \operatorname{Enc}, \operatorname{Dec})$ be an encryption scheme with key ...
5
votes
0answers
479 views

Shannon cipher with fewer keys than messages

Alice and Bob have a set $\mathcal{M}$ of $|\mathcal{M}|$ messages and a set $\mathcal{K}$ of $|\mathcal{K}|$ keys. Alice wants to send a message $m \in \mathcal{M}$ to Bob. She uniformly picks a key $...
4
votes
2answers
1k views

Perfect Secrecy for two distinct messages

We say that and encryption scheme $\pi$ is perfectly secret for two distinct messages, if for all distributions over $\mathcal{M}\times\mathcal{M}$ ($\mathcal{M}$ is the message space), for all $m_1,...
3
votes
1answer
681 views

monoalphabetic substitution perfect secrecy

I have this question that I'm trying to answer: Consider a monoalphabetic substitution cipher applied to plaintexts consisting of just a single letter. That is, $$M = \{0, 1, . . . , 25\}$$ The ...
2
votes
4answers
1k views

Would using a one-time pad multiple times with some conditions be safe?

I understand why |one-time pad|=|message| using a normal one-time pad, but I don't understand why for perfect secrecy it must alway be that |key|>|all messages exchanged|. What if, for example, I had ...
0
votes
1answer
308 views

Maximum secret key length from a time series shared signal

Alice and Bob share a common time series signal. 1. What can be the largest possible secret key? 2. Will the entropy and secrecy of system depends on this length? Ideally if after passing though ...
5
votes
1answer
1k views

What are the ways to generate Beaver triples for multiplication gate?

So to speed up the function evaluation we use beaver trick, to generate raw data in the offline phase and use them in the online phase to get the output share for the multiplication gate. So what are ...
0
votes
0answers
75 views

Perfect Secrecy and Message distributions

It is know that for a perfect secrecy scheme, for all m1,m2 and c: $Pr[C=c | M=m1] = Pr[C=c | M=m2]$ I also know that for all distributions of M, m1,m2 and c: $Pr[M=m1 | C=c] = Pr[M=m2 | C=c]$ Does ...
1
vote
1answer
2k views

Cryptography - Perfect secrecy => adversarial indistinguishability - proof

I'm just starting out with cryptography now and have gone over the various defnitions for a perfectly secret cipher. One of the equvilant definitons is adversarial indistinguishability. When trying to ...
1
vote
1answer
241 views

To which game-based security definition is Perfect Secrecy equivalent?

We all know the classic definitions of perfect secrecy, being $$\Pr[M=m|C=c]=\Pr[M=m]$$ and $$H(M|C)=H(M)$$ But now what I've asked myself: If we were to remove the polynomial restriction on the ...
4
votes
1answer
1k views

Does perfect forward secrecy (using DH or ECDH) imply quantum resistance?

Does perfect forwarding secrecy, as used for e.g. the DHE_ and ECDHE_ TLS ciphersuites make it impossible for quantum analysis ...
1
vote
0answers
547 views

Proving that Perfect Secrecy implies Adversarial Indistinguishability wrt. probabilistic adversaries

In their book Introduction to Modern Cryptography, chapter 2, authors Katz and Lindell ask the reader to show that perfect secrecy is equivalent to adversarial indistinguishability as an exercise. I ...
0
votes
2answers
301 views

Does shift cipher with non-uniform plain text probability have perfect secrecy?

I am having a hard time grasping the perfect secrecy concept. (I have already tried solving a couple of similar problems, so please don't think I am trying to get you guys to do my work, I really am ...
0
votes
1answer
687 views

Is there an encryption scheme that provides $Pr\{M_1 = m_1\wedge M_2 = m_2 | C_1 = c_1 \wedge C_2 = c_2\} = Pr\{M_1 = m_1 \wedge M_2 = m_2\}$

Question: Consider the following definition of perfect secrecy for the encryption of two messages.An encryption scheme (Gen, Enc, Dec) over a message space M is perfectly-secret fortwo messages if ...
2
votes
0answers
187 views

Showing that perfect secrecy implies adversarial indistinguishability

I've been reading the proof in these slides, the last page, and the author is using the lemma: $Pr[A(c)=1|M=m_0]=Pr[A(c)=1|M=m_1]$ I understand on the intuitive level that it's a consequence of the ...
1
vote
2answers
1k views

Can you help me prove perfect secrecy?

I'm actually new to cryptography and a friend of mine requested that I should read the Katz and Lindell book – “introduction to modern cryptography”. As I read the book I found it very interesting ...
9
votes
2answers
2k views

Definitions of secrecy

I found terms like "forward secrecy", "future secrecy", "backwards secrecy" and "perfect forward secrecy" and I would like to know their definitions and to understand the differences among them. I ...
0
votes
1answer
545 views

How can we prove that the following theorem is valid for almost perfect secrecy?

We have the following theorem: Let $\Pi$ be a perfectly-secret scheme over message space $M$, and let $K$ be determined by $Gen$. Then $|K| ≥ |M|$. How can we prove that the above theorem is ...
-2
votes
2answers
1k views

Is the one-time pad secure?

I have read about one-time pads (OTP) on Wikipedia. Is this secure? Can I actually use modular addition as ecryption like it said in Wikipedia? And the plaintext is as long as the OTP, so when I send ...
2
votes
1answer
644 views

An example of of an information theoretically secure protocol that is not cryptographically secure

Does there exist a protocol $\pi$ for some functionality $F$ which is information theoretically secure protocol that is not cryptographically secure for some threshold number of corrupt parties? ...
3
votes
2answers
350 views

How to prove a symmetric encryption scheme provides perfect secrecy?

I learned in class that in order to achieve perfect secrecy, the source of the plaintext $\mathcal{P}$ needs to be independent from the source of the encryption key $\mathcal{K}$. We also learned that ...
2
votes
3answers
548 views

How do I create a secure encryption scheme using addition?

You have a 4 number long PIN code with each number ranging from 0 to 9 which you wish to encrypt. You are then given a random 4 digit number ranging from 0 to 9999, which when added to the original ...
3
votes
1answer
56 views

Generate a random number $r \in \{1,2, \dots , k\}$, where $k$ is not public and is distributedly held

A set of parties can securely generate a random number $r \in \{1,2,3,\dots, k\}$ when $k$ is publicly known. However, can we generate the random number $r$ if $k$ is not publicly known and is held by ...
1
vote
1answer
79 views

Optimal threshold for passive and perfect security

The authors of the book titled "Secure Multiparty Computation and Secret Sharing" claim that there exist functions which cannot be computed with passive perfect security for $t \geq n/2$ corrupt ...
3
votes
2answers
10k views

Shannon theorem of perfect secrecy

From the class: Shannon Theorem: For a perfect encryption scheme, the number of keys is at least the size of the message space (number of messages that have a non-zero probability). Proof: ...
3
votes
1answer
106 views

2 party AND computation under passive perfect security

In the book written by Ivan Damagard titled "Secure Multiparty Computation and Secret Sharing", at the end of the third chapter he provides a proof for why it is impossible to securely compute 2 party ...
3
votes
0answers
426 views

Perfect secrecy is maintained for other plaintext prob distributions?

Suppose a cryptosystem achieves perfect secrecy for a particular plaintext probability distribution. Prove that perfect secrecy is maintained for any other plaintext probability distribution. Having ...