# Questions tagged [security-definition]

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

242 questions
Filter by
Sorted by
Tagged with
59 views

### Groth16 simulate zero-knowledge proof for invalid statement

The zero-knowledge property of the Groth16 (https://eprint.iacr.org/2016/260, page 8) non-interactive zero-knowledge argument is based on the existence of a simulator $\text{Sim}$ generating "...
31 views

### Necessity of non determinism for multiple message security

In Katz & Lindell's textbook (2nd edition)) is said, that only non deterministic encryption can lead to security for multiple encryptions. Now I looked at the experiment for multiple ...
52 views

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 ...
446 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)...
80 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, ...
68 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)...
29 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 ...
50 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 ...
22 views

### Besides block-cipher which other methods can only be computed step-by-step even with known secret (but fast per step) and can be inverted?

Depending at the cryptographic function used applying it $i$-times to a given input can be computed in different complexity classes (based at their input size). $$f^i(m_0) = c_i$$ For example for most ...
47 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 ...
96 views

### Superscript vs subscript notation in cryptographic formulation

I'm currently reading this paper [PDF]. On page 4, I bumped into these notations : \text { Experiment } \operatorname{Exp}_{\mathcal{F} \mathcal{E}, A}^{\text {ind-mode }}(k) \text { :...
76 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 ...
82 views

52 views

### Question about game based security

When a game between an adversary $A$ and a challenger $CH$ is used in the security model of a scheme, and oracles are defined, does the adversary only have access to those oracles in the attack or ...
50 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 ...
40 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). ...
36 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 (...
42 views

134 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 ...
104 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 ...
120 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$, ...
196 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 ...
65 views

241 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 ...
62 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$...
47 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 ...
76 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 ...
189 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 ...
99 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?
239 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 ...
104 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 \$...