搜索结果: 1-15 共查到“hardness”相关记录139条 . 查询时间(0.111 秒)
Academy of Mathematics and Systems Science, CAS Colloquia & Seminars：Pandora Box Problem with Nonobligatory Inspection: Hardness and Approximation Scheme
潘多拉盒问题 非强制性检查 硬度 近似方案
2023/4/14
Weitzman (1979) introduced the Pandora Box problem as a model for sequential search with inspection costs, and gave an elegant index-based policy that attains provably optimal expected payoff. In vari...
How to leverage hardness of constant degree expanding polynomials over R to build iO
public-key cryptography Obfuscation
2019/9/16
In this work, we introduce and construct DD-restricted Functional Encryption (FE) for any constant D≥3D≥3, based only on the SXDH assumption over bilinear groups. This generalizes the notion of 33-res...
Another look at some isogeny hardness assumptions
post-quantum cryptography isogeny-based cryptography cryptanalysis
2019/8/22
The security proofs for isogeny-based undeniable signature schemes have been based primarily on two isogeny hardness assumptions: that the One-Sided Modified SSCDH problem and the One-More SSCDH probl...
Estimating Gaps in Martingales and Applications to Coin-Tossing: Constructions and Hardness
information theory foundations distributed cryptography
2019/7/8
Consider the representative task of designing a distributed coin-tossing protocol for nn processors such that the probability of heads is X0∈[0,1]X0∈[0,1], and an adversary can reset one processor to ...
We prove our result by reducing ff to (a variant of) the SINK-OF-VERIFIABLE-LINE problem, which is known to imply PPAD (and in fact CLS) hardness. The main building block of our reduction is a recentl...
Theoretical and Practical Approaches for Hardness Amplification of PUFs
Hardness Amplification Complexity Theory FPGA Security
2019/5/23
The era of PUFs has been characterized by the efforts put into research and the development of PUFs that are robust against attacks, in particular, machine learning (ML) attacks. In the lack of system...
Obfuscation from Polynomial Hardness: Beyond Decomposable Obfuscation
indistinguishability obfuscation functional encryption
2019/3/21
Every known construction of general indistinguishability obfuscation (iOiO) is either based on a family of exponentially many assumptions, or is based on a single assumption -- e.g.~functional encrypt...
How to leverage hardness of constant-degree expanding polynomials over $\mathbb{R}$ to build iO
FE Indistinguishability Obfuscation
2018/11/6
DD -restricted FE allows for useful evaluation of constant-degree polynomials, while only requiring the SXDH assumption over bilinear groups. As such, it is a powerful tool for leveraging hardness tha...
On the Hardness of Learning With Errors with Binary Secrets
complexity theory lattice based cryptography foundations
2018/11/5
We give a simple proof that the decisional Learning With Errors (LWE) problem with binary secrets (and an arbitrary polynomial number of samples) is at least as hard as the standard LWE problem (with ...
Handling Correlated Errors: Hardness of LWE in the Exponent
Learning with errors Error-Correction Generic Group Model
2018/11/5
The hardness of decoding random linear codes with errors is a complexity-theoretic assumption with broad applications to cryptography. In contrast, Reed-Solomon codes permit efficient decoding in many...
On the Hardness of the Computational Ring-LWR Problem and its Applications
Lattice Techniques Public Key Cryptography
2018/6/5
In this paper, we propose a new assumption, the Computational Learning With Rounding over rings, which is inspired by the computational Diffie-Hellman problem. Assuming the hardness of ring-LWE, we pr...
The Ring Learning with Errors problem (RLWE) introduced by Lyubashevsky, Peikert and Regev (LPR, Eurocrypt 2010, Eurocrypt 2013) quickly became a central element in cryptographic literature and a foun...
Generic Hardness of Inversion on Ring and Its Relation to Self-Bilinear Map
MCDH unbalanced modulus
2018/5/22
In this paper, we study the generic hardness of the inversion problem on a ring, which is a problem to compute the inverse of a given prime cc by just using additions, subtractions and multiplications...
Worst-Case Hardness for LPN and Cryptographic Hashing via Code Smoothing
LPN Worst-Case to Average Case Reductions Collision-Resistant Hashing
2018/3/23
We present a worst case decoding problem whose hardness reduces to that of solving the Learning Parity with Noise (LPN) problem, in some parameter regime. Prior to this work, no worst case hardness re...
Hardness of Non-Interactive Differential Privacy from One-Way Functions
differential privacy one-way functions traitor tracing
2017/11/21
A central challenge in differential privacy is to design computationally efficient noninteractive algorithms that can answer large numbers of statistical queries on a sensitive dataset. That is, we wo...