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
0 votes
0 answers
14 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 ...
user avatar
  • 191
0 votes
0 answers
29 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 ...
user avatar
  • 1,492
4 votes
0 answers
104 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 ...
user avatar
  • 475
0 votes
0 answers
46 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 ...
user avatar
1 vote
1 answer
95 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$ ...
user avatar
  • 475
0 votes
1 answer
52 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 ...
user avatar
  • 113
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 ...
user avatar
  • 31
0 votes
1 answer
70 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 ...
user avatar
  • 512
0 votes
1 answer
58 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 ...
user avatar
  • 40
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 ...
user avatar
0 votes
0 answers
26 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 ...
user avatar
  • 512
0 votes
1 answer
27 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 \...
user avatar
  • 475
1 vote
0 answers
87 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 ...
user avatar
  • 475
1 vote
1 answer
84 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 ...
user avatar
  • 475
2 votes
1 answer
124 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 ...
user avatar
1 vote
1 answer
44 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$ ...
user avatar
  • 475
0 votes
1 answer
25 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 ...
user avatar
2 votes
1 answer
58 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 ...
user avatar
  • 205
0 votes
0 answers
46 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 ...
user avatar
1 vote
2 answers
88 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 ...
user avatar
0 votes
1 answer
77 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 ...
user avatar
1 vote
1 answer
64 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 ...
user avatar
4 votes
1 answer
435 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, ...
user avatar
2 votes
1 answer
78 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 ...
user avatar
  • 21
0 votes
2 answers
137 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 ...
user avatar
  • 859
1 vote
1 answer
58 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 ...
user avatar
0 votes
1 answer
167 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 ...
user avatar
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 ...
user avatar
  • 512
1 vote
0 answers
58 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 $\...
user avatar
4 votes
1 answer
112 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 "...
user avatar
3 votes
0 answers
91 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. ...
user avatar
  • 707
0 votes
0 answers
34 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 ...
user avatar
  • 1,492
1 vote
1 answer
74 views

Adaptive Security Advantage

Adaptive model: the attacker can adaptively query the challenger for private keys. The challenge message need not be revealed at the start of the security game Selective model: the attacker has to ...
user avatar
1 vote
3 answers
477 views

Post quantum security experiment

In cryptography there are 4 basic attack classifications: Ciphertext-Only Attack Known-Plaintext Attack Chosen-Plaintext Attack Chosen-Ciphertext Attack In Katz & Lindell's textbook (2nd edition)...
user avatar
  • 1,492
2 votes
0 answers
94 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, ...
user avatar
1 vote
1 answer
184 views

KPA-Security definition

In cryptography there are 4 basic attack classifications: Ciphertext-Only Attack Known-Plaintext Attack Chosen-Plaintext Attack Chosen-Ciphertext Attack In Katz & Lindell's textbook (2nd edition)...
user avatar
  • 1,492
1 vote
0 answers
42 views

Exact security requirements for extendable output functions (XOF)?

In the FIPS202 document "SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions" an extendable-output functions is defined as: An extendable-output function (XOF) is a ...
user avatar
0 votes
1 answer
78 views

Reference for a formal definition of universal forgery and EUF-CMA

In many papers, I see EUF-CMA and SUF-CMA referenced as a canonical term used, but I did not find a reference paper/book that ...
user avatar
0 votes
0 answers
29 views

Besides block-cipher which other methods can only be computed step-by-step even with known secret (but fast per step) and can be inverted?

Depending at the cryptographic function used applying it $i$-times to a given input can be computed in different complexity classes (based at their input size). $$f^i(m_0) = c_i$$ For example for most ...
user avatar
  • 475
0 votes
0 answers
62 views

How can a concatenation of $N$ block-cipher with known keys be more secure?

General problem / Intro: encrypting the (computable) relation in between two random numbers which are members of a as small as possible set while anything except the order of execution is known to the ...
user avatar
  • 475
1 vote
1 answer
113 views

Superscript vs subscript notation in cryptographic formulation

I'm currently reading this paper [PDF]. On page 4, I bumped into these notations : \begin{equation} \text { Experiment } \operatorname{Exp}_{\mathcal{F} \mathcal{E}, A}^{\text {ind-mode }}(k) \text { :...
user avatar
  • 512
1 vote
1 answer
90 views

Can a block-cipher considered secure if a bit-change of the input leads to a 50% chance change for every single output bit? -> round number?

Block-cipher use self-inverse ($f(f(x)) = x $) operations which then will be applied to the plaintext and most likely contain some constants which can be based at a key. To get security such ...
user avatar
  • 475
4 votes
0 answers
213 views

2 different definitions of Special Soundness

There are 2 different definitions of special soundness in the literature: (1) can be found in Damgard: We say that a Sigma-protocol $\Pi$ satisfies special soundness, if there exists a PPT extractor $\...
user avatar
  • 173
1 vote
1 answer
95 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{ ...
user avatar
1 vote
1 answer
43 views

Is it allowable to put a restriction on the length of the plaintext used in the known-plaintext attack?

The definition of the known-plaintext attack: I have a plaintext and I can encrypt it to have its ciphertext, then I use this pair to break the cipher. The question: The only thing I further assume is ...
user avatar
  • 435
1 vote
1 answer
278 views

MPC Definitions: UC-Security vs. Real-Ideal Simulation?

I consider the "standard" definition of maliciously-secure 2PC to be the simulation-based, ideal–real-world indistinguishability definition of e.g. Lindell's How to Simulate It [Lin17, ...
user avatar
  • 135
2 votes
0 answers
42 views

Encrypting random coins used for the encryption itself

Circular security notions for PKE schemes capture the security of (PKE) schemes when encrypting the secret decryption key. Is there an analogous notion but for encrypting the randomness used for the ...
user avatar
0 votes
0 answers
75 views

Shamir secret sharing in automated verification tools

Can Shamir secret sharing scheme (SSS) be verified using automated verification tools such as AVISPA? I read in the HLPSL manual that we cannot use arithmetic or relative operations such +,-,< ......
user avatar
  • 105
2 votes
2 answers
293 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 ...
user avatar
2 votes
0 answers
115 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 ...
user avatar

1
2 3 4 5 6