# Questions tagged as ['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.
Score: 5
Can a series of triangle reflections be used for cryptography?

(I guess no but why is this the case? Any way to make it possible?)

Out of a given equilateral triangle T1 (with his 3 vertices A,B,C lying in a finite Field $$\mathbb F_N^D$$) another equilateral triangle T2 can get constructed by mirroring one of the 3 vertices at the edge in between the two other vertices. This will be repeated multiple times.

Given just two random triangle T1 and T2 (and $$\mathbb F_N^ ...$$

Score: 1
Provable security: impossible reduction when messages are encrypted/semantic security with function depending on the output of adversary

I've a problem with a protocol for which I can prove the security if the messages sent by the adversary are sent in clear, but I can't prove the security anymore if the messages sent by the adversary are encrypted... and this is a bit strange since I expect the protocol to also be secure in that second case.

More precisely, I'm considering a protocol for which a server Bob receives a message $$k$$ from ...

Score: 6
Small error in security proof on the paper On the Multi-User Security of Short Schnorr Signatures with Preprocessing

I think I found a small error in the security proof Link end of page 37. It states that

$$\sum_{i\leq q} \frac{3i+2}{p-(3q +2)^2/4} \leq \frac{3(q +1)q/2+2}{p - (3q +2)^2 /4}$$.

But shouldn't it be

$$\sum_{i\leq q} \frac{3i+2}{p-(3q +2)^2/4} \leq \frac{3(q+1)q/2+2q}{p - (3q +2)^2 /4}$$ ?

I think that the proof still works, since we want to show that you need $$\mathcal{O}(\sqrt{q})$$ queries to succe ...

Score: 1
How are probabilities combined in the game hopping proof technique?

I'm currently studying a paper (Sequences of Games: A Tool for Taming Complexity in Security Proofs) on proving semantic security using the Game Hopping technique by Victor Shoup.

On pages 9-11, he is using a sequence of three games, $$Game 1$$, $$Game 2$$, and $$Game 3$$ to deduct the semantic security of Hashed ElGamal to DDH and entropy smoothing assumptions. How does he combine the three probabilitie ...

Score: 2
Question about styles of reduction proofs

In cryptography security proofs mainly use the reduction proof technique. I now have read a lot of reductions proofs and also did some on my own and I think I understand it pretty well. While reading those proofs I noticed two main styles of such a reduction.

Say we have scheme $$B$$ based on $$A$$. We know $$A$$ is secure. If one wants to proof the security of $$B$$ by reducing it to the security of $$A$$ ...

Score: 0
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 indistinguishable security and there is said, that the challenger gets two sets of messages from the adversary. Say we have the PRG cryptosystem, that XORs messages with the output of the PRG. Why couldn't the ch ...

Score: 1
(Multi-User) Security Key-prefixed Schnorr Signature

Bernstein proofs in his paper that single-key security of the classic Schnorr signature system tightly implies the single-key security of the key-prefixed variant of the system. Can this statement be applied also for short schnorr signatures (halved hash output length)? In other words: Does single-key security of short schnorr signature system tightly implies the multi-key security of the key-prefixed va ...

Score: 2
Proving a derived MAC is secure via reduction

I don't have a very specific question, but reductions have been a weaker suit of mine and I was wondering if there is a secure MAC scheme, and a derived MAC' that uses MAC but modifies it in some way, how could you prove that MAC' is secure via reduction? I know how to do reductions for PRGs and PRFs, but not sure how to use it for MACs. I don't have a concrete example, but a walkthrough of the general  ...

Score: 1
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) one can find a security definition and experiment for those attacks. E.g. to define CPA-security. Those experiment are between a arbitrary adversary and a challenger. I was wondering, if there exists such  ...

Score: 3
Hash function requirements for short Schnorr Signature

Neven et al. stated in their paper Hash Function Requirements for Schnorr Signatures following theorem (using the forking lemma): $$\mathbb{G}$$ is the generic group (section 2), $$s \approx \log_2q$$, hash function $$H: \lbrace 0,1 \rbrace^* \rightarrow \lbrace 0,1 \rbrace^n$$.

Theorem 1 If the discrete logarithm problem in $$\mathbb{G}$$ is $$(t_\text{dlog}, \epsilon_\text{dlog}$$-hard, then the Schnorr Signatu ...

Score: 2
Clarification of the provable cryptography controversies

I read about the provable cryptography in Wikipedia. The article referred to tense controversies around 2007.

Do these controversies still exist?

What is the substitution for the provable-security? Is not it sufficient? I think AES does not follow provable cryptography style, am I right?

Which is the accepted/preferred view in the Cryptography community?

Why did it started in the first place, Is n ...

Score: 1
Superscript vs subscript notation in cryptographic formulation

I'm currently reading this paper [PDF]. On page 4, I bumped into these notations :

$$$$\text { Experiment } \operatorname{Exp}_{\mathcal{F} \mathcal{E}, A}^{\text {ind-mode }}(k) \text { : }$$$$

$$$$A_{1}^{\mathrm{KDer}\left(s k_{i}\right)}(p k)$$$$

I tried searching online and resolved most of the other notations involved, like the $$\stackrel{\\\}{ ...$$

Score: 7
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 parameter is $$k$$. The Schnorr Signature $$\sigma = (s,e)$$ with $$s,e \in \mathbb{Z}_q$$ has a signature length of $$4k$$ bits ($$s$$ and $$e$$ have $$2k$$ bits, $$e$$ is a hash output). The Short Schnorr Signature uses a shorter  ...

Score: 1
The Diffie-Hellman-based Private set intersection protocol cannot pass simulation proof?

Given the popular Private Set Intersection (PSI) protocol first described in [1]:

• Alice choose a random $$a$$, and sends $$\{H(x_i)^{a}\bmod p\}| (i=1,...m)$$ to Bob.
• Bob choose a random $$b$$, and sends $$\{H(y_i)^{b}\bmod p\}| (i=1,...n)$$ to Alice.
• Alice computes and sends $$\{H(y_i)^{ba}\bmod p\}| (i=1,...n)$$ to Bob.
• Bob computes and sends $$\{H(x_i)^{ab}\bmod p\}| (i=1,...m)$$ to Alice.
• Each party locall ...
Score: 0
Static vs Adaptive security of a distributed cryptographic protocol

Let $$n$$ be the number parties in a distributed cryptographic protocol where an adversary can corrupt up to $$n/3$$ nodes in the network.

Static Adversary: The set of corrupt nodes is fixed a priori.

Let’s say we do not know how to prove a distributed cryptographic primitive X secure against an adaptive adver ...

Score: 1
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 schemes used in practice use Feistel Network like FF1 and FF3. What makes provable secure FPEs work slower so that they are not used in practice?

Score: 1
Security level of FHE constructions for non-standard parameters

homomorphicencryption standards already provide recommended parameters and their corresponding security levels. However, I would like to calculate a security level for nonstandard parameter selection.

Is there an simple way to calculate the security level?

Score: 1
Proof Techniques to Prove System Secure

I have so far seen the proof by reduction technique to prove the security guarantee of cryptosystem where we consider breaking the cryptosystem as hard as solving a difficult mathematical problem. What are the other proof techniques used to prove the security of the Cryptosystem? It would be beneficial if the technique is briefly stated.

Score: 4
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 $$\mathcal{E}$$, such that given any pair of accepting transcripts $$(com,ch_1,resp_1),(com,ch_2,resp_2)$$ with $$ch_1\neq ch_2$$, $$\mathcal{E}$$ can recover $$sk$$.

(2) can be found in Katz: Digital Signature ...

Score: 0
Ensure that a speedrun (or video recording) was done in one continuous hop (and not spliced together from many parts)

In speedrunning video games, one records a game being played and beaten in one continuous attempt. However, what can be done to cheat is to do multiple attempts, and splice together clips of the best segments to make one fast speedrun that wasn't done in a single continuous hop. This splicing isn't hard, as e.g. loading screens always look the same, so you can swap the video at those points witho ...

Score: 1
Can interactive zero-knowledge proof systems be implemented using secure two-party computation?

I am defining multi-party computation using the real-ideal paradigm (see A Pragmatic Introduction to Secure Multi-Party Computation). That is, for any successful attack on an MPC protocol in the real world, there exists a simulator that carries out this attack successfully in the ideal world. It follows that security in the real world must be equivalent to security in the ideal world.

I am defining inter ...

Score: 4
Are there different definitions of secure two-party computation?

While reading tutorials on two-party computation I encountered two (at least formally) different definitions of security (with semi-honest adversaries). What I want to know is whether these definitions are actually different or can be shown to be equivalent. I suspect that they are different, but I might be missing something, considering that I have not read anywhere about different definitions.

...

Score: 1
How was the adversary's success probability calculated in this 2002 paper by Dodis, Katz, Xu, Yung about key-insulated signature schemes?

In this paper ("Strong key insulated signature schemes" by by Dodis, Katz, Xu, Yung (2002)), I understand most of the proof for Lemma 1 (pg. 9); I struggle with how some of the probability is calculated though.

No need to read the paper, I think, all you need is the following:

## Context

• Adversary $$A$$ breaks (the "new") scheme $$\Pi$$
• Challenger $$A'$$ wants to break the underlying scheme $$\Theta$$ usin ...
Score: 1
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 their applications?

I always thought there were limitations adopting simulation based proofs and Universal Composability, in general, in Formal Verification, but as of late I'm thinking there must be mor ...

Score: 1
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-alone model,

if the adversary controls the party running the prover, then it directly sends the input and witness pair $$(x, w)$$ to $$f_{\textsf{zk}}$$. This means that a simulator who internally runs the adversary wi ...

Score: 2
Security of Signature Schemes in the Multi-User Setting

I've often read about the security of a signature scheme in the multi-user setting Link1 Link2, but I couldn't find a real definition. I would like to be sure that I understand it correctly. So my question is: If we consider Def 1, would Def 2 make sense for the multi-user setting?

Def 1: The signature scheme yields k-bits of security in the single-user setting if the probability that an attacker can  ...

Score: 0
When does a proof by reduction do not hold?

I was doing the following exercise from the Introduction of Modern Cryptography from Katz and Lindell:

Let $$F$$ be a length preserving pseudorandom function. For the following constructions of a keyed function $$F' : \{0,1\}^n \times \{0,1\}^{n-1} \rightarrow \{0,1\}^{2n}$$, state whether $$F'$$ is a pseudorandom function. If yes, prove it; if not, show an attack.

(d) $$F'_k(x) \stackrel{def}{=} F_k(0||x) || ...$$

Score: 3
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 protocol that is secure in the stand-alone model but insecure in the UC model:

Assume there is such a "puzzle system" that both the prover and the verifier can efficiently generate puzzles, and

• The prover c ...
Score: 3
What is the reason for Shamir scheme to use modulo prime?

In Shamir's secret sharing scheme, Dealer performs the following steps

1. Choose a prime number $$q$$ such that $$q > n$$

2. Choose a secret $$s$$ from finite field $$\mathbb{Z}_q$$

3. Choose $$t-1$$ degree polynomial

$$g(x)=s+c_1x+c_2x^2+\cdots +c_{t-1}x^{t-1}$$

1. Compute shares $$s_i = g(id_i) \mod q \text{ for } i=1,2, \cdots,n$$ and sends secretly to participants

2. At least threshold number of participants ca ...

Score: 2
Can CPA secure scheme be converted to CCA secure?

I would like to know if there are some methods or techniques that can convert a public key encryption scheme from CPA secure to CCA secure?