Questions tagged [security-definition]
Questions about formal definitions of "security" for various cryptographic schemes (e.g. perfect secrecy, semantic security, ciphertext indistinguishability, etc.)
288
questions
1
vote
1
answer
97
views
Adaptive Security Advantage
Adaptive model: the attacker can adaptively query the challenger for private keys. The challenge message need not be revealed at the start of the security game
Selective model: the attacker has to ...
1
vote
3
answers
518
views
Post quantum security experiment
In cryptography there are 4 basic attack classifications:
Ciphertext-Only Attack
Known-Plaintext Attack
Chosen-Plaintext Attack
Chosen-Ciphertext Attack
In Katz & Lindell's textbook (2nd edition)...
- 2,120
2
votes
0
answers
147
views
Difference between an authentication scheme and a identification scheme in ZK proofs?
EDIT: I want to specify what I know about schemes security:
Authentication schemes: P can prove V he is P, and nobody else can prove V that they are P.
Identification schemes: P can prove V he is P, ...
- 131
1
vote
1
answer
632
views
KPA-Security definition
In cryptography there are 4 basic attack classifications:
Ciphertext-Only Attack
Known-Plaintext Attack
Chosen-Plaintext Attack
Chosen-Ciphertext Attack
In Katz & Lindell's textbook (2nd edition)...
- 2,120
1
vote
0
answers
83
views
Exact security requirements for extendable output functions (XOF)?
In the FIPS202 document "SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions" an extendable-output functions is defined as:
An extendable-output function (XOF) is a ...
- 347
0
votes
1
answer
167
views
Reference for a formal definition of universal forgery and EUF-CMA
In many papers, I see EUF-CMA and SUF-CMA referenced as a canonical term used, but I did not find a reference paper/book that ...
- 347
0
votes
0
answers
85
views
How can a concatenation of $N$ block-cipher with known keys be more secure?
General problem / Intro: encrypting the (computable) relation in between two random numbers which are members of a as small as possible set while anything except the order of execution is known to the ...
- 573
1
vote
1
answer
187
views
Superscript vs subscript notation in cryptographic formulation
I'm currently reading this paper [PDF]. On page 4, I bumped into these notations :
\begin{equation}
\text { Experiment } \operatorname{Exp}_{\mathcal{F} \mathcal{E}, A}^{\text {ind-mode }}(k) \text { :...
- 878
1
vote
1
answer
129
views
Can a block-cipher considered secure if a bit-change of the input leads to a 50% chance change for every single output bit? -> round number?
Block-cipher use self-inverse ($f(f(x)) = x $) operations which then will be applied to the plaintext and most likely contain some constants which can be based at a key.
To get security such ...
- 573
4
votes
0
answers
852
views
2 different definitions of Special Soundness
There are 2 different definitions of special soundness in the literature:
(1) can be found in Damgard:
We say that a Sigma-protocol $\Pi$ satisfies special soundness, if there exists a PPT extractor $\...
- 173
1
vote
1
answer
175
views
The security of DDH with multiple instances?
Let $G$ be a finite group of prime order $p$, and $g$ a generator of $G$.
The standard DDH is hard to distinguish two distributions
$$
\{ (g, g^a, g^b, g^{ab}) : a, b \leftarrow \mathbb{Z}_p\} \text{ ...
- 149
1
vote
1
answer
47
views
Is it allowable to put a restriction on the length of the plaintext used in the known-plaintext attack?
The definition of the known-plaintext attack: I have a plaintext and I can encrypt it to have its ciphertext, then I use this pair to break the cipher.
The question:
The only thing I further assume is ...
- 407
1
vote
1
answer
722
views
MPC Definitions: UC-Security vs. Real-Ideal Simulation?
I consider the "standard" definition of maliciously-secure 2PC to be the simulation-based, ideal–real-world indistinguishability definition of e.g. Lindell's How to Simulate It [Lin17, ...
- 145
2
votes
0
answers
87
views
Encrypting random coins used for the encryption itself
Circular security notions for PKE schemes capture the security of (PKE) schemes when encrypting the secret decryption key.
Is there an analogous notion but for encrypting the randomness used for the ...
- 141
0
votes
0
answers
114
views
Shamir secret sharing in automated verification tools
Can Shamir secret sharing scheme (SSS) be verified using automated verification tools such as AVISPA? I read in the HLPSL manual that we cannot use arithmetic or relative operations such +,-,< ......
- 177
5
votes
2
answers
869
views
Statistical security parameter -> information theoretically secure
If a cryptographic protocol has a computational security parameter and a statistical security parameter, does this mean it is only computationally secure instead of information-theoretically secure?
I ...
2
votes
0
answers
161
views
Uniform vs Non-uniform Attackers
There is a concept of attackers gaining some information before attacking a system and those attackers being called non-uniform attackers. How do the security proofs for cryptographic primitives in ...
2
votes
1
answer
136
views
What do the "adversary state" and "internal coins" mean?
I was reading papers about searchable symmetric encryption these days and in the security definition part the author mentioned:
where state is a polynomially bounded string that captures A1’s state, ...
- 21
2
votes
1
answer
82
views
Why require that public and private key each have length at least the security parameter?
In Jonathan Katz and Yehuda Lindell's Introduction to Modern Cryptography (3rd edition), the key generator of e.g. signature has
The key-generation algorithm $\mathsf{Gen}$ takes as input a security ...
- 138k
1
vote
0
answers
60
views
If a different plaintext may produce the same ciphertext, is the system perfectly secure?
Define the injective map $\phi: \Omega\rightarrow \mathbb{N}$, such that $\Omega=\mathcal{A}^n$ denotes the set of all strings of length $n\in\mathbb{N}^*$ from an alphabet $\mathcal{A}$ of elements $...
- 11
1
vote
0
answers
54
views
Prove that secure authenticated encryption system composed with itself is secure
Suppose $(E,D)$ provides authenticated encryption with key space $K$. Define $(E',D')$ with key space $K^2$ as follows:
$$
E'((k_1,k_2),m) = E(k_2,E(k_1,m)) \\
D'((k_1,k_2),c) = \begin{cases}
D(k_1,E(...
- 111
1
vote
0
answers
56
views
Distributional Virtual Black Box security
Can anyone clearly explain the difference between these two notions of obfuscation security: VBB security and D-VBB Security.
VBB Security: An obfuscated program is no better than just a black box ...
- 31
0
votes
1
answer
114
views
Reduction to the discrete log problem
Let $G$ be a group of prime order $p$ and generator $g$.
Let $msk_i = (x_i, y_i) \in Z_p^2$ be two master secret keys and $mpk_i = (g^{x_i}, g^{y_i})$ the corresponding master public keys, $i \in [0, ...
- 567
1
vote
0
answers
58
views
How to compare two post quantum digital signature schemes in terms of latency?
I want to compare two digital signature schemes of different nature. One is Hash-based (Winternitz one time signature scheme) and the other is lattice-based (Dilithium Crystals). What about be an ...
1
vote
0
answers
48
views
How to evaluate number of security bits of a signature scheme?
I am trying to evaluate the effective security levels that a digital signature scheme (namely post-quantum digital schemes like WOT-S (Winternitz one time signature scheme) and Dilithium Crystals). ...
0
votes
0
answers
39
views
show that key recovery is not possible in a computationally secure system
(G, E, D) is a computationally secure encryption scheme over the message space $\{0,1\}^n$. Show that the probability that a PPT adversary can recover the key after seeing the encryption of a random (...
- 121
0
votes
1
answer
59
views
what's the reason of the notational difference between statistical and computational indistinguishabilities?
Statistical: $|\Pr[E_K(m_0)\in T]-\Pr[E_K(m_1)\in T]|\leq\epsilon$
Computational: $|\Pr[A(E_K(m_0))=1]-\Pr[A(E_K(m_1))=1]|\leq\epsilon(n)$
What is the $1$ doing there? Why isn't it $Pr[A(E_K(m_0))\in ...
- 121
4
votes
2
answers
313
views
What is Black-Box Obfuscation?
I understand black-box obfuscation at some intuitive level as- "an adversary can learn nothing more from an obfuscated program/circuit/function than he or she can from a black-box access to the ...
- 143
1
vote
1
answer
832
views
Does CCA-security implies CPA-security
While reading Katz & Lindell's textbook (2nd edition) if found three main security definitions: ING-EAV-Security, ING-CPA-Security and ING-CCA-Security. (From this forum I know there are more, but ...
- 2,120
1
vote
1
answer
123
views
Question on the disprove of CCA security
I have a question on the disprove of the CCA-security given in Katz & Lindell's textbook (2nd edition) in chapter 3.7 on page 97. It works like this:
Consider our construction based on PRFs: $\...
- 2,120
1
vote
1
answer
309
views
How does the security of Elliptic curve compare to normal discrete logarithm?
Intro:
EC are often compared with RSA but how about a more safe version of the discrete logarithm?
All 3 can be reduced to the problem:
$$b = g^a \mod{P}$$
In RSA $P$ is a product of two primes. To ...
- 573
3
votes
2
answers
219
views
Combined scheme security proof
Let CS be a combined scheme of $n$ public key subschemes.
CS is composed of two algorithms Setup and KeyGen, that all the subschemes share, plus all the other algorithms of each subscheme.
Suppose ...
- 567
2
votes
1
answer
628
views
Clarification of Advantage vs Probability/Success of an Adversary
In cryptography, for a polynomial time-bounded adversary $\mathcal{A}$, given a scheme $\Pi$, the success or probability of succeeding $\mathcal{A}$ is the likelihood for $\mathcal{A}$ to break $\Pi$, ...
- 445
2
votes
0
answers
388
views
An exercise to show that CBC Chain is insecure
The CBC-Chain mode of operation is a CBC variant in which the IV that is used for
the very first message to be encrypted is randomly selected, whereas the IV used for
each subsequent encrypted message ...
- 41
0
votes
0
answers
189
views
Question about IND-CCA security
We are given the following securitygame $G^{\text{LOSTNAME}}$:
Generate $k \leftarrow \{0,1\}^{\kappa}$ uniformly at random
Choose $h \leftarrow \{0,1\}$ uniformly random
Create decryption oracle $\...
2
votes
1
answer
138
views
GetModulus negligible probability
I have this textbook definition, I shall include below.
GenModulus denotes a ppt algorithm that, on input $1^n$, outputs $(N, p, q)$ where $N = p\,q$ and (except with negligible probability) $p$ and $...
- 145
1
vote
4
answers
1k
views
How long would it take all of the supercomputers or cloud computing on Earth to bruteforce a significantly long password?
I was arguing with a colleague who thinks that SHA256 (password + 64 character static salt) is "insecure." My argument is that nothing in cryptography is "secure," it's all a ...
1
vote
0
answers
96
views
How to formally define the security of Random Oblivious Transfer
Assume that there is a protocol $(A,B)$ such that receives no input and satisfies:
$A$ - outputs two random bits $x_0, x_1 \in \{0,1\}$
$B$ - outputs a random bit $b \in \{0,1\}$ and also outputs $x_b$...
- 155
1
vote
1
answer
51
views
Alternatives to simple bit-measured security for ciphers
For a cryptographic primitive, we usually see the security level measured in bits, where n-bit security means that the attacker would have to perform $2^n$ operations to break it.
For key-derivation ...
- 1,443
2
votes
1
answer
117
views
Not understanding deterministic authenticated encryption (DAE) security definition
I have a question regarding the security definition of deterministic authenticated encryption (DAE) as defined by Bellare and Shrimpton. Their definition is reproduced below, and my question pertains ...
- 2,695
0
votes
2
answers
633
views
Bits of security vs collision resistance?
I have been doing some research on security, and I am confused on the bits of security vs collision resistance, and I was wondering if someone could clarify my understanding.
For instance, if you have ...
- 3
4
votes
1
answer
493
views
What are the “costs” to find a pre-image, weak collision, or strong collision?
For a secure, n-bit hash function, what are the “costs” to find a pre-image, weak collision, or strong collision?
- 43
4
votes
1
answer
1k
views
When knowledge soundness implies soundness
In the work of Bellare–Goldreich that defines knowledge soundness BG92, the discussion of Section 4.5 specifically decouples knowledge soundness from soundness. That is, proving knowledge soundness ...
- 155
3
votes
1
answer
184
views
The number of cipher texts possible for each plaintext
This is from Dan Boneh's book
Theorem 2.1. Let X = (E, D) be a Shannon cipher defined over (K, M, C). The following are
equivalent:
(i) X is perfectly secure.
(ii) For every $c \in C$, there exists $...
- 2,169
0
votes
0
answers
44
views
What is a quantifier in game-based definitions?
I'd like to know what are quantifiers in game-based security definitions (in cryptography)
Some relevant examples and sources are also much appreciated.
Edit: for example, in a formal definition, we ...
- 442
2
votes
1
answer
94
views
Why do we need multiple adversaries in a game-based definition?
Consider we have a protocol, where multiple algorithms of it are run by an adversary.
When we want to define a game for that protocol (or its security properties), I have seen that an adversary is ...
- 442
1
vote
1
answer
78
views
Can we determine a security parameter in the hybrid argument where the number of hybrids is polynomially bounded but not known?
Let $\lambda$ be a statistical security parameter. Consider a security proof that is based on hybrid argument, where there are polynomially many (say, $n = p(\lambda)$) hybrids, $H_1, ..., H_n$. Any ...
- 414
0
votes
0
answers
165
views
Formal proof that the following definitions of perfect secrecy are equivalent
I've seen the following two definitions of perfect secrecy for an encryption scheme (Gen, Enc, Dec).
...
- 1
1
vote
2
answers
215
views
Proving security of $\Pi' = E_k(E_k(m))$ knowing $\Pi = E_k(m)$ is secure
I recently started studying cryptography but I am not sure I quite understand the concept of proof by reduction. Question I am trying to solve is as follow:
Suppose $\Pi$ is a symmetric encryption ...
- 35
4
votes
0
answers
198
views
Differences in definitions of "Computational Special Soundness"
I am looking at Unruh's transform (ePrint 2014/587) and in particular the definition in §2.2 for computational special soundness in sigma protocols. Let $\cal{R} \subset \cal{X} \times \cal{Y}$ be ...
