搜索结果: 1-15 共查到“密码学 lower bound”相关记录21条 . 查询时间(0.062 秒)
A Candidate Access Structure for Super-polynomial Lower Bound on Information Ratio
secret sharing general access structures information ratio
<
2019/6/3
The contribution vector (convec) of a secret sharing scheme is the vector of all share sizes divided by the secret size. A measure on the convec (e.g., its maximum or average) is considered as a crite...
Valiant's Universal Circuits Revisited: an Overall Improvement and a Lower Bound
Universal Circuits Private Function Evaluation Multiparty Computation
<
2018/11/7
A universal circuit (UC) is a general-purpose circuit that can simulate arbitrary circuits (up to a certain size nn). At STOC 1976 Valiant presented a graph theoretic approach to the construction of U...
Is there an Oblivious RAM Lower Bound for Online Reads?
Oblivious RAM Lower Bounds Locally Decodable Codes
<
2018/6/25
Oblivious RAM (ORAM), introduced by Goldreich and Ostrovsky (JACM 1996), can be used to read and write to memory in a way that hides which locations are being accessed. The best known ORAM schemes hav...
Ciphertext Expansion in Limited-Leakage Order-Preserving Encryption: A Tight Computational Lower Bound
Encrypting plaintexts CRYPTO
<
2018/6/5
Order-preserving encryption emerged as a key ingredient underlying the security of practical database management systems. Boldyreva et al. (EUROCRYPT '09) initiated the study of its security by introd...
An Oblivious RAM (ORAM) introduced by Goldreich and Ostrovsky [JACM'96] is a (possibly randomized) RAM, for which the memory access pattern reveals no information about the operations performed. The m...
Conjecturally Superpolynomial Lower Bound for Share Size
secret sharing information-theory
<
2018/2/9
Our conjecture emerges after introducing the notion of convec set for an access structure, a subset of nn-dimensional real space. We prove several topological properties about convec sets and raise se...
A Ciphertext-Size Lower Bound for Order-Preserving Encryption with Limited Leakage
Symmetric Encryption Searchable Encryption Lower Bound
<
2017/11/27
We consider a recent security definition of Chenette, Lewi, Weis, and Wu for order-revealing encryption (ORE) and order-preserving encryption (OPE) (FSE 2016). Their definition says that the compariso...
How to Circumvent the Two-Ciphertext Lower Bound for Linear Garbling Schemes
garbled circuits lower bound on linear garbling schemes semi-private function evaluation
<
2017/2/20
At EUROCRYPT 2015, Zahur et al.\ argued that all linear, and thus, efficient, garbling schemes need at least two kk-bit elements to garble an AND gate with security parameter kk. We show how to circum...
Improving the lower bound on the maximum nonlinearity of 1-resilient Boolean functions and designing functions satisfying all cryptographic criteria
Boolean functions nonlinearity resiliency algebraic immunity
<
2016/12/8
In this paper, we improve the lower bound on the maximum nonlinearity of 1-
resilient Boolean functions, for n even, by proposing a method of constructing this
class of functions attaining the best ...
Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning
Parity Learning bounded storage model
<
2016/2/22
We prove that any algorithm for learning parities requires either a memory of
quadratic size or an exponential number of samples. This proves a recent conjecture
of Steinhardt, Valiant and Wager [SV...
Circuit ORAM: On Tightness of the Goldreich-Ostrovsky Lower Bound
oblivious RAM secure multi-party computation
<
2016/1/7
We propose a new tree-based ORAM scheme called Circuit ORAM. Circuit ORAM makes
both theoretical and practical contributions. From a theoretical perspective, Circuit ORAM
shows that the well-known G...
Is There an Oblivious RAM Lower Bound?
ORAM Sorting Multi-Party Computation Cryptography
<
2015/12/23
An Oblivious RAM (ORAM), introduced by Goldreich and Ostrovsky (JACM 1996), is a
(probabilistic) RAM that hides its access pattern, i.e. for every input the observed locations
accessed are similarly...
The Good lower bound of Second-order nonlinearity of a class of Boolean function
Boolean function Higher-order derivatives Second-order nonlinearit Walsh-spectrum
<
2012/3/26
this paper we find the lower bound of second-order nonlinearity of Boolean function $f_{\lambda}(x) = Tr_{1}^{n}(\lambda x^{p})$ with $p = 2^{2r} + 2^{r} + 1$, $\lambda \in \mathbb{F}_{2^{r}}^{*}$ and...
Improved lower bound on the number of balanced symmetric functions over GF(p)
lower bound balanced symmetric functions Symmetric Boolean functions
<
2009/6/3
The lower bound on the number of n-variable balanced
symmetric functions over finite fields GF(p) presented in [1]
is improved in this paper.
A lower bound on the higher order nonlinearity of algebraic immune functions
lower bound higher order nonlinearity algebraic immune functions
<
2009/3/19
We extend the lower bound, obtained by M. Lobanov, on the first order nonlinearity
of functions with given algebraic immunity, into a bound on the higher order
nonlinearities.