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
5
votes
1
answer
467
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
67
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 (...
- 63
2
votes
1
answer
121
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....
- 392
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
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 ...
- 538
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
216
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 ...
- 133
3
votes
0
answers
50
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
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
11
votes
1
answer
464
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$ ...
- 363
2
votes
1
answer
179
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,...
- 33
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:
...
1
vote
0
answers
49
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
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 ...
2
votes
1
answer
109
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 ...
- 21
1
vote
1
answer
346
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&...
user104553
1
vote
2
answers
154
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 ...
- 13
2
votes
1
answer
87
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 ...
- 878
1
vote
2
answers
274
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 ...
- 13
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 ...
- 383
2
votes
1
answer
95
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$ ...
- 45
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
103
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
313
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
743
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 ...
- 113
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 ...
- 41
0
votes
1
answer
107
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 ...
- 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 ...
- 140
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 ...
- 232
0
votes
1
answer
51
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 \...
- 573
1
vote
0
answers
108
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
1
vote
1
answer
119
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 ...
- 573
2
votes
1
answer
388
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 ...
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$ ...
- 573
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 ...
- 29
2
votes
1
answer
229
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 ...
- 215
0
votes
0
answers
71
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
309
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 ...
- 29
0
votes
1
answer
132
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 ...
- 29
1
vote
1
answer
221
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 ...
- 29
4
votes
1
answer
663
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, ...
- 63
2
votes
1
answer
114
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 ...
- 21
1
vote
2
answers
389
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 ...
- 869
2
votes
2
answers
109
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 ...
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 ...
4
votes
1
answer
286
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 "...
3
votes
1
answer
304
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. ...
- 787
0
votes
0
answers
48
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 ...
- 2,120