Questions tagged [cr.crypto-security]

Theoretical aspects of cryptography and information security.

48 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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 ...
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 ...
14
votes
0answers
236 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 ...
14
votes
0answers
292 views

Pseudorandom functions in ACC^0?

In the lower bound result by Ryan Williams (Non-uniform $\mathsf{ACC}$ circuit lower bounds), there is a mention of "little evidence that Pseudorandom function generators exist in $\mathsf{ACC}^0$. Is ...
11
votes
0answers
183 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 ...
9
votes
0answers
176 views

Pseudorandom object yielding shrinkage in $\ell_p$ norm?

Extractors have the following property: For a random variable $X$ of min-entropy $k$ and a seed $Y$, denote the output of an $(k,\epsilon)$-extractor by $\mathrm{Ext}(X,Y)$. Then $\|\mathrm{Ext}(X,Y)-...
9
votes
0answers
499 views

VNP = VP versus complexity classes in Arithmetic Geometry

What is the implication of $VNP = VP$ to cryptography schemes such as Elliptic curve/Abelian Variety/Arithmetic Geometry based cryptography? Are there any papers or books that talk about sophisticated ...
9
votes
1answer
439 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 ...
8
votes
0answers
629 views

A generalisation of one-wayness

$\mathbf{NP}$-complete problems are worst-case hard. Their average-case counterpart are one-way functions. Is there an analogous one-wayness notion for $\mathbf{coNP}$-complete problems? More ...
7
votes
0answers
262 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 '...
7
votes
0answers
183 views

Oracle sparating FIP for bounded-depth Frege from FIP for Frege (and hardness conditions on DDH)

Is there an oracle such that in the relativized world, bd-Frege (bounded depth Frege propositional proof system) has FIP (feasible interpolation property) but Frege does not have FIP? Such an oracle ...
7
votes
0answers
199 views

Equivocal primitives in practice

To prove a protocol secure in the computational model, one can use game-based approach or the simulation approach (I just assume these two models for simplicity). In the game based approach, the ...
6
votes
0answers
154 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 ...
6
votes
0answers
207 views

What is the best fitness function for detecting natural language?

First, let me apologise, as this question is far from my area of expertise, but is related to a side interest (read hobby), and so this question might be very naive. This may even be off-topic for the ...
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 ...
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 \...
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-...
5
votes
0answers
73 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 ...
5
votes
0answers
206 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$, ...
5
votes
0answers
93 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 \: : \: \{0\hspace{....
4
votes
0answers
114 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 ...
4
votes
0answers
142 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 in})...
4
votes
0answers
267 views

A approximation version of the Goldreich-Levin Theorem

A little introduction The Goldreich-Levin Theorem says that let $f$ a one-way function and set $f'(x,r)=(f(x),r)$ where $|r|=|x|$ then $\langle x, r \rangle = \sum_{i}x_ir_i \mod 2$ is an hard-core ...
3
votes
0answers
73 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 $P_{...
3
votes
0answers
64 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
0answers
170 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 ...
3
votes
0answers
74 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 $\...
3
votes
0answers
186 views

Simulator Efficiency versus Algorithm Efficiency

I have a question about the simulator efficiency. I am reading a group key exchange protocol which is UC-Secure (the security is proven on universal composability framework of Canetti). The proof uses ...
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 ...
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 ...
2
votes
0answers
223 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 ...
2
votes
0answers
107 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
0answers
114 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 $\omega\left(\log^...
2
votes
0answers
139 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 ...
2
votes
0answers
203 views

Can Canetti's composition theorem be used to prove composition of Nash equilibrium?

This might be a very simple doubt, but I am not able to prove or disprove it rigorously. Canetti's work on "Security and Composition of Multiparty Cryptographic Protocols: JoC 2000" allows us to ...
2
votes
0answers
120 views

Security of IBE schemes

Suppose we have an ID-based encryption (IBE) (Setup, Extract, Enc, Dec) scheme which is IND-ID-CPA (resp IND-ID-CCA) secure, and we want to construct threshold version of this scheme. My question is: ...
2
votes
0answers
131 views

What is the notion behind proxy re-signatures?

Digital signatures allow an entity to sign a digital message so that it is easy to verify the signature, but it is hard to forge a valid signature on a given message. It is sometimes useful to be ...
2
votes
0answers
267 views

Some problems involving polynomials of public and private variables over GF(2).

Suppose there are a set of low degree (less than some degree $z$) polynomials $P_0, P_1, ..., P_k$ each of which is defined over two types of variables, red variables ${v_r}_0, {v_r}_1, ..., {v_r}_n$ ...
2
votes
1answer
149 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 ...
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 ...
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 ...
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
vote
0answers
276 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 ...
1
vote
0answers
333 views

How kerberos key distribution protocol prevents replay attack ?

How kerberos key distribution protocol prevents replay attack ?
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
1k 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 ...
0
votes
0answers
81 views

Security of threshold blind signatures

To prove unforgeability of threshold signatures TSig =(TKeyGen, TSign, Verify), it is sufficient to prove that the underlying signature scheme Sig=(KeyGen, Sign, Verify) is secure and TSig is ...
0
votes
0answers
86 views

What is the meaning Partitioned Signatures?

Context: Boneh & Boyen devised a transformation for these class of signatures which increases the security to stronger notion of unforgeability. It would be nice if it is an example. Thanks! ...