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.

Filter by
Sorted by
Tagged with
3
votes
0answers
54 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 ...
1
vote
2answers
54 views

Is it possible to verify that the output of an executable came from its unaltered control flow?

I suppose an executable could contain a key which signs its output, but that key could be extracted and used to sign other data. Is it possible to verify that the output of an executable is the direct ...
2
votes
1answer
78 views

Katz/Lindell 2.4 - Generalizing from 2 messages to any message space?

I'm trying to solve problem 2.4 in "Introduction to Modern Cryptography" (2nd edition) for self-study. The problem asks to prove that perfect secrecy $$ Pr[M = m | C = c] = Pr[M = m] $$ ...
0
votes
1answer
46 views

Security in a pipeline

I am new to cryptography, I am trying to design a secure pipeline environment for the fast transfer of messages. To reduce the Key size I am planning to encrypt the messages with AES session keys (for ...
0
votes
0answers
21 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 ...
0
votes
1answer
33 views

Some misunderstanding on the Security Proof with Oracle

I have a question about the security proof. Suppose that I proved the following relations. That is, I proved that $Adv_A \le Adv_A^{O} \le Adv_B$, where A,B are some cryptographic schemes and O is an ...
1
vote
0answers
36 views

Showing that $F'(k, x) := F(F(k, 0^{n}), x)$ is a PRF [duplicate]

I wanted to do some practice on security reduction proofs, and I am stumped on this one from the Boneh-Shoup book. If $F(k, x)$ is a secure PRF, then show that $F'(k, x) := F(F(k, 0^{n}), x)$ is a ...
0
votes
1answer
48 views

Where can I find good practice questions for proofs by reduction?

I already have the Katz-Lindell textbook, but I also want some additional practice problems for security reductions for stuff like PRFs, MACs, digital signatures, private and public key schemes, and ...
0
votes
2answers
92 views

What are security reductions of symmetric-key algorithms?

I was reading Wikipedia page of post-quantum cryptography. It says that it is desirable for cryptographic algorithms to be reducible to some particular mathematical problem, that is intractability of ...
5
votes
1answer
1k views

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 ...
1
vote
0answers
31 views

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 ...
6
votes
1answer
602 views

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 $\...
1
vote
1answer
194 views

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 ...
2
votes
1answer
104 views

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 ...
0
votes
0answers
32 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 ...
1
vote
0answers
31 views

(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 ...
2
votes
1answer
74 views

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, ...
3
votes
1answer
163 views

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$, ...
1
vote
3answers
461 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)...
2
votes
1answer
648 views

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 ...
1
vote
1answer
103 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 { :...
7
votes
0answers
177 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 ...
1
vote
1answer
67 views

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 $\...
0
votes
0answers
36 views

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. ...
1
vote
0answers
36 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 ...
1
vote
1answer
53 views

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. ...
1
vote
1answer
61 views

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. ...
4
votes
0answers
102 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 $\...
0
votes
1answer
56 views

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 ...
1
vote
1answer
54 views

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 ...
4
votes
1answer
124 views

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 ...
1
vote
1answer
36 views

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 ...
1
vote
0answers
50 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 ...
1
vote
0answers
25 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-...
2
votes
2answers
56 views

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 ...
0
votes
0answers
46 views

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 ...
3
votes
0answers
36 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 ...
2
votes
1answer
123 views

What is the reason for Shamir scheme to use modulo prime?

In Shamir's secret sharing scheme, Dealer performs the following steps Choose a prime number $q$ such that $q > n$ Choose a secret $s$ from finite field $\mathbb{Z}_q$ Choose $t-1$ degree ...
2
votes
1answer
103 views

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?
0
votes
0answers
51 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 +,-,< ......
2
votes
2answers
164 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 ...
1
vote
1answer
47 views

If a protocol has a statistical security parameter, does this mean it is only computationally 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 ...
2
votes
1answer
39 views

Specialized simulators in Universal composability

The UC framework [Can00 (version of 2020-02-11)] defines security (defn 9) as for all adversaries there exists a simulator such that for all environments the environment output is indistinguishable in ...
0
votes
1answer
62 views

Set membership proof for private value and set

This set membership proof is used in P2P networks, when one party possesses a private value, and the other party possesses a set. They would have to broadcast some data associated with the value and ...
1
vote
0answers
66 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 ...
4
votes
2answers
283 views

Quantitative reduction of Schnorr's identification scheme to DLP

Question I seek a quantitatively better proof of theorem 13.11 in Katz and Lindell's Introduction to Modern Cryptography (3rd edition) (or nearly equivalently, theorem 19.1 in Dan Boneh and Victor ...
0
votes
0answers
79 views

Proof of theoritical security of Shamir's secret sharing

community ! I'm looking for the proof of theoritical security of Shamir's secret sharing. I found some articles saying that it's assimilable to the halting problem, which implies that there is no ...
4
votes
2answers
854 views

What does existential unforgeability mean in a digital signature scheme?

In a digital signature scheme (Gen, Sign, Verfiy) that satisfies correctness and existential unforgeability, can you assume that the outputs of Sign() are computationally indistinguishable from random?...
3
votes
1answer
187 views

How to build a periodic PRF from a PRF?

This question may be related to this one, though the construction differs. Let us consider a PRF $f$. We define $g_k$ as $g_k(x)=f(x)\oplus f(x\oplus k)$. Is $g_k$ a PRF, assuming $k$ is chosen at ...
7
votes
1answer
176 views

Difference between Generic Group Models

I'm trying to understand the difference between the (classical) Generic Group Model as it is described by Shoup [Shoup] and the somewhat restricted Generic Group Model as it is described by Schnorr ...

1
2 3 4 5
12