Questions tagged [cr.crypto-security]

Theoretical aspects of cryptography and information security.

Filter by
Sorted by
Tagged with
8
votes
1answer
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 (...
1
vote
0answers
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 ...
6
votes
0answers
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 ...
-3
votes
1answer
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?
7
votes
1answer
448 views

Discrete log in GL(2,p)

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$, ...
8
votes
1answer
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 ...
11
votes
0answers
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 ...
9
votes
1answer
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 ...
7
votes
2answers
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 ...
2
votes
1answer
169 views

A mathematical problem in software watermarking

I am wondering if there are any existing works/ideas that are related to the following problem. A solution of this problem can be probably useful in software watermarking. Given, Two sets $\mathcal{...
3
votes
0answers
170 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 ...
4
votes
2answers
554 views

To what extent is anonymity through a Chaum mix compromised by using trusted mixes in the cascade?

As I understand it, a fundamental of Chaum's mix-net is that, absent an external adversary who can analyse traffic on links within the network, no mix can link the source and destination of any ...
27
votes
4answers
1k views

A lottery that you can be convinced that it is fair

(Sorry if this is well known.) I would like to give some item to one of $k$ agents, so that agent $j$ will get the item with probability $p_i$. Is there a cryptographic (or other) tool so that every ...
8
votes
1answer
119 views

Deciding DDH based in partial information

Decisional Diffie–Hellman assumption, or DDH in short, is a famous problem in cryptography. The DDH assumption holds on a cyclic group $(G,*)$ of (prime) order $q$, if for a generator $g \in G$, and ...
-3
votes
1answer
283 views

After implementing a novel encryption algorithm, how would one go about analyzing its security or get help from others in doing so?

Over the years, two novel encryption techniques have come to mind and been implemented as programming libraries that could be integrated into applications. However, how to analyze their security and ...
4
votes
2answers
848 views

Justifying simplifying assumption about message distributions for perfectly secret encryption?

I am currently reviewing my way through Katz and Lindell's Intro to Modern Cryptography, and have found the following question early in the book (exercise 2.6) surprisingly difficult to answer cleanly:...
4
votes
2answers
148 views

Algorithm Design for only Mutual Information Sharing

Bob and Alice each have a bit string they want to keep private. They each want to know what the bitwise AND of their two strings would be without telling the other or anyone else listening to their ...
3
votes
2answers
493 views

Boolean Circuit in a Black Box?

Just had this random idea... but unfortunately I'm not quite versed in complexity theory, so I thought it would be a good idea to ask it here. Let's equip a normal Turing machine with a "black box ...
17
votes
2answers
908 views

Are theoretically sound pseudorandom generators used in practice?

As far as I'm aware, most implementations of pseudorandom number generation in practice use methods such as linear shift feedback registers (LSFRs), or these "Mersenne Twister" algorithms. While they ...
3
votes
0answers
74 views

Are there any “two-sided” strong blenders?

My question is related to explicit extractors and strong blenders. We can define explicit strong blender in a straight forward way. I want to know if there are any known explicit strong blenders $\...
4
votes
1answer
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 ...
14
votes
2answers
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 ...
4
votes
2answers
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 ...
-1
votes
1answer
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 ?
0
votes
1answer
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 ...
-2
votes
1answer
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 ...
2
votes
1answer
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 ...
2
votes
1answer
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 ...
8
votes
2answers
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})$. ...
9
votes
0answers
176 views

Pseudorandom object yielding shrinkage in $\ell_p$ norm?

Extractors have the following property: For a random variable $X$ of min-entropy $k$ and a seed $Y$, denote the output of an $(k,\epsilon)$-extractor by $\mathrm{Ext}(X,Y)$. Then $\|\mathrm{Ext}(X,Y)-...
14
votes
0answers
292 views

Pseudorandom functions in ACC^0?

In the lower bound result by Ryan Williams (Non-uniform $\mathsf{ACC}$ circuit lower bounds), there is a mention of "little evidence that Pseudorandom function generators exist in $\mathsf{ACC}^0$. Is ...
3
votes
1answer
124 views

Choices for the group in Public Key Cryptography

I am only aware of two alternatives for the group used in Diffie-Hellman scheme (and similar ones) where logarithms are conjectured to be hard. Those are $\mathbb{F}_p$ and Elliptic Curves. Are there ...
2
votes
2answers
222 views

Auditable encrypted ledger

Consider a cloud-based accounting system that needs access to aggregate information such as an account's balance but doesn't need access to individual transaction amounts in a ledger. Does there ...
8
votes
2answers
343 views

Using negative results to prove positive results in computability theory

Many results in cryptography depend on impossibility results/conjectures in complexity theory. For example, public-key cryptography using RSA is believed to be possible because of the conjecture about ...
3
votes
1answer
1k views

How to find the exact period of Blum-Blum-Shub random number generator?

I've read the original paper and some related ones. But the best I can find about the period of BBS is that the period is a factor of $λ(λ(M))$, where $λ$ is Carmichael function and $M$ is the product ...
8
votes
2answers
255 views

Is public-key spread-spectrum communication possible?

Alice wants to get a message to a large number of people living under a censorship-happy government, run by Eve. The traditional way of doing this is samizdat, but that process requires each person ...
4
votes
1answer
232 views

Pseudo-Random Function families whose instances have full domain

The GGM construction gives (PRF) pseudo-random function families whose instance's input's are binary strings of a single length. I've convinced myself that one could get a PRF family whose instances ...
10
votes
2answers
436 views

One-Way Functions vs. perfectly binding commitments

If OWFs exist, then statistically binding bit commitment is possible.[1] Is it known that if OWFs exist then perfectly binding bit commitment is possible? If no, is there a known black-box ...
3
votes
2answers
410 views

Factorization Using Statistical Methods

We consider a number $N=AB$ where $A$ and $B$ are primes. Along the whole number-line from $1$ to $N$ we have two success points or target points: $A$ and $B$. If we had millions of target points the ...
3
votes
1answer
182 views

MACing from an arbitrary high min-entropy shared secret

Let $\gamma$ be such that $\, 0<\gamma \,$. $\hspace{.1 in}$ Define $H_{\infty}$ to be min-entropy. If $S_n$ is a shared secret between Alice and Bob such that $\, n^{\frac12+\gamma} \leq H_{\...
2
votes
0answers
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 ...
25
votes
4answers
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-...
8
votes
1answer
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). ...
4
votes
1answer
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 ...
6
votes
1answer
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 ...
4
votes
1answer
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 ...
8
votes
2answers
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 ...
9
votes
1answer
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 ...
2
votes
0answers
120 views

Security of IBE schemes

Suppose we have an ID-based encryption (IBE) (Setup, Extract, Enc, Dec) scheme which is IND-ID-CPA (resp IND-ID-CCA) secure, and we want to construct threshold version of this scheme. My question is: ...
7
votes
2answers
1k views

Zero knowledge proof for value of a hash function

Is there a zero knowledge proof which demonstrates that Peggy knows a value v whose hash-function is w? In my understanding of the general theorems on zero-k there EXISTS such a function if the has-...