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
0
votes
0answers
32 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 (...
0
votes
1answer
35 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 ...
2
votes
2answers
84 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 ...
0
votes
1answer
47 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 ...
1
vote
1answer
43 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: $\...
1
vote
1answer
101 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 ...
1
vote
1answer
88 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 ...
1
vote
1answer
41 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$, ...
2
votes
0answers
87 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 ...
0
votes
0answers
36 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
1answer
72 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 $...
1
vote
2answers
122 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 ...
0
votes
0answers
46 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$...
1
vote
1answer
39 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
vote
1answer
57 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 ...
0
votes
2answers
72 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 ...
2
votes
1answer
54 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?
1
vote
1answer
167 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 ...
3
votes
1answer
91 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 $...
0
votes
0answers
24 views

Correctness and security of a scheme

Is correctness of a scheme considered part of the security of that scheme or is it separate? I've seen both approaches in different papers.
0
votes
0answers
33 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 ...
2
votes
1answer
53 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 ...
1
vote
1answer
38 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 ...
0
votes
0answers
60 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
vote
2answers
124 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 ...
0
votes
0answers
17 views

Integrated Signatures and Encryption Scheme

Suppose we have a scheme ISE that combines $n$ signature schemes and one encryption scheme, where the same keys are used. It is composed of the following algorithms: Setup, KeyGen, $Sign_1,...,Sign_n, ...
3
votes
0answers
43 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 ...
5
votes
4answers
217 views

What does perfect mean within perfect forward secrecy and why do some cryptographers disagree with the term?

In this blog post, Matthew Green says Forward secrecy (usually misnamed “perfect forward secrecy”)... The Wikipedia article on forward secrecy (which the same sentence links to in the blog) says ...
0
votes
0answers
96 views

ROLLO : security bits parameters

In ROLLO -Rank-Ouroboros, LAKE & LOCKER p.20, it says that "Notice that for 128 security bits parameters, the practical security is rather higher than 128 at about 170 bits." How Can I ...
4
votes
2answers
133 views

What is the difference between security parameter and $b$-bit security?

In a previous question, I read ... for $b$-bit security meaning $O(2^b)$ work for an attacker to break the system... While in Katz's Introduction to modern Cryptography, I read: The key-generation ...
11
votes
1answer
2k views

Meaning of “Security can be reduced to a problem”

I'm studying reductions in cryptography and confused about the way people use the word "reduction". My question is almost the same as a past question, but what I want to ask is slightly different. A ...
2
votes
1answer
257 views

RSA and the strong RSA assumptions

The RSA assumption: Given a randomly generated RSA modulus $n$, exponent $r$ and a random $z \in \mathbb{Z}_n^{*}$, find $y$ such that $y^r=z$. The strong RSA assumption: Given a randomly chosen ...
0
votes
0answers
19 views

Does multiple substitutions increase security? [duplicate]

Yes, because the attacker must decrypt the cypher text twice No, because it is equivalent to a single substitution Maybe, depending on the complexity of each substitution
0
votes
1answer
117 views

MAC security game

In the applied cryptography book by Boneh and Shoup, Chapter 6 on MACs, it is stated that one can modify SUF-CMA game by removing verify oracle access to the adversary. Therefore, the two versions are ...
1
vote
1answer
518 views

Seed/key algorithm security

Currently I'm working on implementing a seed/key algorithm to limit access to a tool for authorized users. My understanding of the algorithm is that its strength is derived from the seed itself. ...
0
votes
0answers
113 views

Importance of Backward and forward secrecy

Which security feature is more important in security protocols being used in different applications? Forward Secrecy or Backward Secrecy
0
votes
1answer
62 views

Research topics related to cryptography and Hamiltonian cycles

I am very interested in pursuing a research where I can show an application of Hamiltonian cycles in Cayley graphs of some group such as reflection groups to the field of cryptography. But currently ...
1
vote
0answers
145 views

Game-based proofs and semantic security

After reading this question, I understood that "game-based" and "simulation-based" have to do with the way that security properties are postulated. In particular, IND-CPA is a canonical example of ...
0
votes
3answers
352 views

Is a PRG concatenation using the same input still a PRG?

Suppose we have a secure PRG $G: \{0,1\}^s→ \{0,1\}^n$ and we define a $G'(k)$ as: $$ G'(k) = G(k) \| G(k) $$ So if $G(k)=\mathbf{i}$, $G'(k) = \mathbf{i} \| \mathbf{i}$ Is $G'$ still a secure PRG? ...
1
vote
1answer
53 views

Forward Security of Symmetric Encryption Schemes with LFSR based PRNG

Forward security can be achieved using symmetric encryption schemes by combining with a pseudo-random number generator (PRNG). Does LFSR based PRNG provide forward security in this case?
9
votes
1answer
1k views

Existential unforgeability vs strong unforgeability

In the article https://crypto.stanford.edu/~dabo/pubs/papers/strongsigs.pdf there are two definitions for the security of a digital signature scheme: existential unforgeability and strong ...
0
votes
0answers
41 views

Is this simple proposed scheme semantically secure?

Suppose we have two parties, including $P_1$ and $P_2$ using a type of symmetric encryption algorithm, say, AES256. Let's assume the shared key is: $K$. Encryption: Each party generate a key such ...
2
votes
0answers
39 views

decrypting a one-time-pad that outputs 0,1 in preknown probabilities

assuming a two users want to use a one time pad ciphersystem, and they are using a program that was developed by a third party that was supposed to create random undependable bits, but for some reason ...
2
votes
1answer
153 views

Does an information-theoretically secure hash function exist?

Does an information theoretically secure hash function exist? (By exist I mean is discovered/invented and implemented, not whether it could exist.)
2
votes
2answers
139 views

Collision resistant functions - definition

Let $f$ be a collision resistant function i.e. it is computationally impossible to find $x_0, x_1$ such that $f(x_0) = f(x_1)$. If a computationally bounded adversary demonstrates that he knows some $...
0
votes
0answers
58 views

DLP instances for given number of congruences

Let $S$ be the set of $k$ congruences of the type $g_{i}^{x_i} \equiv h_i \pmod{n_i}, \quad \forall i,1\leq i \leq k$ What would be the best way to describe such set $S$ with a term in literature. ...
0
votes
0answers
98 views

1-out-of-2 Oblivious Transfer Security

Just started reading Oblivious Transfer. I am searching for a proof of security based on RSA implementation but I can't find anything simple to understand. Can someone direct/show me to an easy to ...
0
votes
1answer
233 views

Security of this PRF [closed]

Given $F$ a secure PRF with input size $\lambda$. Define $F'$ as $F'(k,x||x') = F(k, 0||x)\oplus F(k, 1||x')$ with $x$ and $x'$ of $\lambda-1$ bits. Is $F'$ a secure PRF?
1
vote
1answer
43 views

Looking for a formula for “Given $x_1$, $\ldots$, $x_{n-1}$, the output $F(x_1,\ldots,x_n)$ is dependent of $x_n$ and is of $l$-bits security”

Suppose I have a function $F(x_1,\ldots,x_n)$, where each $x_i$ is of $l$-bits security (suppose each $x_i$ is a binary string of length $l$). At the same time, suppose there are $n$ persons, each one ...
1
vote
0answers
40 views

Precise Definition of 1-out-of-2 Oblivious Transfer

What's the precise definition for 1-out-of-2 OT? and what's the best way to show that it can't be achieved under unconditionally secure setting? I am reading about it and just couldn't get my head ...

1
2 3 4 5