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
2
votes
1answer
617 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
92 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
158 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
41 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
30 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
34 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
41 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
57 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
75 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
53 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
47 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
113 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
32 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
39 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
23 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
36 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
42 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
33 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 ...
1
vote
1answer
91 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
83 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
46 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
98 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
32 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
34 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
58 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
63 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
271 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
66 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
721 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
176 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 ...
4
votes
1answer
141 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 ...
2
votes
1answer
73 views

Names and games for security properties preventing substitution of signed message by the signer

Some signature schemes, notably ECDSA, unwillingly allow users to prepare their public/private key pair as a function of two arbitrary messages of their choice, and compute a signature that checks for ...
1
vote
0answers
38 views

Security game for factoring

this is probably a fairly simple request, but I have'nt been able to find it anywhere. A lot of cryptography schemes have security games associated with them. In the Book by Katz, a bunch of schemes ...
2
votes
1answer
60 views

Why require that public and private key each have length at least the security parameter?

In Jonathan Katz and Yehuda Lindell's Introduction to Modern Cryptography (3rd edition), the key generator of e.g. signature has The key-generation algorithm $\mathsf{Gen}$ takes as input a security ...
4
votes
1answer
99 views

Relation between short and «regular» Schnorr signature

I'm failing to fully understand the reasoning in 19.2.3 of Boneh and Shoup's A Graduate Course in Applied Cryptography. That constructs short («optimized»/original) Schnorr signature from «regular» (...
2
votes
0answers
70 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:...
0
votes
0answers
53 views

Random Oracle Model for an ideal block cipher vs Ideal Cipher Model

Some security proof involving an ideal function use the Random Oracle Model (ROM). They posit a thing that given integer $b$ and bistring $M$, returns what it previously returned for that input $(b,M)$...
2
votes
0answers
35 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$ ...
1
vote
1answer
99 views

RSA public key identification

Consider a multi party system where public keys of all receivers are known. Server wants to send message to one of them using (textbook?) RSA. Adversary is given ciphertext and even Message to be send,...
7
votes
2answers
235 views

Rabin-Williams signature and it's reduction to factorization

Rabin signature is rightly celebrated as a signature scheme with provable reduction to factorization. How do we show that for Rabin-Williams signature as standardized, under the common and realistic ...
1
vote
0answers
51 views

Cardinality of a set of successful hash values

Im trying to comprehend a proof from the paper "Efficient Identity Based Signature Schemes Based on Pairings"(2002) by Florian Hess. At one point of the proof for Theorem 2 I don't ...
0
votes
1answer
53 views

Reduction to the discrete log problem

Let $G$ be a group of prime order $p$ and generator $g$. Let $msk_i = (x_i, y_i) \in Z_p^2$ be two master secret keys and $mpk_i = (g^{x_i}, g^{y_i})$ the corresponding master public keys, $i \in [0, ...
0
votes
0answers
50 views

Question about game based security

When a game between an adversary $A$ and a challenger $CH$ is used in the security model of a scheme, and oracles are defined, does the adversary only have access to those oracles in the attack or ...
1
vote
0answers
50 views

How to compare two post quantum digital signature schemes in terms of latency?

I want to compare two digital signature schemes of different nature. One is Hash-based (Winternitz one time signature scheme) and the other is lattice-based (Dilithium Crystals). What about be an ...
1
vote
0answers
38 views

How to evaluate number of security bits of a signature scheme?

I am trying to evaluate the effective security levels that a digital signature scheme (namely post-quantum digital schemes like WOT-S (Winternitz one time signature scheme) and Dilithium Crystals). ...
1
vote
0answers
73 views

What's the difference between H(m) $\oplus$ H(key) and H(m || key) in MAC construction?

We all know that HMAC has the form of $H(ikey || H(okey || M))$. I'm wondering what if we replace the H(okey || M) into H(okey) $\oplus$ H(M)? In other words, is $$H\Big( ikey \mathbin\| \big( H(okey) ...
4
votes
1answer
71 views

What is meant by the probability distribution of a verifier?

I'm having trouble understanding the role of probability distributions in the definitions of computational/statistical indistinguishability, especially in the definition of zero-knowledge. From A ...
0
votes
0answers
66 views

About CPA or CCA security proof

Recently reading about CPA, CCA safety security proof. After reading a few papers, the author is in the process of proof. The challenger maintains some lists. I really don’t understand why the ...
0
votes
0answers
32 views

Does IND-CPA to INC-CCA effects on the error probability?

If we have a key encapsulation mechanism (KEM) that is IND-CPA secure, with some error probability $P_e$ (probability that the shared keys are not equal). The goal is to use the Fujisaki-Okamoto ...
2
votes
1answer
85 views

Data Security and Encryption

I have a research paper on data security using proxy re-encryption, and I need to provide an answer to a reviewer's comment. However, I have no idea on what to do or how to answer it. The security ...

1
2 3 4 5
12