The Experts below are selected from a list of 9651 Experts worldwide ranked by ideXlab platform
Salil P Vadhan - One of the best experts on this subject based on the ideXlab platform.
-
on extractors and exposure Resilient Functions for sublogarithmic entropy
Random Structures and Algorithms, 2013Co-Authors: Yakir A Reshef, Salil P VadhanAbstract:We study Resilient Functions and exposure-Resilient Functions in the low-entropy regime. A Resilient Function (a.k.a. deterministic extractor for oblivious bit-xing sources) maps any distribution on n-bit strings in which k bits are uniformly random and the rest are xed into an output distribution that is close to uniform. With exposure-Resilient Functions, all the input bits are random, but we ask that the output be close to uniform conditioned on any subset of n k input bits. In this paper, we focus on the case that k is sublogarithmic in n. We simplify and improve an explicit construction of Resilient Functions for k sublogarithmic in n due to Kamp and Zuckerman (SICOMP 2006), achieving error exponentially small in k rather than polynomially small in k. Our main result is that when k is sublogarithmic in n, the short output length of this construction (O(logk) output bits) is optimal for extractors computable by a large class of space-bounded streaming algorithms. Next, we show that a random Function is a Resilient Function with high probability if and only if k is superlogarithmic in n, suggesting that our main result may apply more generally. In contrast, we show that a random Function is a static (resp. adaptive) exposure-Resilient Function with high probability even if k is as small as a constant (resp. log logn). No explicit exposure-Resilient Functions achieving these parameters are known.
-
On extractors and exposure‐Resilient Functions for sublogarithmic entropy
Random Structures and Algorithms, 2012Co-Authors: Yakir A Reshef, Salil P VadhanAbstract:We study Resilient Functions and exposure-Resilient Functions in the low-entropy regime. A Resilient Function (a.k.a. deterministic extractor for oblivious bit-xing sources) maps any distribution on n-bit strings in which k bits are uniformly random and the rest are xed into an output distribution that is close to uniform. With exposure-Resilient Functions, all the input bits are random, but we ask that the output be close to uniform conditioned on any subset of n k input bits. In this paper, we focus on the case that k is sublogarithmic in n. We simplify and improve an explicit construction of Resilient Functions for k sublogarithmic in n due to Kamp and Zuckerman (SICOMP 2006), achieving error exponentially small in k rather than polynomially small in k. Our main result is that when k is sublogarithmic in n, the short output length of this construction (O(logk) output bits) is optimal for extractors computable by a large class of space-bounded streaming algorithms. Next, we show that a random Function is a Resilient Function with high probability if and only if k is superlogarithmic in n, suggesting that our main result may apply more generally. In contrast, we show that a random Function is a static (resp. adaptive) exposure-Resilient Function with high probability even if k is as small as a constant (resp. log logn). No explicit exposure-Resilient Functions achieving these parameters are known.
-
on extractors and exposure Resilient Functions for sublogarithmic entropy
arXiv: Computational Complexity, 2010Co-Authors: Yakir A Reshef, Salil P VadhanAbstract:We study deterministic extractors for oblivious bit-fixing sources (a.k.a. Resilient Functions) and exposure-Resilient Functions with small min-entropy: of the Function's n input bits, k << n bits are uniformly random and unknown to the adversary. We simplify and improve an explicit construction of extractors for bit-fixing sources with sublogarithmic k due to Kamp and Zuckerman (SICOMP 2006), achieving error exponentially small in k rather than polynomially small in k. Our main result is that when k is sublogarithmic in n, the short output length of this construction (O(log k) output bits) is optimal for extractors computable by a large class of space-bounded streaming algorithms. Next, we show that a random Function is an extractor for oblivious bit-fixing sources with high probability if and only if k is superlogarithmic in n, suggesting that our main result may apply more generally. In contrast, we show that a random Function is a static (resp. adaptive) exposure-Resilient Function with high probability even if k is as small as a constant (resp. log log n). No explicit exposure-Resilient Functions achieving these parameters are known.
Yakir A Reshef - One of the best experts on this subject based on the ideXlab platform.
-
on extractors and exposure Resilient Functions for sublogarithmic entropy
Random Structures and Algorithms, 2013Co-Authors: Yakir A Reshef, Salil P VadhanAbstract:We study Resilient Functions and exposure-Resilient Functions in the low-entropy regime. A Resilient Function (a.k.a. deterministic extractor for oblivious bit-xing sources) maps any distribution on n-bit strings in which k bits are uniformly random and the rest are xed into an output distribution that is close to uniform. With exposure-Resilient Functions, all the input bits are random, but we ask that the output be close to uniform conditioned on any subset of n k input bits. In this paper, we focus on the case that k is sublogarithmic in n. We simplify and improve an explicit construction of Resilient Functions for k sublogarithmic in n due to Kamp and Zuckerman (SICOMP 2006), achieving error exponentially small in k rather than polynomially small in k. Our main result is that when k is sublogarithmic in n, the short output length of this construction (O(logk) output bits) is optimal for extractors computable by a large class of space-bounded streaming algorithms. Next, we show that a random Function is a Resilient Function with high probability if and only if k is superlogarithmic in n, suggesting that our main result may apply more generally. In contrast, we show that a random Function is a static (resp. adaptive) exposure-Resilient Function with high probability even if k is as small as a constant (resp. log logn). No explicit exposure-Resilient Functions achieving these parameters are known.
-
On extractors and exposure‐Resilient Functions for sublogarithmic entropy
Random Structures and Algorithms, 2012Co-Authors: Yakir A Reshef, Salil P VadhanAbstract:We study Resilient Functions and exposure-Resilient Functions in the low-entropy regime. A Resilient Function (a.k.a. deterministic extractor for oblivious bit-xing sources) maps any distribution on n-bit strings in which k bits are uniformly random and the rest are xed into an output distribution that is close to uniform. With exposure-Resilient Functions, all the input bits are random, but we ask that the output be close to uniform conditioned on any subset of n k input bits. In this paper, we focus on the case that k is sublogarithmic in n. We simplify and improve an explicit construction of Resilient Functions for k sublogarithmic in n due to Kamp and Zuckerman (SICOMP 2006), achieving error exponentially small in k rather than polynomially small in k. Our main result is that when k is sublogarithmic in n, the short output length of this construction (O(logk) output bits) is optimal for extractors computable by a large class of space-bounded streaming algorithms. Next, we show that a random Function is a Resilient Function with high probability if and only if k is superlogarithmic in n, suggesting that our main result may apply more generally. In contrast, we show that a random Function is a static (resp. adaptive) exposure-Resilient Function with high probability even if k is as small as a constant (resp. log logn). No explicit exposure-Resilient Functions achieving these parameters are known.
-
on extractors and exposure Resilient Functions for sublogarithmic entropy
arXiv: Computational Complexity, 2010Co-Authors: Yakir A Reshef, Salil P VadhanAbstract:We study deterministic extractors for oblivious bit-fixing sources (a.k.a. Resilient Functions) and exposure-Resilient Functions with small min-entropy: of the Function's n input bits, k << n bits are uniformly random and unknown to the adversary. We simplify and improve an explicit construction of extractors for bit-fixing sources with sublogarithmic k due to Kamp and Zuckerman (SICOMP 2006), achieving error exponentially small in k rather than polynomially small in k. Our main result is that when k is sublogarithmic in n, the short output length of this construction (O(log k) output bits) is optimal for extractors computable by a large class of space-bounded streaming algorithms. Next, we show that a random Function is an extractor for oblivious bit-fixing sources with high probability if and only if k is superlogarithmic in n, suggesting that our main result may apply more generally. In contrast, we show that a random Function is a static (resp. adaptive) exposure-Resilient Function with high probability even if k is as small as a constant (resp. log log n). No explicit exposure-Resilient Functions achieving these parameters are known.
Jung Hee Cheon - One of the best experts on this subject based on the ideXlab platform.
-
CRYPTO - Nonlinear Vector Resilient Functions
Advances in Cryptology — CRYPTO 2001, 2001Co-Authors: Jung Hee CheonAbstract:An (n, m, k)-Resilient Function is a Function f : Fn2 → Fm2 such that every possible output m-tuple is equally likely to occur when the values of k arbitrary inputs are fixed by an adversary and the remaining n - k input bits are chosen independently at random. In this paper we propose a new method to generate a (n + D + 1, m, d - 1)- Resilient Function for any non-negative integer D whenever a [n, m, d] linear code exists. This Function has algebraic degree D and nonlinearity at least 2n+D - 2n⌊√2n+D+1⌋ + 2n-1. If we apply this method to the simplex code, we can get a (t(2m - 1) + D + 1, m, t2m-1 - 1)-Resilient Function with algebraic degree D for any positive integers m, t and D. Note that if we increase the input size by D in the proposed construction, we can get a Resilient Function with the same parameter except algebraic degree increased by D.
-
ICISC - Elliptic Curves and Resilient Functions
Lecture Notes in Computer Science, 2001Co-Authors: Jung Hee Cheon, Seongtaek CheeAbstract:In this paper, we propose a novel relationship between the correlation of two polynomial-type Boolean Functions and the order of an associated algebraic curve. By this relationship, we propose a method to generate a Resilient (correlation immune and balanced) Function from a cubic polynomial. Since our Resilient Function is derived from a polynomial over a finite field, its nonlinearity is much easier to control. Moreover we can construct a Resilient Function with multi-bit outputs. We present several examples of a Resilient Function with 2 outputs.
-
Nonlinear vector Resilient Functions
Lecture Notes in Computer Science, 2001Co-Authors: Jung Hee CheonAbstract:An (n, m, k)-Resilient Function is a Function f: F n 2 → F m 2 such that every possible output m-tuple is equally likely to occur when the values of k arbitrary inputs are fixed by an adversary and the remaining n - k input bits are chosen independently at random. In this paper we propose a new method to generate a (n + D + 1, m, d - 1)-Resilient Function for any non-negative integer D whenever a [n,m,d] linear code exists. This Function has algebraic degree D and nonlinearity at least 2 n+D - 2 n [√2 n+D+1 ] + 2 n-1 . If we apply this method to the simplex code, we can get a (t(2 m - 1) + D + 1,m,t2 m-1 - 1)-Resilient Function with algebraic degree D for any positive integers m,t and D. Note that if we increase the input size by D in the proposed construction, we can get a Resilient Function with the same parameter except algebraic degree increased by D.
Salih Ergün - One of the best experts on this subject based on the ideXlab platform.
-
A high speed IC Random Number Generator based on phase noise in ring oscillators
2010 IEEE International Symposium on Circuits and Systems (ISCAS), 2010Co-Authors: Ülkühan Güler, Salih ErgünAbstract:There is an increasing demand for fully digital, high speed Random Number Generators because of their speed compatibility and uncomplicated integration to digital platforms. To the best of our knowledge, this paper presents the first ASIC implementation of Random Number Generator based on ring oscillators. Prototypes have been designed and fabricated by using HHNEC's 0.25 /xm eFlash process with a supply voltage of 2.5V. The circuit occupies 0.043 mm2 and dissipates minimum 0.011 W of power. IC design level experiences, measurements, analyses of measurements and statistical test results are also demonstrated. Instead of Resilient Function which decreases the throughput, we propose to use only a simple Von Neumann corrector, thus 4 times faster throughput can be obtained in comparison with the previous design in which Resilient Function is employed. We achieved fullfilled test results from NIST 800-22 test suit after Von Neuman corrector with 16.5 Mbps throughput which is the highest data rate to date with fullfiled test results. The results were repeatable numerous times.
Douglas R. Stinson - One of the best experts on this subject based on the ideXlab platform.
-
a provably secure true random number generator with built in tolerance to active attacks
IEEE Transactions on Computers, 2007Co-Authors: Berk Sunar, William J Martin, Douglas R. StinsonAbstract:This paper is a contribution to the theory of true random number generators based on sampling phase jitter in oscillator rings. After discussing several misconceptions and apparently insurmountable obstacles, we propose a general model which, under mild assumptions, will generate provably random bits with some tolerance to adversarial manipulation and running in the megabit-per-second range. A key idea throughout the paper is the fill rate, which measures the fraction of the time domain in which the analog output signal is arguably random. Our study shows that an exponential increase in the number of oscillators is required to obtain a constant factor improvement in the fill rate. Yet, we overcome this problem by introducing a postprocessing step which consists of an application of an appropriate Resilient Function. These allow the designer to extract random samples only from a signal with only moderate fill rate and, therefore, many fewer oscillators than in other designs. Last, we develop fault-attack models and we employ the properties of Resilient Functions to withstand such attacks. All of our analysis is based on rigorous methods, enabling us to develop a framework in which we accurately quantify the performance and the degree of resilience of the design
-
Orthogonal Arrays, Resilient Functions, Error-Correcting Codes, and Linear Programming Bounds
SIAM Journal on Discrete Mathematics, 1996Co-Authors: Jürgen Bierbrauer, K. Gopalakrishnan, Douglas R. StinsonAbstract:Orthogonal arrays (OAs) are basic combinatorial structures, which appear under various disguises in cryptology and the theory of algorithms. Among their applications are universal hashing, authentication codes, Resilient and correlation-immune Functions, derandomization of algorithms, and perfect local randomizers. In this paper, we give new explicit bounds on the size of orthogonal arrays using Delsarte's linear programming method. Specifically, we prove that the minimum number of rows in a binary orthogonal array of length $n$ and strength $t$ is at least $ 2^{n} - (n 2^{n-1}/t+1)$ and also at least $ 2^{n} - (2^{n-2}(n+1)/\lceil \frac{t+1}{2} \rceil).$ We also prove that these bounds are as powerful as the linear programming bound itself for many parametric situations. An $(n,m,t)$-Resilient Function is a Function $f: \{0,1\}^{n} \longrightarrow \{0,1\}^{m}$ such that every possible output $m$-tuple is equally likely to occur when the values of $t$ arbitrary inputs are fixed by an opponent and the remaining $n-t$ input bits are chosen independently at random. A basic problem is to maximize $t$ given $m$ and $n$, i.e., to determine the largest value of $t$ such that an $(n,m,t)$-Resilient Function exists. In this paper, we obtain upper and lower bounds for the optimal values of $t$ where $1 \leq n \leq 25$ and $1 \leq m < n$. The upper bounds are derived from Delsarte's linear programming bound, and the lower bounds come from constructions based on error-correcting codes. We also obtain new explicit upper bounds for the optimal values of $t$. It was proved by Chor et al. in [{\em Proc. {\rm 26}th IEEE Symp. on Foundations of Computer Science}, 1985, pp. 396--407] that an $(n,2,t)$-Resilient Function exists if and only if $ t < \lfloor \frac{2n}{3} \rfloor$. This result was generalized by Friedman [{\em Proc. $33$rd IEEE Symp. on Foundations of Computer Science}, 1992, pp. 314--319], who proved a bound for general $m$. We also prove some new bounds, and complete the determination of the optimal resiliency of Resilient Functions with $m=3$ and most of the cases for $m=4$. Several other infinite classes of (optimal) Resilient Functions are also constructed using the theory of anticodes.