Questions about formal definitions of "security" for various cryptographic schemes (e.g. perfect secrecy, semantic security, ciphertext indistinguishability, etc.)

learn more… | top users | synonyms

8
votes
3answers
127 views

How to prove the security of block ciphers

I see very often proofs of security for asymmetric crypto algorithms, for instance, using reductions to known hard problems, or game based proofs... In the field of protocols (like authentication) it ...
0
votes
1answer
78 views

Difference left-or-right CPA security, IND-CPA security

I am trying to understand the notion of left-or-right-CPA (LOR-CPA) security for private-key encryption schemes introduced in my lecture. If I understood it correctly so far, the only difference to ...
15
votes
3answers
9k views

What are preimage resistance and collision resistance, and how can the lack thereof be exploited?

What is "preimage resistance", and how can the lack thereof be exploited? How is this different from collision resistance, and are there any known preimage attacks that would be considered feasible?
2
votes
1answer
30 views

On the security definition of password-authenticated key exchange

I found in all PAKE papers, the security is defined as something like this: Let $Succ(A)$ be the probability that an attacker $A$ successfully distinguished the session key from a random string. Then ...
3
votes
0answers
43 views

Quantifying bit security for smart-vercauteren encryption scheme

I am working on project that requires to compare in terms of security between two encryption schemes, one of them is the SV scheme. However, I dont know what are the steps exactly towards quantifying ...
1
vote
1answer
36 views

Are the definitions of IND-CCA secure and of IND-CCA secure under standard model identical?

Suppose there is a public key cryptosystem based on the discrete logarithm problem and let this cryptosystem be IND-CCA secure under standard model. Does this statement mean that the given ...
3
votes
1answer
115 views

The exact definition of a symmetric encryption

I have doubts for the definition of the decryption algorithm $D(.)$. I think I've already seen that the decryption returns a plaintext $M$ on input the key $K$ and $C=E_K(M)$. I have also seen that ...
-2
votes
0answers
38 views

What is the definition of Selective Security?

What exactly is the definition of "selective security"? For instance, it is used in [KSW'13] (Predicate Encryption Supporting Disjunctions, Polynomial Equations, and Inner Products), but is there a ...
6
votes
2answers
95 views

Confusion about definition of homomorphic encryption

I am trying to better understand homomorphic encryption, but I feel like I keep getting inconsistent information in the papers that I am reading. One of the papers I am reading says the following: ...
4
votes
1answer
58 views

Is there an example of a “robust, yet not private” SMC protocol?

I have been trying to understand the interplay between robustness and privacy of an SMC protocol. It is easy to come up with a protocol that is private but not robust. Can someone provide an example ...
0
votes
0answers
17 views

Is there a German word for computationally secure? [migrated]

This is mainly intended for German cryptographers and I think since the topic is really specific it's more relevant to ask this here than in a German language section. Cryptography is mainly based ...
13
votes
1answer
3k views

What stops the Multiply-With-Carry RNG from being a Cryptographically Secure PRNG?

Despite the fact that Marsaglia's MWC PRNG (multiply-with-carry random number generator) is considered to be "the mother of all RNGs", it does not seem to be considered to be a CSPRNG ...
0
votes
0answers
21 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
80 views

“Security” of SHA functions (Wikipedia), what does it mean?

Wikepedia's table Comparison of SHA functions mentions "Security(bits)" for some SHA functions. From the ratio (Output size (bits): Security(bits)), I feel it is something like "collision resistance". ...
13
votes
6answers
8k views

Simply put, what does “perfect secrecy” mean?

I would like to ask for a clear (but maybe not so deep) explanation of what the term "perfect secrecy" means. As far as I have researched and understood, it has to do with probabilities of assuming ...
4
votes
2answers
93 views

Example of a PRP that is not a strong PRP

The exact definition of security for a pseudorandom permutation is straightforward - for some encryption scheme $E\,\colon\,\mathcal{K}\times\mathcal{D}\rightarrow\mathcal{D}$, it must be the case ...
1
vote
0answers
33 views

Can a secure MAC break if the adversary is given oracle access to Verify?

In the Mac-forge experiment, the adversary is given access to a tag-generation oracle, which generates a tag for each message given by the adversary. The adversary's task is to generate a valid tag on ...
3
votes
0answers
79 views

What is the difference between mutual authentication and unilateral authentication both ways?

I am currently reading Engineering Security by Peter Gutmann, on page 7 he states: proper mutual authentication is quite different from unilateral authentication in both directions He ...
2
votes
0answers
56 views

Q: Relevance of physical layer security to cryptography

I found that there are quite some active research activities in a field named "physical layer security", with in particular some types of codes that apparently are different from those commonly ...
0
votes
0answers
18 views

HMQV and MQV group representation attack

Currently reading Krawczyk's HMQV paper https://eprint.iacr.org/2005/176 and trying to follow what he says about the group respetnation attack on MQV: It says that for any group of prime order $q$, ...
6
votes
1answer
123 views

What is the difference between RCCA and CCA2?

Well, I know it's easy to tell CCA1 from CCA2, but I failed to find the difference between RCCA and CCA2. What is the difference?
2
votes
1answer
3k views

When NIST disallows the use of 1024-bit keys, what effect will that have on SHA-3 (with max. 512 bits)?

Quoting the article Gone in 60 Months or Less: The National Institute of Standards and Technology (NIST) has disallowed the use of 1024-bit keys after 31 December 2013 because they are insecure. ...
0
votes
2answers
140 views

Random Coin Flip

Quoting an old question: Consider the following protocol for two parties A and B to flip a fair coin (more complicated versions of this might be used for Internet gambling): A trusted ...
2
votes
1answer
102 views

What is the difference between CPA and IND-CPA?

I am writing a paper and I got comments from the reviewer that I don’t really understand. Is there any difference between a CPA (Chosen Plaintext Attack) and IND-CPA (Indistinguishability under ...
4
votes
1answer
93 views

Do Curtmola et al.'s IND-CKA1/2 security definitions protect against search pattern leakage?

In the article Searchable Symmetric Encryption: Improved Definitions and Efficient Constructions, Curtmola et al. propose adaptive and non-adaptive (indistinguishability and simulator-based) security ...
7
votes
2answers
275 views

Key Size for Symmetric Homomorphic Encryption Over the Integers

In the paper Fully Homomorphic Encryption over the Integers, it mentions a symmetric key scheme on page 1 and 2. Key Generation: Pick a random odd number $p \epsilon [2^{N-1},2^N)$ Encrypt A Bit m: ...
2
votes
1answer
182 views

Why is the definition of Special-honest verifier zero-knowledge probabilistic?

Let $P$ be a prover willing to prove to a verifier $V$ that he knows a witness $w$ satisfying $(x,w) \in R$ for some relation $R$ and some common input $x$. As found in the literature, $P$ can use a ...
3
votes
1answer
92 views

What does “simulator” and “interactive” mean in a cryptographic credential system's definition of security?

Definition 1 on Page 7 of “An Efficient System for Non-transferable Anonymous Credentials with Optional Anonymity Revocation” by Camenisch and Lysyanskaya, uses the term “simulator” in defining the ...
4
votes
1answer
119 views

Hard-core predicates: should the adversary be given $1^n$?

In most (all?) classical sources such as the book of Goldreich (2001), hard-core predicated are defined thus: A polynomial-time computable predicate $b : \{0,1\}^* \to \{0,1\}$ is a hard-core of a ...
1
vote
1answer
139 views

What is a man-in-the-middle attack (for instance in Diffie-Hellman)?

I'm new to cryptography and I just started learning about the Diffie-Hellman key agreement. I read that this system is vulnerable to a man-in-the-middle attack when used alone. What kind of attack is ...
10
votes
4answers
2k views

Is the one-time-pad a secure system according to modern definitions?

Occasionally I hear people say that one-time pads are "useless" or even "broken". "modern cryptography knows more security definitions, under some of which the one-time pad is completely ...
1
vote
1answer
105 views

Correctness in Multi-party Computation: Real/Ideal Paradigm in Malicious case

I need to know: 1- What does exactly correctness mean in this context? 2- How is correctness implied in malicious model? 3- If the correctness means " the adversary cannot cause the output to be ...
4
votes
1answer
671 views

Proofs by reduction and times of adversaries

I have some difficulties to understand, when we construct a reduction, how we determine the time for the constructed adversary to break a target security property. In general these details are not ...
3
votes
5answers
372 views

Effective security of block cipher – equal the key size, or half the key size?

The Wikipedia “Key Size” article states: The security of an algorithm cannot exceed its key length (since any algorithm can be cracked by brute force), but it can be smaller. … … … Most ...
0
votes
0answers
33 views

Outsourced Multiparty computation proof in Ideal world

I need to know in an outsourced two party computation where honst $A$ and $B$ outsource their private and secure data to a malicious server, why we need to design a simulator that interacts with an ...
0
votes
0answers
49 views

Role of trusted party in the Ideal model in Malicious case

Imagine there is a protocol supporting outosurced multi party computation. There are three parties involved in the protocol: client $A$, client $B$ and a server. Client $A$ and $B$ send their private ...
9
votes
3answers
3k views

What is the difference between uniformly and at random in crypto definitions?

Very often in the description and analysis of a cryptographic protocol there is a need for a an element $k$ that is sampled uniformly AND at random. Is there a redundancy in the definition with ...
1
vote
3answers
408 views

When is a cipher considered broken?

We've all read how some people claim AES is broken because there was supposedly a way to get the plain text from a cipher text faster than brute-force. But is this the definition? Is a cipher broken ...
0
votes
1answer
117 views

Is adaptive security the same as full security?

This question contains a great answer about adaptive security, but I haven't yet found a proper definition what full security is. Does a stronger security than adaptive security exist or are the two ...
11
votes
7answers
2k views

How exactly is “true randomness” defined in the realms of cryptography?

Especially in relation to stream ciphers, I frequently read about (sometimes theoretical, sometimes practical) attacks that are able to "distinguish a ciphertext from a truly random stream". What's ...
0
votes
2answers
249 views

What would be the best plain text Cryptography method without the use of a computer? [closed]

What would be the best Cryptography method without the use of a computer? This could be a list of the current options available, that could be used without the use of a computer ...
2
votes
1answer
266 views

Flaw in the security definition of *Stateful* Authenticated Encryption?

I'm in search of the correct definition of a stateful authenticated encryption scheme (sAE), and its related security notion. This has been treated several times in the academic literature, however, ...
3
votes
2answers
212 views

What, cryptographically speaking, is a “long message”?

I have read about long message attacks on some cryptographic hash functions. However, I don't quite understand what is being referred to as a "long message". Also, do long message attacks only apply ...
6
votes
1answer
464 views

Understanding Twist Security with respect to short Weierstrass curves

I'm trying to understand the "Invalid-curve attacks against ladders" section of SafeCurves Twist Security page and I have difficulties to apply it to short Weierstrass curves. That section claims ...
2
votes
2answers
292 views

What is a q-type assumption?

I've seen the term "$q$-type assumption" used in a few papers without a definition. A google search doesn't seem to come up with anything useful either (except the same papers without a definition). ...
2
votes
0answers
75 views

Bridging the gap between security proofs and “real-world” security

I've been studying cryptography for a little while. I understand fairly well the nuts and bolts of security proofs, but I'm having trouble reconciling the formal statements of security in these proofs ...
0
votes
1answer
373 views

Security properties and Cryptography objectives applied in algorithms

We all know there are five properties of Security. They are: Confidentiality Availability Authorization Integrity and Provenance As Security and Cryptography are co-related these properties ...
1
vote
0answers
109 views

Privacy-Preserving Protocols and Proofs of Security

While dabbling in privacy-preserving protocols (mainly using Semi-Homomorphic Encryption) and coming up with miscellaneous ideas for comparison tests or other similar primitives, based on obfuscation ...
7
votes
2answers
1k views

Why is AES considered to be secure?

The security of RSA is based on the integer factorization problem, which is a very well defined and understood mathematical problem. This problem must be solved in order to fundamentally break RSA. ...
5
votes
1answer
676 views

An unpredictable PRG is secure (Theorem Yao'82)

in the Mr Boneh's online course is stated the following theorem: Let $G:K \to \{0,1\}^n$ be a PRG. “Thm”: if $\forall i \in \{0, … ,n-1\}$ the PRG $G$ is unpredictable at pos. $i$, then ...