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.

learn more… | top users | synonyms

2
votes
1answer
258 views

Security proof in pairing based cryptography

Let : $G_{0}$ and $G_{1}$ be two multiplicative cyclic groups of prime order $p$, $g$ be a generator of $G_{0}$ and $e$ be a bilinear map, $e : G_0 \times G_0 → G_1$ and let $𝐶_{1} = ...
2
votes
1answer
196 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 ...
1
vote
1answer
56 views

Are the following schemes based on a pseudo-random permutation secure?

I am currently working on the following task: Let F be a pseudorandom permutation. Consider the encryption scheme for the message space $\{0, 1\}^n$ defined as follows: $Gen(1^n)$ chooses ...
0
votes
1answer
46 views

How are security proofs done in ABE Schemes?

I have been studying several ABE schemes and I understand the security assumptions and the several types of security models used for the security game between the Challenger and the Adversary. What ...
0
votes
1answer
86 views

Difference left-or-right CPA security, IND-CPA security

I am trying to understand the notion of left-or-right-CPA (LOR-CPA) security for private-key encryption schemes introduced in my lecture. If I understood it correctly so far, the only difference to ...
6
votes
0answers
53 views

Explanation and proof of a well-know probabilistic lemma

Pointcheval and Stern in their paper on "Security proofs for Signature Schemes" state the following "well-known" probabilistic lemma: Let $A \subset X \times Y$, such that $\mathrm{Pr}[A(x, y)] ...
4
votes
0answers
159 views

Salary Negotiation Problem

Imagine Alice is applying for a new job. Alice has an idea of the minimum salary that she is willing to accept—let's call this value A. Bob, the hiring manager for ...
4
votes
0answers
71 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 Feistal ...
3
votes
0answers
65 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
86 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 ...
3
votes
0answers
143 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
76 views

Bridging the gap between security proofs and “real-world” security

I've been studying cryptography for a little while. I understand fairly well the nuts and bolts of security proofs, but I'm having trouble reconciling the formal statements of security in these proofs ...
2
votes
0answers
67 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
139 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 ...
2
votes
0answers
181 views

Setting protocol parameters to achieve concrete security

Background One issue with modern security proofs is that they are usually asymptotic. In other words, such proofs are usually formulated as follows: For any polynomial-time adversary $\mathcal A$, we ...
1
vote
0answers
63 views

Simulation-Based Proof: When a Secret Key is Involved

Assume we have a protocol in which a party receives an encrypted random polynomial. The polynomial is encrypted using his public key. We want to construct a simulator for this party (so this party ...
1
vote
0answers
21 views

Should we use exponent 3 in RSA-OAEP?

As I understand it the proof that RSA-OAEP is secure in the random oracle model is much tighter for exponent 3. Does that mean that exponent 3 should be chosen?
1
vote
0answers
16 views

Finding missing probabilities for formal proofs

In formal proofs, you often need to use probabilities to show that the Advantage of an algorithm is negligible. In proofs by contradiction, these probabilities are often tied to probabilities of ...
1
vote
0answers
64 views

Is $E_{k}(x) = F_{k}(x) \oplus F_{k}( \bar x)$ PRF?

$E_{k}(x) = F_{k}(x) \oplus F_{k}( \bar x)$ and F is PRF which maps $\left \{0,1 \right \}^n \times \left \{0,1 \right \}^n $ to $\left \{0,1 \right \}^n$. Let two messages $m_{0} = 0^l $ and $m_{1} ...
1
vote
0answers
21 views

Proving for a single input vs several inputs. Is there any difference?

I am working on a new protocol for pattern matching. While defining the ideal functionality, it is possible to say: Alice sends $p$ and Bob sends $T$ to the ideal functionality. i.e. searching for ...
1
vote
0answers
55 views

How to securely map an element from an smaller domain to the other element in a large domain

Problem: I have a small sized domain, say s-bit. It's clear that the probability for an adversary to guess an element is $ \frac{1}{2^s}$. I need to make the probability negligible. However, I need to ...
1
vote
0answers
420 views

Variant of the Decisional Bilinear Diffie Hellman problem

I am working on a cryptographic scheme and I need to rely on the following problem, which I have nicknamed the "Hybrid Decisional Bilinear Diffie Hellman (hDBDH)" problem: Let $e: \mathbb G_1 ...
1
vote
0answers
80 views

Efficient proof of knowledge using Wegman-Carter 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 ...
1
vote
0answers
109 views

Privacy-Preserving Protocols and Proofs of Security

While dabbling in privacy-preserving protocols (mainly using Semi-Homomorphic Encryption) and coming up with miscellaneous ideas for comparison tests or other similar primitives, based on obfuscation ...
1
vote
0answers
37 views

What is the restriction on k, for the kth composite residuosity problem to be hard

This paper considers the exponent to be an odd integer. When k = 2, it is called the quadratic residuosity problem (mod n where n is composite) which is hard and can be solved if the factorization of ...
1
vote
0answers
68 views

Is it feasible to break an encrypted and later encoded message?

A message is sent from a person to another. The plain message is first encrypted, even with a weak algorithm - say, DES. Then, the encrypted message is encoded with a simple substitution, which is ...
1
vote
0answers
60 views

Conditions for proving that a signcryption scheme is secure

If I'm able to prove that any scheme satisfies confidentiality ad unforgeability conditions, will it be a valid signcryption scheme, without explicit signature and encryption parts ?
0
votes
0answers
29 views

How is Extended Euclidean Algorithm related to Approximate-GCD problem?

I had a doubt regarding the connection between the Extended Euclidean Algorithm and the Approximate-GCD problem. Are there any relations? i.e., the hardness of A-GCD is derived from EEA. Is there any ...
0
votes
0answers
29 views

Is original DSA a TEGTSS-I scheme?

Brickell et al. define TEGTSS-I scheme in paper "Design validations for discrete logarithm based signature schemes" In this paper original DSA is generalized as DSA-I variant where $r = g^k \bmod p ...
0
votes
0answers
29 views

Permuted Hash Table

Suppose we have a hash table, $HT$, consisting of $100$ bins.The hash table uses a hash function $H$ that is public. We all know that given value $a$ we can compute the address in the hash by ...
0
votes
0answers
18 views

HMQV and MQV group representation attack

Currently reading Krawczyk's HMQV paper https://eprint.iacr.org/2005/176 and trying to follow what he says about the group respetnation attack on MQV: It says that for any group of prime order $q$, ...
0
votes
0answers
75 views

Perfect Secrecy of AES file Encryption

Why does AES file encryption not ensure perfect secrecy? I understand that $\Pr[E(K,M_1)=C_1] = \Pr[E(K,M_2)=C_2]$ given $M1\neq M2$ holds for perfect secrecy of a scheme. However, this seems to hold ...
0
votes
0answers
105 views

CPA-security of a pseudorandom permutation encryption scheme

Let $F$ be a pseudorandom permutation, and define a fixed-length encryption scheme $(Gen, Enc, Dec)$ as follows: on input $m \in$ $\{0,1\}^{n/2}$ and key $k \in \{0,1\}^n$, algorithm Enc ...
0
votes
0answers
66 views

Anyone familiar with domain of hash functions in bilinear pairing based system?

I need a clarification regarding domain of hash functions. I have defined a bilinear pairing based system as follows: Let G1 and G2 be cyclic multiplicative groups of prime order p generated by g1 ...
0
votes
0answers
34 views

Outsourced Multiparty computation proof in Ideal world

I need to know in an outsourced two party computation where honst $A$ and $B$ outsource their private and secure data to a malicious server, why we need to design a simulator that interacts with an ...
0
votes
0answers
49 views

Role of trusted party in the Ideal model in Malicious case

Imagine there is a protocol supporting outosurced multi party computation. There are three parties involved in the protocol: client $A$, client $B$ and a server. Client $A$ and $B$ send their private ...