Theoretical aspects of cryptography and information security.

learn more… | top users | synonyms (1)

0
votes
0answers
20 views

deterministic randomness extractor and privacy

Suppose $X$ is a message which takes values on the set $\{x_1, \dots, x_m\}$ with probability distribution $P_X$. We transmit the message $X$ over the channel $P_{Y|X}$ which outputs $Y$ taking ...
14
votes
2answers
170 views

On the status of learnability inside $\mathsf{TC}^0$

I'm trying to understand the complexity of functions expressible via threshold gates and this led me to $\mathsf{TC}^0$. In particular, I'm interested what's currently known about learning inside ...
3
votes
3answers
110 views

On proving it is hard to compute $g^{rb}$ with knowledge of $r$, given $g, g^a, g^{ab}$

I am trying to prove the following Given $g, g^a, g^{ab}$ it is hard to compute $r, g^r, g^{rb}$, for some arbitrarily chosen value of $r$ where $g ∈ \mathbb{G}, \mathbb{G}$ is a cyclic group ...
4
votes
0answers
46 views

Inf-entropy rate and min-entropy

I am reading the paper "Generating random bits from an arbitrary source: fundamental limits" by Vembu and Verdu. This paper is written in the language of information theory, however, I need to ...
3
votes
1answer
67 views

Is Square DH hard in Bilinear Groups?

Let $G$ be a group, $g ∈_R G, x ∈_R Z_q$, and $e: G \times G \rightarrow G_T$ be a bilinear paring. Then, given $g, g^x$, is it still hard to compute $g^{x^2}$? 1. In other words is Square ...
7
votes
1answer
141 views

Secure MAC when the adversary has a verification oracle

A message authentication code (MAC) is defined by a triple of efficient algorithms $(\mathsf{Gen}, \mathsf{MAC}, \mathsf{Verif})$, which satisfy the following (the definition is taken from section 4.3 ...
2
votes
0answers
105 views

Is “best-possible obfuscation” really what its name indicates?

The paper On Best-Possible Obfuscation defines what is calls "best-possible obfuscation", and proves (propositions 3.4 and 3.5) that efficient best-possible obfuscators are exactly efficient ...
0
votes
1answer
59 views

Is there an efficient construction for a trilinear pairing that has been used in theory or practice

A trilinear pairing is defined a function $e:G_1^3 \rightarrow G_2$, such that it satisfies the property $e(k_1^a, k_2^b, k_3^c) = e(k_1,k_2,k_3)^{abc}$ In general I am trying to solve the following ...
-3
votes
1answer
242 views

What is the most efficient algorithm to generate a sequence of prime numbers?

I know about algorithms like Sieve of Eratosthenes and Sieve of Atkin for generating prime numbers. I would like to know what is the most efficient known algorithm to generate the sequence of $k$ ...
0
votes
0answers
31 views

Reference Request: Surveys on attacks on security schemes

I am new to provable security and am working on cryptanalysis of a certificate free signature scheme. Unfortunately, I don't have much knowledge about finding attacks on schemes. It would be very ...
0
votes
0answers
112 views

How to determine if a function is negligible?

In cryptography (and probably in many other areas) there is a huge usage of negligible functions when proving theorems. Although I know what is a negligible function, every time I encounter a ...
5
votes
2answers
297 views

Public-key encryption without the assumption that $P \neq NP$

I'm not talking about the RSA, El-gamal, nor any specific encryption scheme. Rather, my question, as related to this and this threads, is why the idea of Public-Key encryption scheme cannot be secure ...
22
votes
3answers
2k views

Cryptography without assumptions — seeking an overview

Suppose $P = NP$ and a fast linear-time algorithm for SAT appears tomorrow. Suddenly RSA is insecure, much of our modern communication system is broken, and we need to reconsider how to keep secrets ...
0
votes
0answers
60 views

Is there a stand-alone statistical ZK argument with concurrent knowledge extraction?

Is any known construction for an interactive argument of knowledge that is stand-alone statistical zero-knowledge, and allows concurrent knowledge extraction? This is a weakening of my previous ...
6
votes
0answers
180 views

Implication of Bell test loopholes on Vazirani-Vidick random sequence generation scheme

I am trying to imagine what would be the implications of the loopholes on Bell test on the random sequence generation scheme proposed by Vazirani and Vidick (VV protocol) in the paper titled ...
1
vote
3answers
138 views

In a cryptosystem, why does the message space need to be finite?

I am learning cryptography through Douglas Stinson's book: Cryptography -- Theory and Practice (3rd ed.). The first definition in the text is ...
3
votes
1answer
135 views

How to properly define a zero-knowledge proof system with oracle access

An $IP$ system $(P,V)$ is zero-knowledge (ZK) for some language $L$ if for every probabilistic polynomial-time verifer $V^*$ there exists a probabilistic polynomial-time algorithm $S$ for every $x\in ...
3
votes
0answers
46 views

one-way functions vs. secret-coin CRHFs

Is there any paper which can be used to show that there can be no relativizing construction of a secret-coin Collision-Resistant Hash Family from a one-way function and unlike this paper, does not ...
3
votes
3answers
247 views

Zero knowledge verification of an encryption protocol

This seems like a straightforward application of zero knowledge techniques, but an answer eludes me. Alice and Bob claim to have devised an encryption scheme: specifically, they claim to possess ...
1
vote
1answer
41 views

A theorem regarding statistically-hiding commitment schemes

Let $C_n$ be a non-interactive statistically-hiding commitment scheme, able to commit to an $n$-bit string. To commit to $m \in \{0,1\}^n$, the sender picks a random $r$ (of proper length), and sends ...
2
votes
0answers
98 views

non-malleable commitment and security parameters

Although it is not clear, it appears that definition 5 of this paper, page 10 of this paper, and page 6 of this paper, each assume that the honest parties will all use the same security parameter. ...
2
votes
1answer
139 views

Can decoying provide security against traffic analysis?

Eve is an intelligence agency with the capability to scan all cleartext communications and do traffic analysis against encrypted communications. There are n Alices, who each want to communicate ...
3
votes
3answers
278 views

A public key cryptographic technique usable without aid of computer

I wondered if there is any known algorithm for secure messaging without pre-shared keys (i.e. public key cryptography) that is practical to use without the aid of a computer? Obviously I would not ...
2
votes
1answer
90 views

Non-invertibility of RSA for two users

In chapter 8 (page 288) of the "Handbook of Applied Cryptography," the authors describe an attack against RSA with small exponent. Let there be 3 parties with independent RSA public keys $(e_1,n_1)$, ...
4
votes
0answers
102 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
84 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
70 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 ...
6
votes
1answer
180 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 ...
0
votes
0answers
62 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
219 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
87 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 \: : \: ...
10
votes
1answer
557 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 ...
11
votes
2answers
370 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
128 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
153 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
228 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 ...
7
votes
1answer
295 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
1answer
338 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
177 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
357 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
294 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 ...
10
votes
1answer
209 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
439 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
88 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 ...
16
votes
3answers
337 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
80 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
200 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
162 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
167 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
70 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 ...