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
3 votes
1 answer
119 views

What does the bounded storage model mean?

In the bounded storage model, it assumes the storage of the adversary is bounded or limited, and thus it is possible that we can achieve a kind of cryptography without relying on hardness assumption. ...
0 votes
1 answer
214 views

Why are stream ciphers computationally secure?

In case multiple stream ciphers exist, I'm refering to this specific instance in which you generate a key that is just as long as the msg, M, as a function of a nonce and a smaller key K. My textbook ...
0 votes
0 answers
35 views

Strange definition of indistinguishability game

I refer to the paper https://eprint.iacr.org/2018/077 and in particular Definition 6 on page 6. I recite the definition below. Definition. Let $\{\mathcal{D}_\theta^0\}_\theta$, $\{\mathcal{D}_\theta^...
0 votes
1 answer
33 views

Why we need to consider a probability ensemble and not just a probability distribution in the definition of Security under Simulation?

I'm currently reading this classic paper "How To Simulate It" and on most of the definitions it is using the term probability ensemble to represent the message space. From my understanding a ...
1 vote
2 answers
118 views

Why is this PRF not secure? [closed]

So, I'm taking Cryptography I by Dan Boneh on Coursera and I was reviewing the definition of security for a PRF while solving exercises, and I stumbled upon this question from a homework Dan Boneh ...
0 votes
0 answers
58 views

Clarification for CCA security (or - why is the following not a Rabin CCA attack?)

In three different, highly reputable sources (e.g. "Introduction to Modern Cryptography" by Katz and Lindell, 2007), the definition of CCA attack doesn't allow the adversary to decrypt the ...
0 votes
2 answers
41 views

How to understand "Test() query can only be issued to a fresh session" in game-based security proof?

In game-based security proof for key-exchange protocols, there is a Test query. The Test(U) query typically is only available to the adversary if the attacked instance U is fresh. (U represents either ...
0 votes
0 answers
23 views

What happens if the number of message queries are restricted?

In this thread, we only consider symmetric key encryption. I am not familiar with this field, so I am somewhat of an idiot myself. The usual symmetric key encryption allows unbounded queries of ...
2 votes
1 answer
33 views

Limit definition of negligible function

I am reading Dan Boneh's book and I am stuck on Theorem 2.11, whose proof is left as an exercise. The question is: prove that if $\lim_{n \rightarrow \infty} f(n)n^c = 0$ for all $c > 0$, then $f$ ...
4 votes
0 answers
59 views

How to get started with Simulation and UC proofs?

I've been in my PhD program for a few months, and every time I try to understand the simulation and UC proof-paradigms I get so confused. I feel like what I really need is an easy set of (guided) ...
2 votes
2 answers
182 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 ...
0 votes
0 answers
17 views

Correct definition of circular security - multiple encryptions of $sk$ allowed?

As I understand the definition, it's an extension of CPA security where the attacker can ask for an encryption of the secret key, using the public key. My question is - does the definition allow the ...
0 votes
0 answers
37 views

Weak and Strong Unforgeability for Known Message Attacks

For signatures, there is the security goal of existential unforgeability. As seen here and noted here (german source) the security goal can be split into weak and strong unforgeability for chosen ...
4 votes
0 answers
105 views

About the complexity of a path finding attack for a path encrypted with a block cipher (like AES). How many AES calculations count as secure?

Out of $N = s^3$ total points we pick a starting point $p$ and an end point $q$ with $$p=(p_1, p_2)$$ $$q=(q_1,q_2)$$ $$p_1,q_1 \in [0,s)$$ $$p_2,q_2 \in [0,s^2)$$ We want to find a path in between ...
1 vote
1 answer
68 views

Differential Privacy with Outliers

To use the Laplace mechanism, we have to get the global sensitivity of a query function. What do we do in the case where there is one huge outlier(or multiple outliers) in the dataset such that the ...
1 vote
1 answer
110 views

If RSA uses $e$ with $\gcd(e,\phi(N))\ne1$ but $e$ is hard to factorize has an adversary still an advantage in finding $d$ for $m^{ed}\equiv m\mod N$?

Usually RSA uses an encryption exponent $e$ with $\gcd(e,\phi(N))=1$. This question shows why that need to be the case: For $\ne1$ there might exist no decryption exponent $d$ because other $m'\ne m$ ...
0 votes
0 answers
49 views

How is ECB secure? [duplicate]

Setting aside legitimate concerns such as lack of CPA security (not to speak of malleability issues) and thus near-universal insuitability of AES-ECB for general purposes, I thought I recalled reading ...
0 votes
1 answer
75 views

Security definition for IND-CPA of public key encryption

In the security game between the challenger and the adversary for the security definition of public key encryption, the challenger creates and gives the public key pk to the adversary. The adversary ...
0 votes
0 answers
29 views

Secuirty definion of a ad hoc multi-input functional encryption scheme

I have to write an essay on the paper ad hoc multi-input functional encryption, and can't understand the security definition. In a nutshell it is a primitive that allow sources to supply encrypted ...
1 vote
2 answers
88 views

Relative bits of security of slower functions

Leaving memory-hardness assumptions aside, some slow hash functions are iterated salted hash-chain versions of regular cryptographic hashes. This is usually defined by a ...
0 votes
1 answer
63 views

Secure communication over insecure channel is based on the assumption of secure channel?

Consider a scenario:data owners $C$ sends a $l$ bits value $x$ to parties $P_0$ and $P_1$ via additively secret sharing scheme, for example, $C$ randomly selects $r \in_R \{0, 1\}^l$, and sends $r$ to ...
0 votes
1 answer
72 views

Question on notation of random variables in probability ensembles

Let's consider this definition of computational indistinguishability. Computational indistinguishability. A probability ensemble $X=\{X(a, n)\}_{a \in\{0,1\}^{*} ; n \in \mathbb{N}}$ is an infinite ...
0 votes
0 answers
27 views

Difference of unconditional and perfect security in terms of IND-Game

Both unconditional and perfect security were very clear to me, until I bumped upon different sources that confused me. For example : 1 2 3. Also in 3 the DH76 paper is referenced and it doesn't ...
0 votes
2 answers
153 views

How can we measure the security levels of post-quantum cryptographic algorithms? Is there a standard way of this measurement?

How do we measure the security levels of Post Quantum Cryptographic algorithms such as: NTRU Prime, Saber, Kyber,...that are submited to NIST PQC Standardization Process(Competition) in general? I ...
3 votes
2 answers
108 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 ...
0 votes
1 answer
28 views

EC cardinality $P^3+c$ with 3 gen $G$, $F = P\cdot G,H=P^2\cdot G$ and 2 random members $M_1+iG+jF+kH=M_2$. How long would it take to find $i,j,k$?

Given a EC with cardinality $C=P^3+c$ with $P$ a prime $P \approx \sqrt[3]{C}$ and $c>0$. Out of a given generator $G$ we generate two additional generator $F,H$ with $$F = P \cdot G$$ $$H = P^2 \...
1 vote
1 answer
85 views

Which impact on security (factorization) has a common prime factor among prime factors? $N=P\cdot Q$ with $P=2\cdot F\cdot p+1$, $Q=2\cdot F\cdot q+1$

Which impact on security (factorization) has a common prime factor among the prime factors $P$,$Q$ of a number $N$ $$N=P\cdot Q$$ $$P=2\cdot F\cdot p+1$$ $$Q=2\cdot F\cdot q+1$$ with $F,q,p$ different ...
1 vote
0 answers
89 views

Question about sequence length/count/security of $x\mapsto x^\alpha \mod (N=Q\cdot R)$, with $Q=2q_1q_2+1$ and $R=2r_1r_2+1$ and $\alpha = 2q_2r_2$

Given a number $N$ with $$N=Q\cdot R$$ $$Q=2\cdot q_1 \cdot q_2+1$$ $$R=2\cdot r_1\cdot r_2+1$$ with different primes $P,Q,q_1,q_2,r_1,r_2$. If we now choose an exponent $\alpha$ containing prime ...
2 votes
1 answer
145 views

Invalid point attack on quadratic twist of Elliptic Curve when -1 is a quadratic residue

I'm replicating an invalid point attack on ECC using Short Weierstrass curves. For this I have written a "dumb" implementation that does not validate points are on the curve before going ...
8 votes
1 answer
2k views

Understanding Twist Security with respect to short Weierstrass curves

I'm trying to understand the "Invalid-curve attacks against ladders" section of SafeCurves Twist Security page and I have difficulties to apply it to short Weierstrass curves. That section claims ...
1 vote
1 answer
45 views

How secure is a projection to a subspace with much lower member size for $x\mapsto x^a$ mod $N = PQ$, $P=2p+1$, $Q=2qr+1$, to target space $r=2abc+1$?

A cyclic sequence can be produced with $$s_{i+1} = s_i^a \mod N$$ with $N = P \cdot Q$ and $P = 2\cdot p+1$ and $Q = 2\cdot q\cdot r+1$ and $r = 2\cdot u \cdot v \cdot w +1$ with $P,Q,p,q,r,u,v,w$ ...
2 votes
1 answer
74 views

What's the meaning of verifier is "ppt" ? and why we need verifier is ppt in Interactive Proof?

I have been studying Zero Knowledge Proof. I found the Definition of Interactive Proof says that Verifier is ppt. And I only found in PP (Complexity) Wikipedia says that ppt: Turing machines that are ...
0 votes
0 answers
47 views

Collision resistance analysis

I am learning about collision resistance security notion of hash functions. However, I got confused when collision resistance experiment started using "keyed" hash functions in the ...
1 vote
2 answers
100 views

What is the relationship between "Challenger" and "Oracle" in a security proof?

In game-based security proof, I found that games are defiend to be played between a PPT adversary and a challenger. The adversary is able to issue queries to different oracles and receives ...
0 votes
1 answer
91 views

What does hard instance mean in cryptography?

I'm learning cryptography recently. I read that for game-based formal security analysis, it is important to embed the hard instance during reduction. Does "hard instance" mean hard-to-solve ...
1 vote
1 answer
78 views

What is the definition of semantic secure advantage?

I'm doing sequence-of-game formal security analysis for key exchange protocol. It confuses me a lot how to calculate the adversary's semantic secure (SS) advantage. In Shoup's tutorial "sequences ...
4 votes
1 answer
444 views

Indistinguishability of symmetric encryption under CCA

I am learning about symmetric encryption and its security properties. One of the security notion is security against chosen cipher-text attacks (CCA), particularly IND-CCA notion. Under this notion, ...
2 votes
1 answer
81 views

Question about malicious security in protocol using OT

I was studying a protocol that used an OT and suddenly and suddenly I realize that I fail to imagine how a protocol using an OT could be malicious secure. Suppose we have a protocol P that use an OT ...
2 votes
0 answers
121 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
1 answer
98 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{ ...
2 votes
2 answers
353 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 ...
7 votes
2 answers
2k 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 ...
0 votes
0 answers
28 views

Methods of security proofs used in bibliography, apart from games and simulations?

The question in mainly stated on the title. I am currently studying various cryptographic schemes and most of them use either game based or simulation based methodologies for their proof. I was ...
1 vote
0 answers
70 views

IND-CCA implies OW-CCA

(Disclaimer: I am a noob in cryptography so please keep that mind in your answers). In symmetric private key cryptography, an adversary $\mathcal A$ provided with encryption and decryption oracles $\...
5 votes
4 answers
332 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 ...
3 votes
2 answers
459 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 ...
4 votes
1 answer
151 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 "...
26 votes
1 answer
7k views

What do the signature security abbreviations like EUF-CMA mean?

From time to time, one stumbles across formal security definitions. This includes security definitions for signature schemes. The most common ones are the *UF-* ...
4 votes
2 answers
180 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 ...
2 votes
0 answers
99 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, ...

1
2 3 4 5 6