Hot answers tagged provable-security
6
This is not a "block cipher" because a block cipher is a key-dependent permutation of the space of blocks of a given size. Here, you handle data by blocks, but the "encryption" part is done by XORing with a value $H(k+n)$ which depends on the key $k$ and on the "block number" $n$. So you do not have one permutation (for a given key), but a lot of them.
...
6
Summary. This scheme is insecure. It can be cryptanalyzed using standard methods from the cryptanalytic literature. It also has poor performance.
Your algorithm. To summarize your scheme, in your algorithm a one-bit message $m \in GF(2)$ is encrypted by picking a random quadratic polynomial $p(x_1,\dots,x_{128})$ in $GF(2)[x_1,\dots,x_{128}]$, setting $c ...
5
Yes, your scheme is fine.
Nitpick: I think you mean that your goal is to generate a random number in the range $0\ldots n-1$ (not $0\ldots n$). Also, to avoid bias, you need to generate $m$ as a random number in the range $0 \ldots (\lfloor 2^{256}/n \rfloor \cdot n)-1$ (not $0\ldots \lfloor 2^{256}/n \rfloor \cdot n$).
This problem is known as secure ...
4
It's actually quite simple.
Given your adversary $A$ against ind you construct an adversary $A'$ against ind$ by simply forwarding the queries and answers. (This may seem stupid but please bear with me.)
Consider now, the difference between the advantage of $A$ and $A'$:
$$\mathrm{Pr}[K \xleftarrow{$} \mathrm{Key} : A ^{\mathcal{E}_K(\cdot)} \Rightarrow 1] ...
4
Does matching all the test vectors mean my implementations are valid mathematically?
Basically the comments got it, but test vectors are designed to attempt to hit lots of cases, but with high probability will not catch every single mistake. Should you do it? Definitely. Does it mean everything is perfect? No.
Is implementing mathematics correctly ...
4
You have the math right, but you seem to have mis-interpreted the formulas. So, let me try to walk you through it.
The "advantage" of an attack is the difference $|\Pr[Exp(0)=1] - \Pr[Exp(1)=1]|$.
The advantage is a measure of how effective the attack is. If the advantage is large (significantly greater than 0), the attack is successful (and the function ...
4
To prove that a scheme is not secure under such a definition you usually would propose an algorithm such that the experiment described in your question outputs $1$ with probability non-negligibly larger than $1/2$.
As this looks very much like a homework problem I will not give you a solution. However constructing the algorithm is actually very simple in ...
3
Salsa20 is a stream cipher based on a pseudorandom function, not a pseudorandom permutation.
For a fixed key $k$ and nonce $n$, the mapping $PRF^{S20}_{k,n}: \{0,1\}^{64} \to \{0,1\}^{512}$, which maps a "Stream position" to "keystream block", is supposed to be a pseudorandom function. It is not supposed to be injective (i.e. a permutation, even less since ...
3
The inequality is obtained by a distance argument.
Consider two points $X,Y$ on the real line. Taking another point $Z$, you have $|X-Z| + |Y-Z| \geq |X-Z+Z-Y| = |X-Y|$.
Applying this "triangle" inequality to your equality 1, we have for any $z \in \mathbb{R}$,
$\begin{array}{l}
\bigl\lvert\Pr[A(x\oplus g(U_n))=1] - z\bigr\rvert
+ \bigl\lvert ...
3
I'm not sure that I understand the question completely, as there are plenty of proofs of real-ideal simulation-based definitions that are proved in a "sequence of games" style. So, I think that the question being asked might be either of the following:
Rather than comparing proofs, perhaps the question is about definitions. Specifically: what are the main ...
3
Levin showed that combining PRG with a universal hash function, one can reduce the number of calls. Roughly speaking, we shorten a message with a universal hash function before applying the GGM construction.
That is, $y = F_{k,k'}(x) = \mathrm{GGM}_G(k,h(k',x))$, where $h$ is a universal hash function.
At TCC 2012, Jain, Pietrzak, and Tentes gave another ...
3
A random oracle is an idealization of a hash function $H$: if hash functions were perfect they would be random oracles. This is why it is always easier to consider a hash function a random oracle when one proves something about a larger scheme. Those are "proofs in the random oracle model". [1]
That being said it is still possible to prove things using ...
3
As far as I know, there's no fundamental obstacle that would prevent you from implementing any crypto algorithm you want in JavaScript, whether on the server or the client side.
Compared to an optimized implementation written in C or assembly, JavaScript implementations of low level crypto primitives like block ciphers or PRNGs are likely to be slow and hard ...
3
As said in the comments, your construction is not what usually is called a block cipher.
A block cipher is a pair of (deterministic) functions with just two inputs: key and plaintext or ciphertext.
Your function has an additional input, the block number.
One could name this a tweakable block cipher (i.e. $n$ is the "tweak"):
$$ Enc_k^n(P) = P \oplus H(k, ...
2
The standard approach is to break this problem into two pieces:
What information is unavoidably leaked, merely by computing the desired function? In your case, the goal is to compute $\sum_i x_i$. This sum unavoidably leaks a little bit of information about the $x_i$'s. For instance, as you correctly state, if we somehow know that all $x_i$'s are ...
2
The randomness is not enough for IND-CCA-2. If we get a message (so $L$ bits of data plus the $y$ to reconstruct the random seed), we can modify it, say flip the first bit, and ask the decryption oracle for a decryption of the modified message (which will have the same $y$!), which we will get. Then the original message can easily be obtained: we get the ...
2
In Dolev-Yao and other formal models, the assumptions about adversary behavior are encoded via the grammar and entailment relation, and there's no mention of a specific computational definition of encryption security.
But your question is still meaningful, and can be interpreted as follows:
If my encryption scheme is CPA secure, and my protocol is ...
2
Proponents of simulation-based proofs will tell you that their notions are easier to understand and it's clearer what exactly the notion gives you. Compare Jens Groth in http://eprint.iacr.org/2002/002.pdf : his introduction (page 2) is a clearer answer to the "pros" in your question than I can come up with here.
However, if you're actually trying to ...
1
A standard approach in cryptography is to separate out the ideal specification (of what a scheme is supposed to achieve) from the particular instantiation (the implementation of the scheme).
To specify the security and functionality goals, sometimes cryptographers specify an "ideal functionality", which is an idealization of what we are hoping to achieve. ...
1
Guillo-Quisquater scheme uses the Fiat-Shamir trick to convert a proof of knowledge into a signature. There is a paper out there about the security of such schemes in the random oracle model here which seems to give what you want.
1
This is tricky and I don't know that there is a generic way to take care of all domain/auxiliary information.
The way we typically do proofs in multi-party computations is by defining an ideal world and show that the information generated in the ideal world (usually the encrypted inputs and the outputs) could be used to simulate the real world protocol ...
1
This question has been studied, starting in a very nice paper by Abadi
and Rogaway. [...] The linked paper resolves all of these details.
Please be aware that the paper by Abadi and Rogaway cited by another answer here only considers the passive adversary case, i.e., an adversary that can only eavesdrop but not insert messages. The active adversary ...
1
Suppose Alice has $x$ and Bob has $y$ in your scenario, and let $\pi =(\pi_A, \pi_B)$ be the protocol machines for Alice & Bob respectively. Here is how you would formally define security of the protocol against a corrupt Alice.
Define the following algorithms / random variables:
${\sf Real}(\pi, y,\mathcal{A},1^k)$:
Internally simulate an instance ...
Only top voted, non community-wiki answers of a minimum length are eligible
