Theoretical aspects of cryptography and information security.

learn more… | top users | synonyms (1)

7
votes
0answers
134 views

Can a random oracle change which TFNP problems are strongly hard-on-average?

I've been thinking about the following question at various times since I saw this question on Cryptography. Question Let $R$ be a TFNP relation. ​ Can a random oracle help P/poly to break $R$ ...
3
votes
1answer
77 views

Is a “complete” cipher possible?

Is a "complete" symmetric cipher possible? By this I mean a symmetric cipher that is provably secure under the assumption that a secure symmetric cipher exists.
4
votes
1answer
54 views

Is it possible to MAC a quantum state with a classical key under reasonable assumption?

Assume that classical one-way functions secure against quantum adversaries exist. Is it possible, given a quantum state $Q$ and classical secret key $k$, produce a quantum state $AuthQ$ such that: ...
2
votes
1answer
75 views

Is it possible to encrypt quantum states under reasonable assumptions?

Is it possible to encrypt a quantum state, such that a $BQP$ attacker who does not know the secret key cannot obtain any information about the original state, but a $BQP$ decryptor with the key can ...
13
votes
0answers
136 views

Does Factoring have a Statistical Zero Knowledge Proof?

The title should be pretty self-explanatory, but to be more precise, consider the decision version of factoring, which is given input $(x,k)$, where $x$ and $k$ are binary encodings of integers, to ...
1
vote
0answers
67 views

Quantum algorithms for generalizations of determinants

There are a wide variety of determent-like constructions. Some like the permanent or immanents are variations on the ordinary determinant for matrices over fields or commutative rings. Some like ...
7
votes
2answers
215 views

How to find a non-zero point of a non-zero polynomial of low degree?

Given a circuit that computes a polynomial $P(x_1 \dots x_n)$ of low formal degree over some large field $\mathbb{F}$. Moreover, given a point $X \in \mathbb{F}^n$, such that $P(X) \neq 0$. Can one ...
6
votes
1answer
159 views

Quantum Hardness of Approximating Lattice Problems

A common claim in lattice-based cryptography is that cryptosystems based on the Learning with Errors ($\mathsf{LWE}$) problem are hard to break (for a per-system definition of "break") for quantum ...
17
votes
0answers
241 views

Quantum Hardness of Finding Nash Equilibria

This question is inspired by the recent, beautiful work On the Cryptographic Hardness of Finding a Nash Equilibrium by Bitansky, Paneth, and Rosen. Their main result is that the existence of ...
5
votes
2answers
207 views

Alternatives to Diffie Hellman

Assume that Discrete logarithms can be solved in linear time over any group (hence factorization is also trivial by a result of Eric Bach), is there any other candidate public key exchange problem ...
15
votes
1answer
335 views

Complexity classes for proofs of knowledge

Prompted by a question Greg Kuperberg asked me, I'm wondering if there are any papers that define and study complexity classes of languages admitting various kinds of proofs of knowledge. Classes ...
8
votes
0answers
197 views

Knot Recognition as a Proof of Work System

Currently bitcoin has a proof of work (PoW) system using SHA256. Other hash functions use a proof of work system use graphs, partial hash function inversion. Is it possible to use a Decision problem ...
1
vote
0answers
97 views

Extractor with somewhat corrupted seeds

In conditional min-entropy extractor, there is a joint distribution $(X,Y)$ such that if the average min-entropy (for some appropriate notion of it) ${\rm H}_\infty(X|Y)$ is large, then ${\rm Ext}(X, ...
2
votes
2answers
104 views

Factoring semiprimes whose factors very close to a power of two

Are there any factorization algorithms that run well on numbers $N = pq$ where $p,q$ are prime and $p = 2^b - k_p, q = 2^b - k_q$ for very small $k_p,k_q$? What about $p = 2^b + k_p, q = 2^b + k_q$ ...
2
votes
0answers
65 views

Claw finding using quantum walk: superposition for Szegedy's framework

Within Claw Finding Algorithms Using Quantum Walk there is the subroutine $claw_{detect}$ described. As in above paper: Let $J_f(N, l)$ and $J_G(M, m)$ be Johnson graphs. Let $F$ and $G$ be vertices ...
0
votes
0answers
28 views

Claw finding algorithm transformation

In Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies by DeFeo, Jao and Plut (PDF) there is a quantum-resistant cryptosystem defined. On page 17/18 is a quantum attack ...
1
vote
2answers
177 views

Information-theoretic Diffie-Hellman

The following non-standard description of Diffie-Hellman is entirely my own, by which I mean that I came up with it having not read about it anywhere else beforehand. In Diffie-Hellman Alice and Bob ...
9
votes
1answer
226 views

Can we construct a k-wise independent permutation on [n] using only constant time and space?

Let $k>0$ be a fixed constant. Given an integer $n$, we want to construct a permutation $\sigma \in S_n$ such that: The construction uses constant time and space (i.e. preprocessing takes ...
5
votes
1answer
141 views

Simple candidates for pseudorandom permutations?

Even though it is not known whether one-way functions exist, there are several candidate functions used in practice for cryptographic applications that are efficiently computable but are conjectured ...
0
votes
1answer
66 views

Question on cryptographic advantage

In Provably Secure Steganography by Hopper, et al, we have the following definition Cryptographic notions Let $F:\{0,1\}^k \times \{0,1\}^L \rightarrow \{0,1\}^l$ denote a family of functions. Let ...
4
votes
1answer
299 views

Introductions to steganography from an information-theoretic standpoint

Can I get some introductory references for steganography from an information-theoretic standpoint? I recently listened to a talk on it, and the speaker said that he knew of no good introductions to ...
2
votes
1answer
129 views

Cryptography with very small keys

Is anything known about doing cryptography with very small keys? In particular, is there any theory involving cryptosystems (based on whatever assumption you want) that can encrypt messages of length ...
3
votes
0answers
70 views

One kind of dependence relation between a pair of random variables

I have been working on privacy and come across a neat problem. Suppose two random variables $X$ and $Y$, over finite alphabets $\mathcal{X}$ and $\mathcal{Y}$, are given with joint distribution ...
4
votes
1answer
156 views

Cryptographic systems that don't leak linear combinations of encrypted bits

Various encryption schemes would be considered broken if an adversary could have a non-negligible edge in predicting the first (or any) bit of an encrypted message. I am looking for a slightly ...
2
votes
2answers
151 views

Reference on cryptography methods

I'm looking for a good reference, possibly a survey, on the different types of cryptography methods. As far as I understand, the security of a cryptographic method depends on some hardness ...
1
vote
1answer
105 views

Is it possible to encrypt something in such a way that it can be decrypted by two different keys?

I'm a lowly web dev / programmer of 10 years who's never tried to wrap his brain around the high concept stuff, so apologies is this is a stupid question (or if it belongs in ...
11
votes
0answers
195 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 ...
9
votes
2answers
406 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
66 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 ...
3
votes
1answer
110 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
317 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 ...
5
votes
1answer
84 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
78 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
77 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
1answer
93 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
220 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
126 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
79 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
87 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
196 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
157 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
78 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
535 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
40 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
435 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 ...
7
votes
1answer
444 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 ...
-1
votes
1answer
139 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
245 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
165 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 ...