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
4
votes
1
answer
491
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?
- 47.5k
3
votes
1
answer
299
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. ...
CommunityBot
- 1
5
votes
1
answer
466
views
What is a non-OWF?
We know that A function $f:\Bbb Z_2^n \longrightarrow\Bbb Z_2^m$ is a (strong) one-way function (OWF), if:
$f$ can be computed by a PT algorithm. Equivalently, there exists a PPT algorithm that on ...
- 206
2
votes
1
answer
64
views
In NIZK, what is the difference between "transparent“ and “without trusted setup”?
When I study a zk-SNARK scheme, the scheme claims to be transparent. Does this mean that this scheme does not require a trusted setup? Furthermore, if a NIZK scheme includes a Common Reference String (...
- 12.5k
2
votes
1
answer
117
views
IND-CPA/CCA security of AEAD schemes
I was reading the Hybrid Public Key Encryption (HPKE) RFC and I came across this sentence in section 9.4 "All AEADs MUST be IND-CCA2-secure, as is currently true for all AEADs listed in Section 7....
- 2,848
0
votes
0
answers
68
views
Why is decryption algorithm usyally deterministic?
For security against Chosen Plaintext Attack (CPA), we need randomized algorithms for encryption. But in some schemes (maybe almost all of them) take decryption algorithm deterministic. This procedure ...
- 363
3
votes
1
answer
79
views
Why do we need "selective security" for ABE?
The general question is: Why are ABE schemes usually/sometimes proven in the selective-set of attributes model of security? Or even co-selective (both attributes and policy function)? Is it just ...
- 363
0
votes
0
answers
34
views
Comparison of distinguishing attack against blockcipher and permutation
In a previous question, we explored various security definitions of encryption schemes, such as IND-CPA, IND-CCA{1,2,3,etc.}
These indistinguishability games can roughly translate to blockciphers, as ...
- 9,001
3
votes
0
answers
57
views
On the Adaptive Security of MPC Protocols
In adversarial context of MPC, the corruption behavior
refers to the assumptions about the corrupted parties’ deviation level from the protocol
specification. Three main types of corruption behaviors ...
- 91.7k
2
votes
1
answer
93
views
Defining the random variables $K,M,C$ and Perfect Secrecy
In many books on Cryptography, we refer to probability distributions over the key space $\mathcal{K}$, over the plaintext space $\mathcal{M}$ and over the ciphertext space $\mathcal{C}$.
Then, we let $...
- 206
0
votes
1
answer
210
views
Use Shamir's Secret Sharing Scheme to split a key between a client, a server and multiple 3rd parties
I'm trying to design an encryption system for a new mobile app and am thinking of using Shamir's Secret Sharing Scheme in a way which I have not seen before. Does this seem possible or does it violate ...
- 138k
3
votes
0
answers
47
views
Variant of CCA security for Paillier with blinded decryption oracle
Consider a variant of the Paillier encryption scheme where the message space is restricted to $\mathbb{Z}_q$ such that the RSA modulus $N$ of the Paillier cryptosystem satisfies $N > q + q^2$. I am ...
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 ...
- 2,565
1
vote
0
answers
87
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 ...
- 2,565
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 ...
- 138k
2
votes
2
answers
108
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 ...
3
votes
0
answers
99
views
Semantic Security equivalent to Real/Random Semantic Security
I'm reading Boneh and Shoup's book "A Graduate Course in Applied Cryptography." Im doing one of the questions at the end of the stream ciphers chapter. I'm not sure how to do this problem:
...
- 2,565
11
votes
1
answer
456
views
What does 'a reduction is tight' mean rigorously?
As far as I know, when someone says 'a reduction is tight', it means that given that there is an adversary $A$ with advantage $\epsilon$ and running time $t$ and another adversary $B$ utilizing $A$ ...
- 5,133
2
votes
1
answer
84
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 ...
- 11.6k
2
votes
1
answer
175
views
Let $G$ be a PRG. Establish whether the following PRG candidates $G^{'},G^{''}$ are secure or not
Let $G:\{0,1\}^n \leftarrow \{0,1\}^{2n}$ be a PRG. Establish whether the following PRG candidates $$G^{'},G^{''}:\{0,1\}^n \leftarrow \{0,1\}^{3n}$$ are secure or not:
$G^{'}(s)=(x⊕y,u,v)$ where $(x,...
- 5,133
2
votes
1
answer
100
views
Alternative definition of security for MAC
In the usual definition of security for message authentication codes, we let an adversary $A$ have access to an oracle for $Mac_k(.)$. However, if we consider that there exists a more powerful type of ...
CommunityBot
- 1
1
vote
0
answers
48
views
Is the security of output of Skein when using arbitrary output size similar to that of SHAKE?
Let's suppose I have a 1MB high-resolution photo and I want to hash and create a 1536-bits key.
I know that I could just use SHAKE-256 as its a pre-enginered way for doing that.
There is also Skein ...
- 877
2
votes
1
answer
104
views
Knowledge extractors in proofs of knowledge
I'm somewhat new to cryptography and I've been looking at knowledge extractors in proofs of knowledge and I am a little confused by the use of somewhat different definitions.
In textbooks or early ...
- 1,095
2
votes
2
answers
773
views
An example of of an information theoretically secure protocol that is not cryptographically secure
Does there exist a protocol $\pi$ for some functionality $F$ which is information theoretically secure protocol that is not cryptographically secure for some threshold number of corrupt parties? ...
- 13
1
vote
2
answers
150
views
Clarification of some probability concepts used in crypto
So I am a math major who is trying to learn some crypto. However I have some difficulties with some of the probability definitions that are assumed in the cryptography book that I am using at the ...
- 99
1
vote
1
answer
329
views
How to test/calculate "how secure" an encryption algorithm is?
I'm new to the topic guys, but as there are literally too many encryption methods out there, too that I could even come up with many ideas of them, how to we actually test/calculate "how secure&...
- 5,786
0
votes
1
answer
326
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 ...
CommunityBot
- 1
1
vote
2
answers
272
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 ...
- 176
0
votes
2
answers
56
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 ...
- 4,597
2
votes
1
answer
94
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$ ...
- 21.2k
4
votes
0
answers
100
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) ...
- 41
0
votes
0
answers
99
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 ...
- 2,120
6
votes
0
answers
125
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 ...
- 573
1
vote
1
answer
311
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$ ...
- 573
0
votes
1
answer
722
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 ...
- 1,082
0
votes
0
answers
36
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 ...
- 91.7k
1
vote
2
answers
93
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 ...
- 878
0
votes
1
answer
91
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 ...
- 413
0
votes
1
answer
105
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 ...
- 413
1
vote
2
answers
379
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 ...
- 46
3
votes
2
answers
113
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 ...
- 1,582
0
votes
1
answer
50
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 \...
- 145k
1
vote
1
answer
118
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
107
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 ...
- 573
2
votes
1
answer
386
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
3k
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 ...
- 47.5k
1
vote
1
answer
52
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$ ...
- 21.9k
2
votes
1
answer
218
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 ...
- 2,169
0
votes
0
answers
70
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 ...
- 63
1
vote
2
answers
306
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 ...
- 12.5k