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.

70 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
9
votes
0answers
391 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 ...
7
votes
0answers
139 views

Replacing signer with simulator

Assume we can prove security of digital signature scheme against key-only (no message) attacks. Now we want to prove security against adaptive chosen message attack. We use random oracle model. The ...
7
votes
0answers
307 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 ...
6
votes
0answers
63 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 ...
5
votes
0answers
163 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 ...
5
votes
1answer
451 views

Hash function as secure as one-time pad?

We know that the one-time pad is provably secure as a cipher to encrypt some data. Is there an algorithm which does the same just as a hash function? Can we get a provably secure hash function? Maybe ...
4
votes
2answers
136 views

Why ``adversary'' and ``challenger'' and what are typical roles of those?

I'm confused with words adversary and challenger, that are used in proof of security of some cryptosystems. For example, adversary and challenger appear in the formal definitions of IND-CPA, IND-CCA, ...
4
votes
0answers
82 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-...
4
votes
0answers
97 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 ...
4
votes
0answers
152 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$ ...
4
votes
1answer
262 views

Formal Verification of DHKE protocol using ProVerif

I am new to ProVerif and trying to verify a simple DHKE protocol. The attacker is assumed as passive. The specifications are: The attacker cannot obtains the mutual key. Both participants obtain the ...
4
votes
0answers
60 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 ...
3
votes
0answers
52 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 ...
3
votes
0answers
41 views

Are there any more ways to validate a security proof except peer review?

Are there any ways better than peer review to validate a security proof? Are there any ways to make your security proof easier to validate; using a simulator based proof instead of a game based proof? ...
3
votes
0answers
51 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 ...
3
votes
0answers
104 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 ...
3
votes
0answers
66 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^...
3
votes
0answers
74 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-...
3
votes
0answers
229 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, ...
3
votes
0answers
260 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 ...
3
votes
0answers
55 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 ...
3
votes
0answers
370 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 ...
3
votes
0answers
140 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 ...
2
votes
0answers
34 views

decrypting a one-time-pad that outputs 0,1 in preknown probabilities

assuming a two users want to use a one time pad ciphersystem, and they are using a program that was developed by a third party that was supposed to create random undependable bits, but for some reason ...
2
votes
0answers
70 views

Security of MAC-Then-Encrypt without MAC key authentication

We have the following settings in our system: TLS 1.2 using legacy cipher suite - OFB mode (using 64 bit block cipher) and trunkated CBC-MAC (32 bit). The goal is to achieve authenticated encryption ...
2
votes
0answers
38 views

Leftover hash lemma-like without lossy functions

In short: Are lossy function the only way to prove security using leftover hash lemma for computationally secure protocols? Longer: I recently discovered/understood the leftover hash lemma, that ...
2
votes
0answers
169 views

How few cryptographic primitives can we use to derive all other constructions?

We have a lot of cryptographic primitives now, and many methods of deriving one type of scheme from another. There are even some like the Merkle signature scheme, which uses a hash function to derive ...
2
votes
2answers
65 views

Sensitivity of probability measure in differential privacy

I know that we need some sort of sensitivity(global, local) to calculate noise that needs to be added for differential privacy. The noise is the maximum difference between two neighboring datasets. ...
2
votes
0answers
111 views

Why does the DBDH simulator have half the advantage of an adversary?

Literature that includes the DBDH assumption such as this paper or this paper has a formal security proof that states: Suppose an adversary with non-negligible advantage $\varepsilon = Adv$. A ...
2
votes
0answers
273 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}$ ...
2
votes
0answers
74 views

Can we use a pseudorandom function in both models of a simulation based proof?

Assume in the real model a party blinds a fixed element $b$ as: $v_i=r_i\cdot b$, where $r_i$ is a output of pseudorandom function. So we give $v_i$ to a semi-honest adversary. Now we want to sketch ...
2
votes
0answers
168 views

Proof of IND-q-CCA security

I have some questions about the paper Bounded CCA2-Secure Encryption (pdf). On page eight "3.2 Construction", the authors have done a black-box construction of an IND-q-CCA security schema and then ...
2
votes
0answers
422 views

Looking for a detailed example of proof by reduction

I'm looking for a very detailed example of proof by reduction. Say we have two or three protocols (that have been proven secure) and we construct a new protocol. We want to provide a proof of security ...
2
votes
0answers
92 views

Protocol/algorithms based on a variable-length input PRF

Are the proofs based on a PRF assumption still valid when using a variable-length input PRF ? The answer might be obvious, but I have a doubt.
2
votes
0answers
689 views

Ideal system for an encryption scheme

What is the ideal system for an encryption scheme? For a pseudorandom permutation the ideal one is a random permutation, for a pseudorandom function the ideal one is a random function. For an ...
1
vote
0answers
60 views

Do simulator based proofs still rely on the random oracle model?

I have seen many game based proofs using the random oracle model (ROM), do simulator based proofs require it? Is it possible to do a simulator based proof for every game based proof? For context: ...
1
vote
0answers
122 views

Reduction to security of proof system for proving knowledge

I want to prove security of my system by reduction to the security of an underlying non-interactive proof system for proving knowledge. I know a game that captures the desired security property of my ...
1
vote
0answers
31 views

Malicious OT from 'Efficient Secure Two Party Protocols' — defining the simulators

I am looking at Protocol 7.5.1 in Hazay and Lindell's Efficient Secure Two Party Protocols, it can found here (p 201). A similar protocol is proven secure in Section 7.4 (p190) and the proof is ...
1
vote
0answers
44 views

Prove that Alice’s solution x is equal to Bob’s plaintext m

The answer to the second part of this question exists already. However, I need help understanding how the first part of the question is solved. I have a feeling that it must have something to do with ...
1
vote
0answers
51 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 schemes 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 construct a scheme as ...
1
vote
0answers
56 views

Extractability property in Zero Knowledge Discrete Log problems

I am trying to construct a simulator and an extractor for a zero knowledge protocol. I just encountered this text that explains the construction of the simulator. Does someone know of a similar text ...
1
vote
0answers
44 views

Proofs of security for anonymity in a multi-party setting

I'm looking for material that proves the anonymity of parties in a non-interactive setting. I would like to know if there are simulation based proofs (UC) and property based proofs (game based) for ...
1
vote
0answers
47 views

Non-uniform Deciders for computational indistinguishability

I don't quite understand the notion of a decider having a probability distribution function associated with it, and what it exactly says about the decider. From here on page 3-4 it says ...Now, in ...
1
vote
0answers
37 views

A qusetion about the security game of Certificateless signatures

Recently I read Certificateless Public Auditing for Data Integrity in the Cloud , I have a question about the security of proposed HOMOMORPHIC AUTHENTICABLE CLS. (Sec. IV). For the Type-I Adversary, ...
1
vote
0answers
45 views

A modular approach to the design and analysis of authentication and key exchange protocols

I am studying modular approach to the design and analysis of authentication and of the key exchange protocols. One of them are proposed by bellare et al. On page number 11, I do not understand the ...
1
vote
0answers
58 views

Security of certain homomorphic encryption scheme

Is the following homomorphic encryption scheme: Ahmed El-Yahyaoui and Mohamed Dafir Ech-Chrif El Kettani, A Verifiable Fully Homomorphic Encryption Scheme for Cloud Computing Security (April 2018, at ...
1
vote
0answers
76 views

Can RSA be used as a one-time pad for authentication?

In the case of Smart Contracts, there are self-destruct functions for the contract which can only be run by the contract owner. In many cases attackers have found a way to take over the contract ...
1
vote
0answers
49 views

Cryptographic Tagging of Information over an Insecure Channel

Is there an efficient algorithm for the tagging and location of information over an insecure channel, where two parties (the tagger and the intended recipient for the tag) can recognize a piece of ...
1
vote
0answers
132 views

Whcih one is computationally more expensive: Zero knowledge proof or cut-and-choose

As we know, in order to have multi-party protocol secure against the malicious parties, researchers usually utilise the standard techniques such as zero-knowledge proofs or cut-and-choose technique. ...
1
vote
0answers
98 views

Chosen plain-text attack proof for Bethencourt CP-ABE scheme

Consider the CPA security game which consists of the following steps: Initialization Setup Phase 1 Challenge Phase 2 Guess Can someone provide the proof for this game under Bethencourt ...