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
210 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
156 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\...
matheg'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 ...
matheg's user avatar
  • 131
0 votes
0 answers
30 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
57 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
  • 194
5 votes
1 answer
471 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
  • 206
2 votes
1 answer
86 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
148 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
  • 392
0 votes
0 answers
78 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
0 votes
0 answers
37 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 ...
DannyNiu's user avatar
  • 9,080
4 votes
0 answers
67 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
  • 610
2 votes
1 answer
100 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
  • 206
0 votes
1 answer
284 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
53 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
100 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
487 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
204 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
106 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
57 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
132 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
454 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
168 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
132 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
333 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
95 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
136 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
108 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
114 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,214
6 votes
0 answers
130 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
  • 573
1 vote
1 answer
330 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
  • 573
1 vote
1 answer
837 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
  • 123
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 ...
mike's user avatar
  • 41
1 vote
1 answer
117 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
  • 194
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
61 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
  • 573
1 vote
0 answers
109 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
  • 573
1 vote
1 answer
126 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
  • 573
2 votes
1 answer
410 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
53 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
  • 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 ...
Chandler's user avatar
2 votes
1 answer
271 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
0 votes
0 answers
75 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 ...
driewguy's user avatar
2 votes
2 answers
349 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 ...
Chandler's user avatar
0 votes
1 answer
140 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 ...
Chandler's user avatar
1 vote
1 answer
239 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 ...
Chandler's user avatar
4 votes
1 answer
703 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, ...
driewguy's user avatar
2 votes
1 answer
119 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 ...
miky's user avatar
  • 21
1 vote
2 answers
427 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 ...
esra's user avatar
  • 869

1
2 3 4 5 6