Public-Key Cryptography

Statements tagged with the public-key area. This is a generated view, not a home directory – a statement can belong to several areas at once. See all statements for the full index, or the schema for what each column means.

Status	Statement	Tags
	Four-party NIKE, quadratic, Maurer’s model Open. Achieved in Shoup’s generic group model by the source paper (Construction 9, Theorem 10); in Maurer’s model the paper’s own O(n^2) attack sets a ceiling that a construction would meet exactly, and nothing is known about reaching it. 5 open	ggmseparationresearch-opennew-idea (ai)
	Quadratic attack on 3-NIKE, Shoup’s model Open in Shoup’s model. Settled by the source paper in Maurer’s model for every K at least 3, including imperfect correctness; its own three-party Shoup construction achieves only an n^1.5 gap, so the truth for three parties lies somewhere between n^1.5 and n^2. 5 open	ggmlower-boundresearch-opennew-idea (ai)
	RBE needs Ω(log n) updates Open. The number of updates for fixed-update-time schemes with polylogarithmic public parameters is known to lie between Omega(log n / log log n) and O(log n); this statement picks the upper endpoint, and the paper’s own tool is proved tight, so it cannot decide the question. 5 open	standardlower-boundresearch-opennew-idea (ai)
	No key agreement from GC-OWF Open for round complexity growing with the security parameter. Proved in full for two messages, which is public-key encryption; the constant-round extension is sketched in the paper’s appendix without a theorem, its security half deferred to the PKE proof. 5 open	otherseparationresearch-openadaptation (ai)
	Threshold one-shot decryption without extractability Open: whether threshold one-shot decryption (for every corruption threshold f < 1/2) follows from one-shot signatures and an ordinary, non-extractable witness encryption scheme. The one known construction needs the witness-encryption extractor to run its security reduction, and the source paper leaves open whether extractability can be weakened or dropped altogether. 5 open	standardassumptionresearch-opennew-idea (ai)IOG
	OWFs are black-box useless for key agreement Open in the general case, which the paper names as the central open problem left by its work. Settled for three restricted protocol classes: constant-query perfect, constant-round constant-query imperfect, and Merkle-type. 6 open	otherimpossibilityresearch-opennew-idea (ai)
	OWF minimality, non-black-box reductions Open when the classical security implication is not witnessed by a black-box reduction between the two games. Settled affirmatively whenever it is, for uniform and non-uniform quantum adversaries alike, with the implementation reduction left arbitrary. 5 open	standardequivalenceresearch-opennew-idea (ai)
	PKE from constant-noise planted k-XOR Open: whether public-key encryption can be based on the hardness of planted k-XOR with a linear number of equations and a constant noise rate, as a single assumption. The survey poses it as one of two closing open questions and does not return to it; every combinatorial scheme it surveys needs sub-constant noise.	standardseparationresearch-openbarrier (ai)
	Ring-LWE error parity Open: whether recovering the Ring-LWE error modulo two is as hard as recovering the error itself. The easy direction is trivial; the source states it has no formal reduction for this one and relies on two heuristics instead, one of which changes the error distribution. 6 open	standardequivalenceresearch-opennew-idea (ai)
	No round-optimal pairing-free blind signature Open for a polynomial query budget. The impossibility is proved when User_2 and Verify together make O(log lambda) random-oracle queries, including when oracle outputs contain group elements; the superpolynomial message space hypothesis is retained. 5 open	ggmimpossibilityresearch-openadaptation (ai)
	Certifying no small non-expanding set Open: whether the non-existence of a small non-expanding set in a random unbalanced bipartite graph admits a nondeterministic certificate that is sound and complete on average, at the parameters the ABW cryptosystem uses. The survey poses it as one of two closing open questions, takes no position, and does not return to it.	standardseparationresearch-opennew-idea (ai)
	Three moves from DL, ROM only Open: three moves, black-box in the group, ROM only, from DL alone. Three moves is achieved from DDH in the ROM and from DL in AGM+ROM; four moves is achieved from DL in the ROM. 5 open	romassumptionresearch-opennew-idea (ai)
	RBE update bound, key-dependent schedules Open exactly when the update schedule may depend on the sampled public keys, which is the standard on-demand completeness notion. Proved when the schedule is any fixed function of registration times (Theorem 4.1) or of the registered identity names and the CRS (Theorem 4.12). 5 open	standardlower-boundresearch-openadaptation (ai)