Stack Exchange Network

Stack Exchange network consists of 174 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 [semantic-security]

produces ciphertext that, by itself, does not reveal information about the original message besides its length

3
votes
1answer
254 views

Is SHA1 secured enough as a PRNG

I read SHA1 is still a secured hashing function with no collision found as of now. However, it's just a matter of time for someone to come up with such a collision or attack. Therefore, in new ...
14
votes
7answers
3k views

Possibility of Chosen Plaintext Attack (CPA) in real-world scenario?

In CPA, it is said that the adversaries get ciphertext for the choice of plaintext of adversaries through an encryption oracle. Is this a realistic assumption in real-world, in which the adversaries ...
1
vote
1answer
37 views

Random semantic security and bijective PRGs

I'm working through Boneh and Shoup's "Graduate Course in Applied Cryptography", and have just finished reading the chapter on stream ciphers and PRGs. The first exercise for this chapter introduces ...
1
vote
0answers
145 views

Leak information (new setting)

This question is similar to Leak Information?, but with new settings. Let $a,b,c,d,e,f$ be selected at random from $\mathbb Z^*_q$. Also, let $r_1,r_2,r_3,z_1,z_2,z_3,p_1,p_2,p_3$ be selected at ...
1
vote
2answers
180 views

Leak Information?

Let a,b,c,d be selected at random from $\mathbb Z^*_q$. We pick values $r_1,r_2,r_3,z_1,z_2,z_3 \gets \mathbb Z^*_q$. Do $u_1,u_2$ that are computed as follows, leak information about values $a,b,c,d$...
4
votes
0answers
113 views

computational indistinguishable/distinguishable?

Let $a,b,c,d$ be selected at random from $Z_q$. Consider the following two distributions $X_1$ and $Y_1$: $X_1={(r_1\cdot a, r_2\cdot b, r_3\cdot c, (r_1+r_2-r_3)\cdot d)}$ where $r_1,r_2,r_3$ ...
0
votes
2answers
49 views

Why isn't E' secure if it's built over a secure cipher?

Let $E$ be a semantically secure cipher. Let $E'(k,m) = E(k,E(k,m))$. How would one prove that $E'$ is not necessarily secure even if $E$ is? It doesn't make sense to me. If you consider the ...
0
votes
0answers
38 views

Inner Product Predicate

what means this ? This is formalized by a simulator that generates a view given the inner-products values, and the adversary tries to tell apart if it’s interacting with the simulator, or if it has ...
1
vote
1answer
85 views

Build a cipher that is secure against message recovery attack but not semantically secure

I know the definitions of both of the securities (against message recovery and semantic), but I don't know how to actually build a cipher that meets these conditions, I mean, I don't know how to ...
0
votes
0answers
52 views

Understading security proof of proxy re-encryption scheme (AFGH06)

I'm trying to understand the reasoning behind the security proof in "Improved Proxy Re-Encryption Schemes with Applications to Secure Distributed Storage" by Ateniese et. al, Appendix A, Theorem 3.1: ...
2
votes
1answer
251 views

Proving that a function is negligible

My question is about proving that a function is negligible if it is ran polynomial number of times. This my solution: By the definition of negligibility, we have $negl_1(n) < 1/p'(n)$ where $p'...
1
vote
1answer
160 views

Proof that pseudo-random generated key is semantically secure

Let $G: \{0,1\}^s \rightarrow \{0,1\}^r$ where $r > s \;$ be a secure pseudo-random generator. Let $\xi = (E,D)$ a semantically secure cipher whose key space is $\{0,1\}^r$ Let $\xi' = (E',D')$ ...
0
votes
0answers
33 views

The output of experiments Real and Ideal in simulation-based security proof

For simulation-based security proof in searchable encryption, there are two experiments running for the Real and the Ideal world respectively. I can understand that the Real world experiment taking ...
0
votes
1answer
683 views

IPSec vs SSL : Similarities and Differences

I am studying SSL and IPSec. I can pretty much nail down the "very high level" differences and similarities between the two, but am struggling to find a "lower level" (but not too deep) look. This ...
3
votes
1answer
327 views

Indistinguishability versus semantic security?

I found some foundations of crypto course notes that mention that these two are equivalent statements of their own degrees of security and was given the following definitions: I was always under the ...
1
vote
1answer
112 views

is the perfect secrecy of one time pad dependent on the xor randomness preserving property?

Is the perfect secrecy of the one time pad dependent upon the xor "randomness preserving" property (xoring a uniformly random string with any string yields a uniformly random string)? I have seen ...
1
vote
1answer
48 views

What does the “Type 1 query” model on Miles, Sahai, and Zhandry's paper?

On the paper Annihilation Attacks for Multilinear Maps: Cryptanalysis of Indistinguishability Obfuscation over GGH13, authors present, in section 2, an abstract model to analyze security of $i\mathcal{...
2
votes
3answers
96 views

Security of stream cipher with a priori knowledge of message

I am generating a ciphertext by XORing the message bits with key stream bits of a stream cipher. But, if I know a priori that message bits contain a predefined number of 0's (say 60%) at unknown ...
0
votes
1answer
191 views

Difference between secure PRG and and semantically secure

I am taking cryptography course in coursera by Stanford University. and I have following question I have a question why append 0 in G(k) i.e., G'(k) = G(k) || 0 is considered as not secure PRG as ...
1
vote
0answers
294 views

Semantically secure, but not CPA secure?

I'm just starting to read a cryptography book and I'm having trouble understanding this. I know that semantically secure means that the adversary cannot learn any significant information seeing the ...
0
votes
1answer
124 views

Who defined semantic security?

In my opinion the most important development in cryptography in the last 30 years is the precise definition of semantic security of a cipher. This definition captures the intuitive ideas of Martin ...
0
votes
1answer
31 views

Security of semantically secure ciphers when the attacker knows the relation between plaintexts

This question is about the security of public-key ciphers when related plaintexts are encrypted by the same encryption key. Take Paillier for example. I know that Paillier is semantically secure under ...
1
vote
2answers
127 views

Homomorphic encryption and approximated GCD

I am reading the paper Fully homomorphic encryption over the integers (PDF). The paper reduced the security to the approximated GCD problem. My first question is whether the scheme proposed by the ...
2
votes
2answers
181 views

Is this authentication system insecure or not

So I want to create a simple, fast and yet secure authentication in two steps for a PC - microcontroller communication. The first step is a seed request, the second step is an authentication request. ...
3
votes
1answer
476 views

How does Signal Messenger's Safety Number Works?

Why do they recommend the user to verify the 60 digit code in person or via other medium of communication. How is the security code generated and work on Signal and Whatsapp Messanger?
0
votes
1answer
87 views

How secret key is sent in cipher-texts?

Secret key is included in cipher text. so how can we say that if hacker grab the cipher text he will not be able crack the code? if he cannot do with cipher-text then how receiver can crack the ...
1
vote
2answers
87 views

security of design for sending files

let's say I have a protocol to send a fi le $F$. I am intending to employ AES in CBC mode for encrypting $F$ where the $IV$ is randomly chosen. For authenticity, I am employing $HMAC$ to compute a ...
2
votes
2answers
437 views

semantic security of RSA variant

I am thinking of a variant of RSA. I know that RSA itself is not semantically secure as it is "deterministic". I have a "randomized" variant of RSA in mind. Suppose that the public key is $<e,n&...
2
votes
1answer
75 views

Any case that can require to encrypt a certificate revocation list before distribution

As far as we know certificate revocation lists (CRLs) include public information so they do not have to be encrypted before distribution. Is there a case that can require to encrypt it before ...
0
votes
0answers
53 views

Reversing Psuedo Random sequence geenration

Suppose I have given degree of correlation, $\alpha$ for two sequences generated from LFSR. Can I back trace and generate two sequences for a given $\alpha$ and length $N$? $111111$, $\alpha$ =0.5 ...
1
vote
1answer
241 views

Is $E′(k,m)=E(0^n,m)$ semantically secure?

$(E,D)$ is a (one-time) semantically secure cipher where the message and ciphertext space is $\{0,1\}^n$. $E'(k,m)$ is defined as $E′(k,m)=E(0^n,m)$ The question is whether $E'(k,m)$ is (one-time) ...
1
vote
1answer
101 views

A question about fully homomorphic encryption (FHE)

Hypothesis: We define the messages on a field $\mathtt{F}_p$, where $p$ is a large prime number. I am considering a dynamic outsourced private data scenario. Assume we have 3 messages: $m_1=2, m_2=...
4
votes
1answer
207 views

How to prove hardness of approximate-GCD problem?

I am trying to prove the security of my system using the hardness assumption of the approximate-GCD problem using contradiction, i.e. If the attacker is able to break in our scheme, then attacker ...
0
votes
0answers
24 views

Value of security through amiguity?

Let's say that you have a symmetric cipher which takes in an 8 bit plain text value and a key, and generates cipher text which can be decoded using the key to get the original plain text value. Since ...
1
vote
1answer
78 views

Secure blinding factor switching at malicious server-side (Switching in One Time pad)

Suppose all the values and operations are defined over a finite field $\mathbb{F}_p$ where $p$ is a large prime number. Assume all values are non-zero. Here $(z)^{-1}$ denotes multiplicative inverse ...
3
votes
1answer
337 views

Homemade Randomized RSA

Considering the following encryption scheme where RSA is used to encrypt a plaintext m and then we choose a random r and compute: $$A = r + m^e \bmod N$$ and $$B = r^e \bmod N$$ So the ciphertext is ...
4
votes
1answer
344 views

Decisional Diffie-Hellman: compute Legendre symbol of $g^{ab}$ from $g^a$ and $g^b$?

From https://en.wikipedia.org/wiki/Decisional_Diffie%E2%80%93Hellman_assumption: Importantly, the DDH assumption does not hold in the multiplicative group $\mathbb {Z} _{p}^{*}$, where $p$ is prime....
6
votes
1answer
2k views

Why is “semantically secure” important for cryptosystems?

The first question: what is the exact definition of semantically secure? Basically, a cryptosystem is semantically secure if given the public key and the ciphertext, an adversary cannot learn any ...
2
votes
2answers
192 views

Semantic Security and Equal Message Length in the Context of Public Key Cryptography

A lot of definitions for semantic security make use an experiment $\text{Exp}$ which is performed between a challenger $\mathcal{C}$ and an adversary $\mathcal{A}$ that begins as follows: $\mathcal{C}...
6
votes
1answer
196 views

Designing Secure Multi-Party Computation Sub-Protocols Based on Homomorphic Encryption

When designing SMPC protocols using secret-sharing, it is a common approach to compose a protocol from several sub-protocols (each proven secure under the formal definition of security w.r.t. semi-...
9
votes
1answer
183 views

Attacks on elliptic-curve based cryptosystems through solving the Decisional Diffie-Hellman Problem with the Weil Pairing

Are there any examples of practical attacks on cryptosystems set over elliptic curves which utilize the easiness of DDH for certain choices of curves $E(\textbf{F}_q)$, and as such their lack of ...
31
votes
1answer
11k views

Easy explanation of “IND-” security notions?

There are many schemes that can advertise themselves with certain security notions, usually IND-CPA or IND-CCA2, for example plain ElGamal has IND-CPA security but doesn't provide IND-CCA security. ...
1
vote
1answer
118 views

The encryption scheme is secure?

I have a scheme and I don't know that this scheme is semantic security or not. Secret keys $\{s_1,s_2, x_1,x_2\}$ and public parameter $p$ (large prime number). Encryption E(m): $C_1 = s_1m + x_1k \...
7
votes
2answers
5k views

Proving the semantic security of the One Time pad

Currently hearing a lecture on cryptography, and the professor gave us the definition of semantic security, which is roughly the following (formally not quite complete, but you get the idea): Given ...
1
vote
1answer
79 views

Key escrow on indistinguishability games

Does it mean that when PPT attacker is breaking an indistinguishable based (equivalent with semantic security) game with non negligible probability that he is able to infer the secret keys either on ...
1
vote
1answer
193 views

Is elliptic curve point multiplication semantically secure?

Is elliptic curve point multiplication semantically secure? I'd like to know if there are some sets of elliptic curve parameters (e.g. NIST curves) that are proved to be semantically secure or that ...
1
vote
0answers
76 views

Does not using padding mean a lack of security?

I've read several texts which say that if the entire plaintext is a multiple of the block-size padding is not required (and not using padding would not mean a loss of security). I generally disagree ...
1
vote
1answer
594 views

Semantic Security Active or Passive attacks?

I'm reading A Practical Public Key Cryptosystem Provably Secure against Adaptive Chosen Ciphertext Attack and here define Semantic Security ... Semantic security, dened by Goldwasser and Micali [14]...
4
votes
1answer
3k views

Perfect Secrecy -> One Time Semantic Security -> Secure PRG

I think I have some sense of what Perfect Security means, and even Semantic Security, but I am struggling with randomness, so I'm going to ask a question about CSPRG's (Cryptographically Secure PRG's) ...
6
votes
1answer
422 views

Homomorphic Encryption and Semantic Security using Lattices?

I've been reading Brakerski and Vaikuntanathan's "Efficient Fully Homomorphic Encryption from (Standard) LWE" and I'm still digesting pieces at a time. Under section 1.1, "Re-Linearization: Somewhat ...