Skip to main content

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
5 votes
1 answer
200 views

Making signature immune to Colliding Signatures and other threats

Some signature schemes1 have strong Existential UnForgeability under Chosen Message Attack (sEUF-CMA), but still allow Colliding Signatures or/and fail to provide Conservative or/and Destructive ...
fgrieu's user avatar
  • 142k
0 votes
2 answers
66 views

Using random samples from indistinguishable ensembles to create new empirical ensembles

Suppose I have two computationally indistinguishable ensembles of random variables $\{X_i\}_i$ and $\{Y_i\}_i$ ($i$ is the usual security parameter). The random variables are both uniformly ...
JasperT's user avatar
1 vote
1 answer
50 views

Sankey Diagram for Wireless sensor network, accurate?

I've designed a Sankey diagram to depict security in Wireless Body Area Networks for my thesis. It's the first time I see such a diagram used for security. I need your help. Could you check its ...
Moh Kashani's user avatar
1 vote
0 answers
67 views

How secure is this hash combination function for merkle trees?

I am exploring the class of functions that I have seen called "hash combination functions". These functions are arguably distinct from hash functions, generally providing second-preimage ...
Justin Martin's user avatar
3 votes
1 answer
193 views

Confusion in the security level offered by KYBER

I was looking at security level offered by KYBER. I have attached the table for the reference. I am little bit confused regarding the security level offered by KYBER. By definition, Level 1 in the ...
V S.'s user avatar
  • 95
0 votes
1 answer
71 views

A question about Definition 3.8 in book IMC by Katz and Lindell

In the book IMC by Katz and Lindell, definition 3.8 says that "if for all PPT adversaries A, there is a negligible function negl such that for all n ......". I am confused about why it holds ...
Jeffrey's user avatar
  • 137
2 votes
1 answer
335 views

Core-SVP Hardness of Kyber

This question is with reference to the python file model_BKZ.py provided in the GitHub repository https://github.com/pq-crystals/security-estimates/blob/master/...
V S.'s user avatar
  • 95
1 vote
1 answer
117 views

Is concatenation of secure encryptions secure?

If I have $n$ secure assymetric encryption schemes, is their concatenation $Enc_{k_1,...,k_n}(m)=Enc_{k_1}(m)||...||Enc_{k_n}(m)$ secure? My intuition is that the concatenation is secure, but I can't ...
Amit Keinan's user avatar
3 votes
1 answer
233 views

Is Goldreich's proof with polynomial number of hybrid arguments wrong?

Oded Goldreich in his book [Foundations of Cryptography, 2004, Section 3.2.3] proves a theorem by polynomial number of hybrids. In rather recent years, Marc Fischlin and Arno Mittelbach published a ...
user1035648's user avatar
2 votes
1 answer
159 views

How many encrypted messages can we know, so that scheme is secure?

Let $G$ be a secure PRG and let $s$ be a private key. We can define $\mathrm{Enc}(s,m) = G(s)\oplus m$. As long as we know only one encrypted message this scheme is secure, since $G(s)\oplus m \sim r\...
giochi's user avatar
  • 131
0 votes
0 answers
71 views

Is this particular encryption algorithm secure?

Suppose that $(\mathrm{Gen},\mathrm{Enc},\mathrm{Dec})$ is a secure encryption scheme. Encryption scheme is secure if for any two sequences $\{a_{n}\}_{n\in\mathbb{N}},\{b_{n}\}_{n\in\mathbb{N}}$ of ...
giochi's user avatar
  • 131
0 votes
0 answers
32 views

Safe use of bilinear pairing, using one way function in the exponent

Given a generator $g$ of a cyclic group, I am trying to look for a case where I use pairing over an element that has an exponent which is a one-way function, e.g., $g^{x^2\mod n}$ (here $x$ in the ...
Doron's user avatar
  • 99
1 vote
1 answer
75 views

What is the standard security and leaky security, and the relation between the standard/leaky security and the leakage function?

Recently, I read some security proofs about the secure multi-party computation (MPC) protocol, which includes statements about information leakage, such as the security proof below from the paper CWL+...
Yang's user avatar
  • 204
5 votes
1 answer
479 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 ...
Chris's user avatar
  • 236
2 votes
1 answer
128 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 (...
user109993's user avatar
2 votes
1 answer
186 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....
honzaik's user avatar
  • 452
0 votes
0 answers
87 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 ...
user1035648's user avatar
4 votes
0 answers
78 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 ...
NB_1907's user avatar
  • 640
2 votes
1 answer
110 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 $...
Chris's user avatar
  • 236
0 votes
1 answer
396 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 ...
glesage's user avatar
  • 133
3 votes
0 answers
59 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 ...
Prashant Agrawal's user avatar
3 votes
1 answer
123 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 ...
user1035648's user avatar
11 votes
1 answer
569 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$ ...
Lee Seungwoo's user avatar
2 votes
1 answer
253 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,...
Giusy's user avatar
  • 33
3 votes
0 answers
121 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: ...
cryptolearner's user avatar
1 vote
0 answers
58 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 ...
phantomcraft's user avatar
2 votes
1 answer
102 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 ...
Caio Nogueira's user avatar
2 votes
1 answer
179 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 ...
geust213's user avatar
1 vote
1 answer
653 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&...
user avatar
1 vote
2 answers
186 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 ...
mathInferno's user avatar
3 votes
3 answers
153 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 ...
tur11ng's user avatar
  • 962
1 vote
2 answers
438 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 ...
Jeff24's user avatar
  • 13
1 vote
0 answers
102 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 ...
Anon's user avatar
  • 403
2 votes
1 answer
175 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$ ...
sadtroll's user avatar
4 votes
0 answers
129 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) ...
FearfulJoe's user avatar
0 votes
0 answers
122 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 ...
Titanlord's user avatar
  • 2,307
6 votes
0 answers
136 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 ...
J. Doe's user avatar
  • 453
1 vote
1 answer
356 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$ ...
J. Doe's user avatar
  • 453
2 votes
1 answer
973 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 ...
Noel's user avatar
  • 133
0 votes
0 answers
38 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 ...
mike's user avatar
  • 41
1 vote
1 answer
127 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 ...
tur11ng's user avatar
  • 962
0 votes
1 answer
94 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 ...
Yang's user avatar
  • 204
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 ...
Kostas Kryptos's user avatar
0 votes
1 answer
79 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 \...
J. Doe's user avatar
  • 453
1 vote
0 answers
112 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 ...
J. Doe's user avatar
  • 453
1 vote
1 answer
130 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 ...
J. Doe's user avatar
  • 453
3 votes
1 answer
479 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 ...
performancematters's user avatar
1 vote
1 answer
55 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$ ...
J. Doe's user avatar
  • 453
0 votes
2 answers
57 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 ...
Chandler's user avatar
2 votes
1 answer
357 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 ...
Sheldon's user avatar
  • 215

1
2 3 4 5 6