# Questions tagged [cr.crypto-security]

Theoretical aspects of cryptography and information security.

251 questions
Filter by
Sorted by
Tagged with
207 views

### question about concurrent ZK paper by Prabhakaran & Sahai

Concurrent Zero Knowledge Proofs with Logarithmic Round-Complexity Page numbers are from the paper itself, and not the pdf. From page 3, "An interactive proof system is said to be black-box (...
77 views

### Length Extension Attack with a fixed length message [closed]

It's well known that using a hash function as message authentication is vulnerable to length extension attacks. ie. H(key+message) is a bad idea. H(message+key), H(key+message+key) have their issues ...
154 views

### The relation between NP and IP(2pfa)

As far as I know, it is not known whether $\mathsf{NP} \subseteq \mathsf{IP(2pfa)}$, where $\mathsf{IP(2pfa)}$ is the class of languages having interactive proof systems with some two-way ...
319 views

### One Way Boolean Function [closed]

If one way functions exist, what would the truth table of a one way boolean function look like?
448 views

Let $p$ be a large prime. Let $A$ be a $2\times 2$ matrix with coefficients in $GF(p)$ (i.e., coefficients taken modulo $p$). Let $B=A^k$, where $k$ is an integer not given to us. Given $p$, $A$, ...
353 views

### Appilicability of Theoritical Computer Science in Malware research

I would like to know the importance of TCS in Malware research. Due to the large volume of new malware variants received per day (~50,000 samples/day according to McAfee), malware researchers are ...
183 views

### generalizing Ben-Or et al's two-prover bit commitment scheme beyond bits

In "Multi-Prover Interactive Proofs: How to Remove Intractability Assumptions" by Ben-Or, Goldwasser, Kilian, and Wigderson, the authors introduce a bit commitment protocol as a subroutine to their ...
326 views

### Learning with (Signed) Errors

$\underline{\bf Background}$ In 2005, Regev [1] introduced the Learning with Errors (LWE) problem, a generalization of the Learning Parity with Error problem. The assumption of this problem's ...
628 views

### Rigorous proof that a random function and a random permutation cannot be distinguished in polynomial time

I have a background in number theory and I'm trying to learn how to reason rigorously about algorithms. I'm reading chapter 2 of Katz and Lindell's Introduction to Modern Cryptography. Show that no ...
169 views

179 views

### Contract preservation using grammars

I am exploring using annotated grammars to formalize and enforce parts of contracts between nodes in a distributed application. I've found a number of articles on languages for specifying fairly ...
1k views

### Best method of Error Correction in Quantum Key Distribution

As far as I can tell, almost all implementations of QKD use Brassard and Salvail's CASCADE algorithm for error correction. Is this really the best known method of correcting errors in a shared ...
253 views

### How much bigger does a precomputed lookup table get when salt is added?

I am trying to wrap my head around the benefits of salt in cryptography. http://en.wikipedia.org/wiki/Salt_(cryptography) I understand that adding salt makes it harder to precompute a table. But ...
81 views

### Rabins Signature Implementation [closed]

I am searching for an Implementation for Rabins Algorithm in any language. I've searched but haven't got it anywhere. does anybody have a link ?
83 views

### Jointly Establishing a Shared Random String for NIZK proofs of knowledge

If OWFs exist, then a Shared Random String for NIZK proofs (of membership) can be established by: verifier commits a random string of the same length using statistically hiding commitment prover ...
377 views

### Can every digital file have a unique fingerprint?

Disclaimer: I am not a CS person but this question is more philosophical in the sense i could not get a good enough answer ANYWHERE ELSE as to how systems such as Youtube content id work. In Youtube ...
218 views

### Pseudorandom increasing sequence

I am looking for a way to generate an increasing sequence of integers $(x_i)$ such that the sequence of differences $(x_{i+1}-x_i)$ is pseudorandom (in any common way of defining pseudorandomness). It ...
165 views

### “forward-secure” zero knowledge protocols

Has anything been done on the modification of the zero knowledge condition where the distinguisher has access to the witness used by the prover and the random bits used by the algorithm that ...
761 views

### Secure multiparty computation of number of 1s times number of 0s in a shared string

Suppose there are $N>2$ parties $p_j$, each with a bit $b_j\in{\{0,1\}}$. I want to compute the multiplication of number of ones times that of zeros, that is, $R=(\sum{b_j})\times(N-\sum{b_j})$. ...
176 views

203 views

### Can Canetti's composition theorem be used to prove composition of Nash equilibrium?

This might be a very simple doubt, but I am not able to prove or disprove it rigorously. Canetti's work on "Security and Composition of Multiparty Cryptographic Protocols: JoC 2000" allows us to ...
4k views

### Arguments for existence of one-way functions

I have read in several papers that the existence of one-way functions is widely believed. Can someone shed light on why this is the case? What arguments do we have for supporting the existence of one-...
181 views

### Digital steganography re-encoding resistance

I'm curious to know if any papers exist on the ability of steganographically-altered image data to retain its integrity after it has been re-encoded into a different format (e.g., from PNG to JPEG). ...
2k views

### The significance of NP-Hard Problems in Cryptography

I didn't refer any literature but thought this was ideal to get views from people here.. Assuming that P=NP is proved would cryptography(only provable security) be impossible? Since the adversary can ...
360 views

### How is it proven that Key Exchange implies OWFs?

Page 38 says that Key Exchange implies the existence of one-way functions. When I try to work out the proof myself, I get that in the hypothetical case where there is Key Exchange but no one-way ...
240 views

### A protocol for honest compromise

This question did not originate in my research, but I think it's interesting. It is somewhat underspecified. I'd be interested in an example in any particular case. We have $n$ parties that between ...
260 views

### On the Proof Technique of Boneh-Lynn-Shacham Gap Signatures

In paper "Short signatures from the Weil pairing" by Boneh, Lynn and Shacham, I was going through the security proof just like any other signature. But the technique used in this paper is quite ...
2k views

### Why SHA-224 and SHA-256 use different initial values?

Wikipedia - SHA-2 says SHA-224 is identical to SHA-256, except that: the initial variable values h0 through h7 are different, and the output is constructed by omitting h7. RFC3874 - A ...