Theoretical aspects of cryptography and information security.

learn more… | top users | synonyms (1)

11
votes
0answers
159 views

Is it possible to make trapdoor board games?

Motivated partly by this MO question, I am wondering if it's possible to design a board game where there is a simple winning strategy but it's hard to find. For example, the game of picking a random ...
-2
votes
0answers
51 views

Are all cryptography problems reducible to factoring?

Are all cryptography problems reducible to factoring? Would the implementation of Shor's algorithm break cryptography? Or do we have another thing to move onto if quantum computers become available?
9
votes
2answers
263 views

Why does most cryptography depend on large prime number pairs, as opposed to other problems?

Most current cryptography methods depend on the difficulty of factoring numbers that are the product of two large prime numbers. As I understand it, that is difficult only as long as the method used ...
5
votes
0answers
49 views

Understanding the weak-OWF exists -> OWF exists proof

This is a proof that I've gone back to many times over the last few years and while I can read it and easily verify the steps, it seems like it's a proof, where I will always essentially forget the ...
2
votes
0answers
43 views

Efficient Shamir secret sharing reconstruction

Shamir's secret sharing scheme is a well known way to convert a secret into a polynomial and distribute points in this polynomial. Some of these points can then be regrouped to reconstruct the ...
5
votes
3answers
232 views

Candidates for One-Way Function

Why are the candidates for one-way functions so few? Today, almost all candidates are based on elementary mathematics, except Goldreich's candidate 2000 and ... (?!). Why one can not generate ...
4
votes
1answer
68 views

Commitment schemes with verification in NC0

Is there any secure cryptographic commitment scheme, where the verification routine can be implemented in $NC^0$? If so, what is the minimum possible depth of the circuit for verification? Applebaum ...
2
votes
1answer
67 views

Sufficient Statistics of $X$ from $Y$

I am reading the paper New Monotone and Lower Bounds in Unconditional Two Party Computation by Wolf and Wullschleger. In Definition 2 on the third page, they define $f(x):=P_{Y|X}(\cdot|x)$ and they ...
5
votes
1answer
52 views

Are there established cryptographic hardness assumptions for chaotic systems?

I found this paper of Cuomo and Oppenheim, where they use a Lorenz system to define an encryption scheme for signals. There is also this blog post describing and implementing the technique. The ...
0
votes
0answers
57 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
195 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
121 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
60 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
72 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
148 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
119 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
66 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
293 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
36 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
244 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
326 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 ...
23
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
64 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 ...
7
votes
0answers
203 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
150 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
139 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
50 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
260 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
44 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
99 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
140 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
285 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
92 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)$, ...
5
votes
0answers
116 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
89 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
72 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
191 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 ...
3
votes
1answer
225 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
89 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
569 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
380 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
131 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
160 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
241 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
301 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
388 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
251 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
361 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
303 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
242 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 ...