Theoretical aspects of cryptography and information security.
4
votes
0answers
61 views
Ergodic Theory and Hash Functions
I was thinking about the old question regarding the existence of fixed points in hash functions (for instance, if we restrict the domain of MD5 to $S = \{0, 1\}^{128}$, making it a mapping $S \to S$, ...
2
votes
0answers
51 views
concurrent non-malleable *statistical* zero knowledge
According to Huijia Lin and
Rafael Pass's "Concurrent Non-Malleable Zero Knowledge with
Adaptive Inputs" paper:
if collision-resistant hash functions exist, then
"there exists a ...
2
votes
0answers
41 views
Are there efficient black-box constructions of sigma-protocols for SAT?
Is there a known black-box construction for the following implication?
non-interactive string commitment that stretches additively by an
amount which does not depend on the string being ...
-3
votes
0answers
44 views
6
votes
1answer
142 views
Consequences of OWFs for Complexity
It it well-known that the existence of one-way functions is necessary and sufficient for much of cryptography (digital signatures, pseudorandom generators, private-key encryption, etc.). My question ...
1
vote
0answers
44 views
mututal data authentication from a short authentication string
For all $n$, $\:$range($\hspace{.005 in}n$)$\:$ is the set of non-negative integers that are less than $n$.
What is known about how many rounds of communication are
needed for mutual data ...
3
votes
1answer
177 views
How to homomorphically and “efficiently” evaluate $$(a_1 + b_1) \cdot c_1 + (a_2 + b_2) \cdot c_2 + \ldots + (a_n + b_n) \cdot c_n$$
Can i evaluate a formula $(a_i + b_i) \cdot c_i$ if i have the encryption of $a_i,b_i,c_i$ respectively using a homomorphic encryption scheme that supports multiplications and additions, supposing ...
5
votes
0answers
79 views
How short can reversible representations of the n-bit primes be?
For $\: 1 < n \:$ and $\: n^{o(1)} < \sigma \leq n \:$, $\:$ how small can $L$ be for there to be for there to be an
efficiently computable (deterministic) function $\;\; f \: : \: ...
7
votes
1answer
302 views
Is bitcoin cryptographically secure
I am trying to understand the bitcoin protocol in the context of computational cryptographic security. The question is a reference request to foundations of cryptography articles on bitcoin.
My first ...
11
votes
2answers
325 views
On fooling $AC^0$
I have a few questions regarding fooling constant depth circuits.
It's known that $\log^{O(d)}(n)$-wise independence is necessary to fool $AC^0$ circuits of depth $d$, where $n$ is the size of the ...
1
vote
1answer
99 views
A reduction proof of SK-security for the Needham-Schroeder-Lowe protocol
The Needham-Schroeder-Lowe protocol works as follows between the initiator I and responder R:
$I \longrightarrow R : \text{Enc}_{pk_R}(r_I, I)$
$R \longrightarrow I : \text{Enc}_{pk_I}(r_I, r_R, R)$
...
7
votes
0answers
138 views
Is there a candidate for a post-quantum one-way group action?
Is there a known family of group actions with a designated element
in the set that is being acted on, where it is known how to efficiently
$\:$ sample (essentially uniformly) from the groups, ...
3
votes
1answer
180 views
What are alternatives to the random oracle model for modelling hash functions?
I was looking for more realistic alternatives to the ROM for describing hash functions in theoretical proofs. I came across the common reference string model (where hash functions can be modeled as ...
8
votes
1answer
260 views
How hard is it to learn a linear modular function?
Let $k$ be a fixed number.
Consider the following task $Q$:
We are given a sequence of numbers $(x_0,x_1,\cdots,x_k)$. We know they satisfy $x_{k+1}=f(x_k)$, and $f(x)=(ax+b \mod p) \mod m$ where ...
9
votes
0answers
141 views
(Cryptographic) problems solvable in a polynomial number of arithmetic steps
In the paper from Adi Shamir [1] from 1979 he shows, that factoring can be done in a polynomial number of arithmetic steps. This fact was restated, and thus came to my attention, in the recent paper ...
6
votes
1answer
107 views
The flaw in Bellare-Rogaway (1995) model on authenticated key exchange
Background:
In their 1995 paper, Bellare and Rogaway describe a formal model for authenticated key exchange in a tripartite setting. In this setting, each client has a shared key with a central ...
7
votes
1answer
332 views
Algorithmic Complexity Attacks
I am studying algorithm construction and weaknesses to resource consumption. One vulnerability that really caught my eye was the Apache Range Header DoS Vulnerability. The following quote was taken ...
-2
votes
1answer
264 views
Computational complexities in factoring
[Note: n is a given integer (not the number of its digits)]
I'd like to know how O(sqrt(n)/log(n)) would compare against the computational complexity of the best available algorithms (as well as the ...
9
votes
1answer
150 views
Noisy Parity (LWE) lower bounds/hardness results
Some background:
I'm interested in finding "lesser-known" lower bounds (or hardness results) for the Learning with Errors (LWE) problem, and generalizations thereof like Learning with Errors over ...
4
votes
3answers
197 views
NIZK proofs: Why is the prove function necessary?
In NIZK proofs, the prover can generate its proof for statement $y$ and witness $w$ using
$$\pi \gets \mathrm{Prove}(\sigma,y,w)\text{,}$$
where $\sigma$ is the common reference string. Source: ...
4
votes
0answers
80 views
Strong extractors with reusable seeds
I have convinced myself of the following:
For every $(k,\epsilon^2\hspace{.005 in})$-strong extractor Ext, for every distribution $X$,
if $\;\; k\leq$ $\:H_{\infty}$$(\hspace{.01 in}X\hspace{.015 ...
15
votes
3answers
311 views
What is the motivation behind the definition of pseudorandom in Nisan/Wigderson?
I am reading the classic "Hardness vs Randomness" by Nisan and Wigderson. Let $B=\{0,1\}$, and fix a function $l\colon \mathbb{N} \to \mathbb{N}$. They define a family of functions $G = \{G_n : ...
0
votes
1answer
75 views
How to design a secret sharing scheme for matrix-like positioned participants
How to design a secret sharing scheme where when participants are positioned as a matrix, the minimum group people who can reconstruct the secret are the ones that are in same row or in same column?
5
votes
1answer
194 views
Is there a Boolean formula that is resistant to bias from a polytime adversary?
I am studying Coin Flipping protocols in cryptography, and the complexity of problems related to this.
Here, a question has come to my mind: Does there exist a public coin, coin flipping protocol?. ...
1
vote
0answers
115 views
Is there a better explanation of Hellman's paper on rainbow tables than the paper itself?
I'm reading through Hellman's A Cryptanalytic Time-Memory Trade-off [PDF], and I was wondering if there is code out there that implements this or if there are better explanations of how a password ...
8
votes
1answer
154 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
68 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
101 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
210 views
One Way Boolean Function [closed]
If one way functions exist, what would the truth table of a one way boolean function look like?
6
votes
1answer
169 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$, ...
1
vote
0answers
69 views
Zero-Knowledge from a semi-trusted random beacon and weak timestamping
For this question, assume that one-way functions exist.
The standard zero-knowledge proof system for NP can easily be implemented with a
random beacon and trusted timestamping service instead ...
7
votes
1answer
210 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 ...
10
votes
0answers
140 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 ...
7
votes
0answers
122 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
387 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
158 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 ...
3
votes
0answers
105 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
124 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 ...
24
votes
3answers
966 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
89 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 ...
-2
votes
1answer
247 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 ...
2
votes
0answers
81 views
Is there a formal definition of security for interlock protocols?
I was reading the wiki article on interlock protocols, and thinking about basing the
security of such protocols on concrete assumptions. $\:$ When doing that, I rather quickly
realized that I have ...
3
votes
2answers
360 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 ...
3
votes
2answers
135 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
310 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 ...
16
votes
2answers
701 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
66 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
146 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 ...
11
votes
1answer
118 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 ...
3
votes
2answers
223 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 ...
