Questions tagged [security-definition]

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

Filter by
Sorted by
Tagged with
2
votes
2answers
1k views

Why the definition in $\epsilon$-differential privacy is multiplicative rather than additive?

According to its mathematical definition, a random algorithm $M: D\rightarrow R$ satisfies $\epsilon$-differential privacy if the adjacent datasets $x, y \in D$ where $D$ is a whole dataset and ...
3
votes
1answer
308 views

Comparison of security definitions for signatures

The two main security definitions for signatures are EUF-CMA and the strong version of it sEUF-CMA. What I see that their difference is that in EUF-CMA experiment, the adversary needs to produce a ...
1
vote
1answer
76 views

Why is the security level defined by $\log _{2} \inf \{ t_{i}/\varepsilon_{i} \mid i \in I \}$

In public-key cryptography, the security level indicates the strength of an adversary in breaking a scheme or solving a problem, which can be seen as the time cost of breaking a scheme or solving a ...
2
votes
1answer
411 views

Formal definition of collision resistance for hash function

In my cryptography class, the professor said that collision resistance for a fixed hash function is not a "precise" definition. The reason is since a fixed hash function is a single instance of a ...
3
votes
2answers
515 views

Differential privacy definition

Differential privacy defines "privacy" of a mechanism $A$ as the "closeness" of the two distribution $Pr[A(D) \in S]$ and $Pr[A(D') \in S]$ where $D,D'$ differ in one element. And the distance between ...
14
votes
2answers
917 views

Does GCM (or GHASH) only provide 64-bit security against forgeries?

In a recent comment a doubt was voiced about my answer, which claims GCM to requires $2^{128}$ for a successful forgery. The doubt was that the square root needs to be taken meaning the security would ...
1
vote
1answer
167 views

What is the security model of the FHE system introduced in Fully Homomorphic Encryption Using Ideal Lattices?

How would one construct a security model to play against the adversary, and define the security of the overall scheme? This is in reference to the scheme introduced in "Fully Homomorphic Encryption ...
3
votes
1answer
164 views

Definition of symmetric cipher and definition of asymmetric cipher

So I'm currently taking a cryptography class right now and my professor has told the class that she can't even define symmetric cipher for us without getting into asymmetric ciphers and the textbook ...
7
votes
3answers
386 views

Is there a cryptographic approach to availability

Background Cryptography can be said to provide the tools used to fulfill the goals of information security. The three pillars of information security are confidentiality, integrity, and ...
4
votes
1answer
645 views

What's the difference between perfect security and unconditional security?

This paper refers to two distinct security models: perfect security and unconditional security. Until now, I knew of them as the same thing and equivalent to information-theoretic security. From the ...
1
vote
0answers
145 views

Non-Repudiation vs Identity-Binding

There are 3 properties offered by a cryptographic digital signature scheme: Integrity guarantee of the message signed. Authenticity guarantee of the message signed. Non-repudiation of the message ...
2
votes
2answers
1k views

Identifying negligible functions

I am having a hard time understanding and applying the formulas that are used to identify a function is negligible or not? One text defines it as; a function $f$ from the natural numbers to the non-...
4
votes
2answers
284 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 ...
1
vote
0answers
211 views

Indistinguishable encryptions and CPA-secure example

Let $ F $ be a PRF and $ G$ be a PRG with expansion factor $n \to n +1 $ For the following encryption scheme, decide whether it has indistinguishable encryptions and whether it is CPA-secure. ...
1
vote
2answers
215 views

How is n-bit security calculated with nested encryption?

What will the total $n$-bit security be if I encrypt a message with a 128-bit XOR cipher and then take that ciphertext and encrypt it with a 128-bit key. Is the total security level now 256? One ...
3
votes
2answers
386 views

Can the key-generation algorithm always be uniform?

Assume that the encryption uses $n$-bit keys to encrypt $l(n)$-length messages. If a symmetric key encryption scheme is defined as $\Pi_{1} = ( \mathrm{Enc}, \mathrm{Dec} )$, then for every $x_{0}, ...
5
votes
1answer
160 views

Parameterizing adversaries with security parameters

In many cryptographic games, the adversary doesn't seem to be parameterized by the security parameter.‡ Are such games equivalent to variants in which the adversary is parameterized by the security ...
0
votes
2answers
261 views

Does encryption using PRP mean indistinguishable encryption against an eavesdropper?

I am a student studying cryptography by reading "Introduction to Modern Cryptography". I have some confusion about encryption using PRP (e.g., AES). Briefly speaking, a keyed deterministic ...
1
vote
1answer
214 views

Is the simulation-based proof difficult and needed? [closed]

What is the role for simulation-based proof under the semi-honest model without considering malicious adversaries? I agree with that a view of a some party is important to prove that a protocol is ...
4
votes
1answer
489 views

Is the practice of "security through obscurity" violating Kerckhoffs's second principle?

Security through obscurity is the reliance on the secrecy of the design or implementation as the main method of providing security for a system or component of a system. Kerckhoffs's second principle:...
0
votes
1answer
154 views

What does $1^n$ mean? [duplicate]

I often see the notation of powers of 1 in cryptography papers. For example, let $n$ be security parameter, then what does $1^n$ mean?? From high school student perspective, powers of one is always ...
1
vote
0answers
133 views

Mersenne Twister's vulnerabilty with small-size distributions

C++ rookie here, trying to wrap his head around (CS)PRNGs. I (assume that I) already understand the concept of the Mersenne Twister being "broken" (i.e. not cryptographically secure) due to its ...
5
votes
1answer
3k views

Difference between semi-honest and malicious adversary using Ideal Real Model Paradigm

Would you please explain to me why in the security definition of ideal/real model paradigm which is described in the efficient secure two-party protocol book(Hazay, Lindell), the simulator tries to ...
2
votes
1answer
165 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 ...
0
votes
1answer
80 views

Is function Deterministic or Probabilistic in the malicious security definition?

As you see, according to the attached definitions from "Efficient Secure Two-Party Protocols", the definition of the security in the semi-honest world has two cases for $f=(f_1,f_2)$.(deterministic ...
0
votes
1answer
70 views

Fairness and guaranteed output delivery

Why for achieving the fairness and guaranteed output delivery, less than a half of the parties should be corrupted? ($t < m/2$, where $t$ is the number of corrupted parties and $m$ is the total ...
4
votes
1answer
536 views

Strong One-Way Function

In the book "Foundations of cryptography-Oded Goldreich-Page 33", if we use the deterministic polynomial-time algorithm instead of the probabilistic polynomial-time algorithm for case 2 (Hard to ...
-1
votes
1answer
62 views

Which of these deductions are true about the simulator and the adversary?

Which of these deductions make sense? The simulator is actually being run by the adversary. It makes sense that the adversary initializes the simulator (which is just a program) with the input that ...
1
vote
0answers
47 views

Proofs of security for anonymity in a multi-party setting

I'm looking for material that proves the anonymity of parties in a non-interactive setting. I would like to know if there are simulation based proofs (UC) and property based proofs (game based) for ...
1
vote
1answer
89 views

Any Arbitrary Function

According to the attached reference, does it mean that the adversary computes $PPT(initial~input)$, $PPT(z)$ and $PPT(f_i(x',y'))$? For example, suppose the corrupted party, in the malicious model, ...
3
votes
1answer
186 views

The interaction between the malicious Adversary and the Simulator and Real-Ideal' views

This example is from “Efficient Secure Two-Party Protocols-Carmit Hazay-Yehuda Lindell”. And the security proof of the above example is this: I have drawn a picture that is deduced from the above ...
1
vote
1answer
91 views

A problem exists with the security proof in the secure AND example in the malicious model [closed]

Imagine that the malicious adversary in the real world uses $Y = 0$ as its input, therefore he computes the output as ($X$ && $y=0$) = $0$. We can conclude that the real view in the real world ...
3
votes
1answer
150 views

Security proof in the Malicious Model

According to the above protocol(Efficient Secure Two-Pary Protocols-Hazay-Lindell-page 27), the authors proved the security of this protocol according to the two paragraphs below: We separately ...
0
votes
1answer
80 views

Using the security definition in the malicious model to prove security in the semi honest model

Can I use the security definition in the malicious model in order to prove the security of a two-party protocol which is in the semi-honest model? (I am using IDEAL/REAL Model paradigm) Would you ...
2
votes
1answer
151 views

How to use Real-Ideal model in a specific scenario (two party with cloud)

I have designed a two-party protocol where two parties outsource their input to the cloud. For example, Alice and Bob have inputs $X$ and $Y$, respectively, after which Alice and Bob encrypt their ...
3
votes
1answer
365 views

difference between the uniform and non-uniform probabilistic polynomial algorithms (ppt)

I am reading the book "Efficient Secure Two-Party Protocol". A question came to my mind. why has the author used a probabilistic polynomial time algorithm for security definition of ideal/real model ...
11
votes
3answers
2k views

How small is negligible?

When proving theorems in crypto we often make use of the concept of negligible functions or, more simply, negligible parameters. As a rule of thumb, given today (2018) computational power, what is ...
5
votes
2answers
406 views

What is the relationship between entropy conditioning and final output bias in a TRNG?

This question concerns the conditioning and output of true random number generators. It refers to NIST Special Publication 800-90C, Recommendation for Random Bit Generator (RBG) Constructions. It ...
5
votes
1answer
276 views

"Power of one" as input to functions of a cryptosystem

What does $1^\lambda$ mean when you pass it as a parameter to the functions of a cryptosystem. The cryptosystem in question is this and a picture reference is this. I have been told it signifies the ...
4
votes
2answers
229 views

Is there a computational security of public-key encryption which is similar to the one of symmetric key encryption

We say a symmetric key encryption scheme $\Pi_{1} = (\mathrm{Gen}, \mathrm{Enc}, \mathrm{Dec})$ is computational security if for every PPT algorithm $A$ and every $x_{0}, x_{1}$ ($|x_{0}| = |x_{1}|$), ...
3
votes
1answer
161 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
82 views

Maximum value of negligible probability?

We can see on many papers for cryptography that there are many uses of negligible probability to ensure something (security, correctness, etc). How can we say that some probability is negligible? I ...
1
vote
0answers
43 views

A qusetion about the security game of Certificateless signatures

Recently I read Certificateless Public Auditing for Data Integrity in the Cloud , I have a question about the security of proposed HOMOMORPHIC AUTHENTICABLE CLS. (Sec. IV). For the Type-I Adversary, ...
1
vote
1answer
106 views

In "Lecture Notes on Cryptography" what does "PTM" mean?

I came across a handbook named "Lecture Notes on Cryptography" from Shafi Goldwasser and Mihir Bellare and I read their definition 3.1 about poly-time indistinguishability: Let $X_n,Y_n$ be ...
5
votes
1answer
2k views

Signature with appendix

I see sometimes signatures schemes with appendix. This is about signatures schemes in which the message is needed in the verification algorithm, that is, the ouput of the signature algorithm is of the ...
3
votes
1answer
408 views

security against CPA attack?

Let $\mathcal{E} = (E,D)$ be a CPA secure cipher. Let's define $\mathcal{E'} = (E', D')$, where $E'(k,m) = E(k, E(k,m))$. How can I prove that $\mathcal{E'}$ will be CPA secure if $\mathcal{E}$ is? ...
-1
votes
2answers
384 views

Secure pseudo-random generator

Suppose that $G : \{0,1\}^k \rightarrow \{0,1\}^{2k}$ is a secure pseudo-random generator. Describe what is wrong with each of the following attempts to build a pseudo-random generator with $k$-bit ...
16
votes
6answers
3k 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 ...
5
votes
0answers
163 views

Explanation of the term "view" for algorithm or adversary

What is the view of an algorithm/adversary? Is view just a term used to describe the output over a set of inputs for a probabilistic algorithm? For example: Consider experiment Mac-forgeA,Π (n). ...
1
vote
0answers
296 views

Design flaw in IND-CKA definition of Searchable Symmetric Encryption?

I am a graduate student interested in searchable encryption research. I carefully read the Secure Indexes paper published in 2004, and I was confused about the IND-CKA, the game-based security ...