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
1answer
46 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 ...
0
votes
0answers
48 views

QR code for products - Can there be duplication? [closed]

https://www.google.com/search?q=qr+code&oq=&aqs=chrome.2.69i177j69i59i450l14.-1j1j7&client=ms-android-lava&sourceid=chrome-mobile&ie=UTF-8 Is it possible that QR codes can have ...
0
votes
0answers
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 ...
0
votes
0answers
44 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 ...
1
vote
1answer
92 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 { :...
1
vote
1answer
73 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 ...
0
votes
1answer
62 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{ ...
4
votes
0answers
75 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 $\...
5
votes
4answers
249 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 ...
1
vote
0answers
63 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 ...
1
vote
1answer
41 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 ...
1
vote
1answer
103 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
109 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, ...
5
votes
1answer
469 views

What does "adaptively secure" mean?

In a paper it says "In the generic group model, the PRF is adaptively secure for inputs of $\mathbb{Z}_q^n$". Maybe a stupid question, but what does "adaptively secure" mean exactly?
2
votes
0answers
30 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 ...
1
vote
1answer
297 views

What does it mean that a protocol realizes "strong mutual authentication"?

What does it mean that a protocol realizes "strong mutual authentication"? And what does it mean that a protocol realizes "weak mutual authentication"? Can you define them formally ...
2
votes
1answer
91 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, ...
0
votes
0answers
46 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 +,-,< ......
2
votes
2answers
95 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 ...
4
votes
0answers
427 views

Hash Function Properties

What I am trying to understand is shown in all three properties of a secure hash function, I will focus on Preimage attack resistance. Preimage resistance: given a hash h, it's difficult to find m s.t....
10
votes
2answers
4k views

Definitions of secrecy

I found terms like "forward secrecy", "future secrecy", "backwards secrecy" and "perfect forward secrecy" and I would like to know their definitions and to understand the differences among them. I ...
2
votes
1answer
60 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 ...
1
vote
0answers
44 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 $...
1
vote
0answers
30 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(...
1
vote
0answers
30 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 ...
0
votes
1answer
53 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, ...
0
votes
0answers
50 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 ...
1
vote
0answers
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 ...
1
vote
0answers
38 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
0answers
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 (...
0
votes
1answer
41 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 ...
3
votes
2answers
112 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
132 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
51 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
131 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 ...
2
votes
1answer
80 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
1answer
6k 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. ...
6
votes
2answers
1k views

What is the difference between information-theoretic and perfect types of security?

I'm having a hard time pinning down an exact definition of the difference between information-theoretic and perfect types of security. A rigorous definition seems elusive... A. Wikipedia puts the ...
2
votes
0answers
190 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 ...
2
votes
1answer
79 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 $...
0
votes
0answers
58 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 $\...
1
vote
1answer
1k views

Difference between eavesdropping and traffic analysis

I was wondering what is the conceptual difference between these two passive attacks on a network. I was reading about them on Wikipedia and they seem quite similar to me. Is there a difference?
0
votes
1answer
488 views

Difference between a secure PRG and semantically secure encryption

I am taking cryptography course in Coursera from Stanford University. I have following question I have a question why append 0 in G(k) i.e., G'(k) = G(k) || 0 is considered as not secure PRG as 0 in ...
3
votes
2answers
1k views

Signature based on public key cryptography and forgery

In the definition of existential unforgeability, there is no detail about the following questions. In general, can we suppose that a signer is also a possible adversary? When generating a signature, ...
1
vote
2answers
201 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
59 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
46 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 ...
2
votes
1answer
75 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
150 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
84 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
2 3 4 5