Questions tagged [cr.crypto-security]

Theoretical aspects of cryptography and information security.

Filter by
Sorted by
Tagged with
5
votes
0answers
69 views

Chosen message attack on unhashed GGH signatures?

Background: I've been reading GGH's Public-Key Cryptosystems from Lattice Reduction Problems, and have a question about a remark the authors make: "It is important to remark at the outset, that ...
33
votes
5answers
4k views

Fast Reduction from RSA to SAT

Scott Aaronson's blog post today gave a list of interesting open problems/tasks in complexity. One in particular caught my attention: Build a public library of 3SAT instances, with as few variables ...
22
votes
2answers
817 views

PPAD and Quantum

Today in New York and all over the world Christos Papadimitriou's birthday is celebrated. This is a good opportunity to ask about the relations between Christos' complexity class PPAD (and his other ...
39
votes
3answers
3k views

Is the integer factorization problem harder than RSA factorization: $n = pq$?

This is a cross-post from math.stackexchange. Let FACT denote the integer factoring problem: given $n \in \mathbb{N},$ find primes $p_i \in \mathbb{N},$ and integers $e_i \in \mathbb{N},$ such that $...
0
votes
2answers
873 views

Password checking algorithm

Usually to check password validity we used to create over given password it hash value and compare it with stored one. So password protection relies on strength of hashing function. Could it be used ...
9
votes
2answers
331 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 ...
2
votes
0answers
82 views

Quantum security of cryptosystems

One of the main candidates for PQ cryptography is code based cryptography (other than lattice based). The Niederreiter cryptosystem based on goppa codes is shown to be resistant to hidden subgroup ...
1
vote
0answers
51 views

Underlying codes in Niederreiter cryptosystems

Niederreiter cryptosystem is usually described by a parity check matrix $H$ over $\mathbb{F}_{2^n}$. The minimum distance $d$ is given by $d= min\lbrace k \text{ such that there are $k$ linearly ...
4
votes
2answers
168 views

If I know pretty well '(a,b)', I know pretty well 'a', or 'b', or 'a xor b'

I've a quite simple problem: let's imagine I have a couple of bits $(a,b) \in \{0,1\}^2$ sampled uniformly at random. Then, I give a function of these bits $f(a,b)$ (it can be any function, including ...
2
votes
1answer
165 views

Would an NP-complete public key cryptosystem imply NP=co-NP?

Would the existence of an NP-complete (or co-NP-complete) public key signature cryptosystem imply that NP = co-NP? My specialty is definitely not theoretical computer science, so this is somewhat of ...
11
votes
2answers
449 views

straight-line simulatability

Does any body know any good reference for meaning of straight-line simulatability? I am currently deep into Universal Composability (UC) framework of Canetti but I can't find any good reference for ...
1
vote
1answer
86 views

Cryptography protocols using graph problem instances

I personally am only aware of basic examples of public key cryptography and I haven't studied cryptography yet. I'm curious if there are circumstances in cryptography where using problem instances ...
11
votes
1answer
362 views

State of research on SHA-1 Collision Attacks

SHA-1 security has been discussed since an algorithm for finding collisions was first published at CRYPTO 2004 and has been subsequently improved. Wikipedia lists a couple of references, however it ...
1
vote
2answers
210 views

Which cryptographic protocols are secure against quantum computer attacks?

Are there any cryptosystems that we know that would be secure against an attack by a quantum computer? Are there problems which are known or suspected to be hard for quantum computers, and can these ...
10
votes
1answer
263 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, ...
8
votes
2answers
160 views

What is the state of the art in online voting?

Is there a cryptographic protocol which, at least in theory (and under standard cryptographic assumptions) enables people to securely vote from their homes? I could see how the various problems might ...
16
votes
1answer
1k views

Password hashing using NP complete problems

Commonly used password hashing algorithms work like this today: Salt the password and feed it into a KDF. For example, using PBKDF2-HMAC-SHA1, the password hashing process is ...
5
votes
0answers
140 views

How hard is it to generate a set of relatively prime numbers between two given bounds?

Informal Question How hard is it to generate a set of relatively prime numbers between two given bounds? Decision Problem Given $a$, $b$, and $k \in \mathbb{N}$. Does there exist a set $S \...
23
votes
1answer
2k views

Knot Recognition as a Proof of Work

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 ...
20
votes
2answers
1k views

Can any computational challenge be transformed to proof-of-work?

The seemingly pointlessness of cryptocurrency mining raised the question of useful alternatives, see these questions on Bitcoin, CST, MO. I wonder whether there exists an algorithm that can convert ...
18
votes
2answers
508 views

Is it possible to encrypt a CNF?

Is it possible to convert a CNF $\mathcal C$ into another CNF $\Psi(\mathcal C)$ such that The function $\Psi$ can be computed in polynomial time from some secret random parameter $r$. $\Psi(\mathcal ...
7
votes
3answers
534 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
97 views

Can entropicly secure encryption algorithms be used on low-entropy messages by adding noise

There exist information-theoretic notions of security like Shannon's "perfect security" that one-time pads exhibit. All methods which achieve perfect security will require long keys, however. If we ...
2
votes
1answer
161 views

Is there a fast algorithm to quickly evaluate $a^{b^c}$ mod $n$?

I need to quickly evaluate $a^{b^c} \mod n$ where $c$ is pretty big. Using the usual repeated squaring trick, this can be performed in $O(\log(b^c)) = O(c)$ time. In my problem, $c$ is huge, (say, $&...
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:...
7
votes
1answer
274 views

Why is the security of lattice cryptosystems not provable from $P \neq NP$?

My understanding is that the Shortest Vector Problem ($\text{SVP}$) is $\text{NP}$-hard. Therefore, $\text{LWE}$ is also $\text{NP}$-hard. But $\text{LWE}$ is hard on average if it is hard in the ...
0
votes
1answer
81 views

Problems equivalent to the existence of secure cryptosystems? [closed]

What are some necessary and sufficient conditions for the existence of following? Symmetric encryption (defined here as satisfying $\text{IND-CPA}$ and $\text{INT_CTXT}$) Asymmetric encryption ...
2
votes
1answer
80 views

“Security Against Covert Adversaries” question

I was reading the paper Security Against Covert Adversaries: Efficient Protocols for Realistic Adversaries by Aumann and Lindell, and had some questions with the protocol for covert OT given errorless ...
5
votes
0answers
74 views

Is [2-party d3-rolling with maximum probability 1/2] known to imply one-way functions?

Most things in complexity-based cryptography (for examples, see page 4) are known to imply the existence of one-way functions, especially after this paper proved that implication for weak coin-...
12
votes
3answers
3k views

How can DES have 6x4 S-Boxes and still be reversible?

Wouldn't data be lost when mapping 6-bit values to 4-bit values in DES's S-Boxes? If so, how can we reverse it so the correct output appears?
6
votes
1answer
365 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 ...
-3
votes
1answer
230 views

The factoring problem reduces to order finding or is it the other way around? [closed]

initially i was not at all equipped in theoretical computer science and knew only basics of number of theory. I started working from scratch on the age old problem of primality testing which led me to ...
3
votes
4answers
239 views

Is a theoretically secure key exchange possible?

During a discussion I was wondering if it would be possible to design a theoretically secure key exchange. In other words: If it is possible to design a key exchange (like Diffie–Hellman) where the ...
9
votes
1answer
276 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$ ...
17
votes
0answers
313 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 ...
2
votes
1answer
102 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.
2
votes
1answer
112 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 ...
0
votes
1answer
121 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 ...
4
votes
1answer
72 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: ...
1
vote
0answers
139 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 ...
6
votes
2answers
266 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 ...
7
votes
1answer
287 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 ...
36
votes
3answers
3k views

Consequences of Factoring being in P?

Factoring is not known to be NP-complete. This question asked for consequences of Factoring being NP-complete. Curiously, no one asked for consequences of Factoring being in P (maybe because such a ...
17
votes
0answers
483 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 ...
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 ...
5
votes
2answers
700 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 ...
19
votes
1answer
805 views

Is there a better than linear lower bound for factoring and discrete log?

Are there any references that provide details about circuit lower bounds for specific hard problems arising in cryptography such as integer factoring, prime/composite discrete logarithm problem and ...
16
votes
1answer
439 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 ...
2
votes
0answers
99 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 ...
1
vote
0answers
106 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, ...

1
2 3 4 5 6