Skip to main content

Questions tagged [provable-security]

A primitive or protocol with provable security is accompanied by a mathematical proof that shows how to reduce the security claims about the protocol to a set of assumptions.

147 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
11 votes
0 answers
690 views

What level of security is provided when a Feistel Cipher is used as a round function of another Feistel Cipher?

Recently, I was reading: Are there any specific requirements for the function F in a Feistel cipher?, and the answer posted mentions a Feistel Cipher named Turtle, which uses a four-round Feistel ...
user avatar
8 votes
0 answers
200 views

Replacing signer with simulator

Assume we can prove the security of the digital signature scheme against key-only (no message) attacks. Now we want to prove security against adaptive chosen message attack. We use the random oracle ...
Student20's user avatar
  • 431
7 votes
0 answers
375 views

Security Proof of Short Schnorr Signature

I know that this is a very specific question, but I still hope that someone can help me. I'm trying to understand the security of the short schnorr signature a little bit better. The security ...
einsteinwein's user avatar
7 votes
0 answers
112 views

Is there a standard definition of non-malleability for the encryption schemes?

I find some different definitions of non-malleability for the encryption schemes. They may be equivalent, but I am not sure which one is better or if there is a standard definition. I give two ...
Blanco's user avatar
  • 1,622
7 votes
0 answers
356 views

Security proof in (Ciphertext-Policy) Attribute-Based Encryption

I am having hard time understanding the security proof in Attribute-Based Encryption, especially in Ciphertext-Policy Attribute-Based Encryption. To do reduction in CP-ABE scheme, how do I check that ...
Nyamaa's user avatar
  • 71
5 votes
0 answers
467 views

ring-LWE: Minkowski Embedding , the Co-Different Ideal, etc

While (trying) to go over the reductions from approx. SVP on ideal lattices to search ring-LWE, [1] and [2], for $K = \mathbb{Q}(\zeta)$ where $\zeta$ is an abstract root of a cyclotomic polynomial, ...
Rohit Khera's user avatar
5 votes
0 answers
193 views

Efficient proof of knowledge using Carter-Wegman hash

A verifier wants to ensure, with only little exchange of data with other systems, that a large block of data $M$ that the verifier holds is also available to some other system(s). It is not an ...
fgrieu's user avatar
  • 142k
5 votes
0 answers
79 views

What is the restriction on $k$, for the $k$th composite residuosity problem to be hard?

The paper “Residuosity Problem and Its Applications to Cryptography” considers the exponent to be an odd integer. When $k = 2$, it is called the quadratic residuosity problem (mod $n$, where $n$ is ...
Misty's user avatar
  • 51
4 votes
0 answers
285 views

XOR of a secure PRF is modified weakly secure PRF

While reading A Graduate Course in Applied Cryptography by Dan Boneh and Victor Shoup. There was the next exercise (Ex. 4.2 (b)), let $F$ be a secure PRF over $(K,X,Y)$ where $Y := \{0,1\}^n$ and $|X|$...
seanL's user avatar
  • 66
4 votes
0 answers
126 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
4 votes
0 answers
1k 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 $\...
jvdh's user avatar
  • 173
4 votes
0 answers
200 views

Formal Verification for Multiparty Computation and Homomorphic Encryption?

I've recently found some work on the use of Formal Verification Software, like ProVerif for enclaves. I wonder is if its feasible to have something similar for MPC and Homomorphic Encryption and ...
DaWNFoRCe's user avatar
  • 872
4 votes
0 answers
66 views

Security proof regarding a zero-knowledge counterexample that is secure in the stand-alone model but insecure in the UC model

Background The following zero-knowledge (ZK) counterexample is described in Canetti's work [Security and Composition of Cryptographic Protocols: A Tutorial, page 26] to show that there exists some ...
X. G.'s user avatar
  • 424
4 votes
0 answers
190 views

Multi-users RSA problem

Rivest and Kalisky's RSA problem considers various notions on security of the RSA One-Way Trapdoor Permutation. They do it only from the perspective of a single user. What's the state of the art in ...
fgrieu's user avatar
  • 142k
4 votes
0 answers
149 views

The security of blind RSA signatures with modular exponentiation as padding

It is known that (blind) RSA signature implementations should apply some sort of padding to messages before signing or blinding them. Does blind RSA signature with modular exponentiation as a padding ...
István András Seres's user avatar
4 votes
0 answers
525 views

Security properties of ElGamal encryption variants

I'll use Taher ElGamal's A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms (July 1985 in IEEE Transactions on Information Theory, formerly in proceedings of Crypto 1984) as ...
fgrieu's user avatar
  • 142k
4 votes
0 answers
112 views

About Cocks IBE

Why doesn't Cocks IBE use the hash function H from ID space to quadratic residue set $\mathbb{QR}_N$ in $\mathbb{Z}/N\mathbb{Z}$ to reduce the ciphertext expansion by half? I think it is also IND-ID-...
Xiaopeng Zhao's user avatar
4 votes
0 answers
176 views

Use of randomness in an Elgamal like encryption

Suppose I have the following encryption scheme: for a message $m\in\mathbb{F}_p^*$, I generate the ciphertext = $(g^r,f^mh^r)$ where $g$ is the generator of a cyclic group $G$ of unknown order $n$ and ...
Papa Delta's user avatar
4 votes
0 answers
109 views

Functional encryption for inner products from DDH

I have been reading this paper by Abdalla, et al. But there's something I don't get about the security proof (Theorem 3.2) for the basic IP scheme from DDH--how are they simulating the mpk's using $g^...
Cinderella's user avatar
4 votes
0 answers
258 views

computational indistinguishable/distinguishable?

Let $a,b,c,d$ be selected at random from $Z_q$. Consider the following two distributions $X_1$ and $Y_1$: $X_1={(r_1\cdot a, r_2\cdot b, r_3\cdot c, (r_1+r_2-r_3)\cdot d)}$ where $r_1,r_2,r_3$ ...
mohsen pourpouneh's user avatar
3 votes
0 answers
120 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
3 votes
0 answers
204 views

Is it necessary for a round function $F$ in a Feistel cipher to be pseudorandom?

I stumbled across this question where the questioner asked for specific requirements for the round function $F$ in a Feistel network so that the construction is secure. The answer explained that a ...
trivicious's user avatar
3 votes
0 answers
455 views

Security of Full Domain Hash (or not quite full)

Full Domain Hash is the simplest signature scheme based on a trapdoor permutation (such as textbook RSA) that enjoys a strict security reduction. It was introduced by Mihir Bellare and Phillip Rogaway:...
fgrieu's user avatar
  • 142k
3 votes
0 answers
60 views

trust-less blind execution environment (thought experiment)

I apologize for the theoretical nature of this question, but It has cost me a lot of sleep over the past months. Querying my immediate peers has so far failed to produce results. I assume this ...
telamon's user avatar
  • 131
3 votes
0 answers
86 views

Are there only two ways to prove a cryptographic protocol is secure?

If I want to prove my protocol is secure, can I just use a game based approach and/or a simulator approach? Or are there other common approaches?
WeCanBeFriends's user avatar
3 votes
0 answers
110 views

Provably secure way of expanding permutations

Gimli is a 384-bit permutation that makes use of an internal 96-bit permutation which works on columns. Every 4 rounds starting from the 1st a "small swap" is performed and every 4 rounds ...
Bob Semple's user avatar
3 votes
0 answers
1k views

Are there any hash functions that are commutative yet secure for ordered lists?

I'm looking for a hashing function that can combine random numbers together in any order yet still find the same value. But it needs to be secure against hackers. The idea is if I'm hashing together: ...
mczarnek's user avatar
  • 203
3 votes
1 answer
180 views

Proof that secret sharing based scheme is CPA secure as long as one of the scheme is CPA secure

I want to construct a CPA-secure scheme using two given schemes $\prod_1$ and $\prod_2$ if only one of them is CPA secure. Taking suggestions from this answer, I am able to construct a scheme as ...
sourav goyal's user avatar
3 votes
0 answers
165 views

Equivalents of Yao's Xor lemma to rounds, or other hardness amplification methods?

Simple question: I just learn the existence of the great Yao's Xor lemma (see a quick sum-up at the end of this post). I'd like to use a similar argument, but instead of a simple function, I've a two ...
Léo Colisson's user avatar
3 votes
0 answers
116 views

Proving simulation-based security with unreliable real-world channels

An ideal functionality considers reliable communication channels, whereas a real functionality must consider unreliable communication channels (e.g., channels controlled by the adversary). Thus, it ...
Alpha Bravo's user avatar
3 votes
0 answers
83 views

Assuming the difference between success probabilities to be positive

Context: I am currently studying Theorem 3.1 in the paper Number-Theoretic Constructions of Efficient Pseudo-Random Functions by Naor and Reingold. The theorem basically states the randomized self-...
Dave's user avatar
  • 131
3 votes
0 answers
620 views

Is a PRG that reveals the first bit of the input secure

Let $G:(0,1)^n \rightarrow (0,1)^{n+1}$ be a secure PRG. Define $G'(s):=s_1 ||G(s)_{2,...,n+1} $. ($||$ is concatenation, and the subscript $ _{2,...,n+1}$ means the last $n$ bits of $G$) I claim ...
sel's user avatar
  • 325
3 votes
0 answers
489 views

Understanding hybrid arguments in detail

Assume we are given three distributions $H_{1}$, $H_{2}$ and $H_{3}$ and the following security games: $Game_{1}$: Distinguish between $H_{1}$ and $H_{3}$. $Game_{2}$: Distinguish between $H_{1}$ ...
EllipticNoob's user avatar
3 votes
0 answers
72 views

Incorrect answers to queries in Waters' IBE proof by Bellare and Ristenpart

In "Simulation without the artificial abort: Simplified proof and improved concrete security for Waters' IBE scheme", Bellare and Ristenpart present a new proof for Waters' IBE scheme that does not ...
cygnusv's user avatar
  • 5,002
3 votes
0 answers
686 views

LR-Oracle Experiment in Lindell and Katz

In reference to the LR-Oracle experiment in “Introduction to Modern Cryptography” (2nd edition) by Lindell & Katz, Definition 3.23 states a scheme $\pi = (Gen,Enc_K,Dec_K)$ is CPA secure for ...
Rohit Khera's user avatar
3 votes
0 answers
209 views

Brute force attack multiple stream cipher

Assume that a scheme used to secure a specific system $Π=(Gen,Enc,Dec)$ which is thought have indistinguishable multiple encryption in the presence of an eavesdropper. For any adversary $A$ that can ...
M.S.B's user avatar
  • 31
2 votes
0 answers
62 views

Inequalities in collision search on the separation between the classical and quantum random oracle (ROM vs QROM)

I'm trying to read the separation between the classical and quantum random oracle through a paper "Random Oracles in a Quantum World" by Dan Boneh, Ozgur Dagdelen, Marc Fischlin, Anja ...
Dai Chi DO's user avatar
2 votes
0 answers
52 views

self-decryption paradox in identity based encryption

In the paper Dual system encryption: realizing fully secure IBE and HIBE under simple assumption (free PDF), the authors said "there is an apparent paradox in this strategy since it seems that ...
Alex Ideal's user avatar
2 votes
0 answers
38 views

Stand-alone simulation proof: Ideal functions and leakage collection

Are ideal functions and leakage collections the terms of UC security? Why I often see them in a simulation-based proof under stand-alone model? Some papers use the definition in Lindell's How to ...
Jeffrey's user avatar
  • 137
2 votes
0 answers
106 views

Automated Security Protocol tool that models algebraic operations

Are there any automated security protocol verification tools that model algebraic operations; specifically addition. I am familiar with AVISPA and Verifpal, and they are both great and user-friendly ...
Mona's user avatar
  • 197
2 votes
0 answers
113 views

Composability of state-separable proofs

Brzusk et al. introduced the state-separation proof technique to tame complexity in game-based security proofs. The framework allows for modular, easy to understand, and reusable proofs. It has been ...
Marc Ilunga's user avatar
  • 3,338
2 votes
0 answers
126 views

Regev PKE not CPA secure for specific $A$?

I encountered notes stating that, for certain fixed $A$, such as $A \in M_{n\log(q)\times n}$ as follows: \begin{bmatrix} 1 & 0 & 0 &\dots\\ 2 & 0 & 0 &\dots\\ 4 & 0 & ...
Anon's user avatar
  • 403
2 votes
0 answers
131 views

A Question on the "rewinding" technique in secure computation

Consider secure two-party computation against malicious adversaries in the standalone model. I know that the "rewinding" technique can be used to extract the corrupt party's input, e.g., in $...
X. G.'s user avatar
  • 424
2 votes
0 answers
27 views

How to prove the security of the MT-based multiplication protocol via the simulation paradigm

It is known that Multiplicaiton Triple (MT) can be used for secure online multiplication, which is defined by $\mathsf{Mul}(x, y)=(z_0, z_1)$, where $x\cdot y = z_0 + z_1$ $P_0$ sample random $a$, ...
xxx's user avatar
  • 21
2 votes
0 answers
91 views

Noise flooding with Renyi divergence

According to this question, I found papers that deal with noise flooding with Renyi divergence. However, the answer is still unclear to me on how to use Renyi divergence on the noise flooding ...
Newbie's user avatar
  • 21
2 votes
0 answers
162 views

Quantitative security of signature scheme obtained by Fiat-Shamir tranform

I'm looking for a quantitative yet simple proof of the EUF-CMA security of a signature scheme obtained by Fiat-Shamir transform. Recall the Fiat-Shamir transform starts from a 3-pass identification ...
fgrieu's user avatar
  • 142k
2 votes
0 answers
70 views

Provably Secure FPEs vs Practically Used FPEs

I have just checked a few FPE schemes like "Swap-or-not", "Mix-and-cut" which are provably secure. What techniques do the provably secure FPE scheme provably secure? The FPE ...
Crypto_researcher's user avatar
2 votes
0 answers
66 views

Why a simulator can obtain a corrupted party's input to some subrountine ideal functionality $F$ "for free" in $F$-hybrid model?

In "How To Simulate It" (page 45, line 10), Lindell noted that, in the $f_{\textsf{zk}}$-hybrid model (where $f_{\textsf{zk}}$ denotes the ideal zero-knowledge functionality) in the stand-...
X. G.'s user avatar
  • 424
2 votes
0 answers
171 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 ...
Crypto_researcher's user avatar
2 votes
0 answers
45 views

Is it secure to use the same master secret key in two independent IBE schemes?

Given two IBE schemes: Boneh-Franklin IBE scheme (https://doi.org/10.1007/3-540-44647-8_13) Secure under the CBDH problem (in the ROM) The master secret key is a random element in $\mathbb{Z}_p$ ...
Ati's user avatar
  • 31