Browse ORBi

- What it is and what it isn't
- Green Road / Gold Road?
- Ready to Publish. Now What?
- How can I support the OA movement?
- Where can I learn more?

ORBi

Practical Provable Security against Side-Channel Attacks Venkatesh, Srinivas Vivek Doctoral thesis (2015) Securing cryptographic systems in the presence of side-channel leakages is still an important problem. Over recent years, the cryptography theory community has shown considerable interest in formally ... [more ▼] Securing cryptographic systems in the presence of side-channel leakages is still an important problem. Over recent years, the cryptography theory community has shown considerable interest in formally modelling the side-channel leakages and in designing "provably" secure cryptographic primitives in these leakage models. This area is often referred to as leakage-resilient cryptography. Yet, designing a formal model that realistically captures side-channel leakages such as power consumption patterns, and designing primitives efficient enough to be deployed in practice in such a leakage model, remains a challenging research direction. In this work, we aim to bridge the above gap between the theory of provably secure cryptosystems that resist side-channel attacks and their practical relevance. Keeping this goal in mind, we analyze existing constructions and provide new ones for basic cryptographic primitives such as encryption and authentication in both public-key and symmetric-key cryptography. This dissertation consists of three parts. In the first part, we analyze existing and design new efficient leakage-resilient constructions for public-key encryption and digital signatures that tolerate continual leakage in the split-state leakage model. Our security reductions are in the generic bilinear group model. The constructions we consider are simple variants of the ElGamal key encapsulation mechanism, and the Boneh-Boyen and the Schnorr signature schemes. We also cryptanalyze a variant of the ElGamal key encapsulation mechanism that was previously conjectured to be leakage-resilient under certain conditions. The second part of this work is concerned with the protection of block ciphers in the probing adversarial leakage model. This approach, popularly known as masking in the cryptographic engineering community, is an effective countermeasure for block cipher implementations against power-analysis attacks. We improve the efficiency of a generic higher-order masking scheme recently proposed by Carlet et al. Improving the efficiency of this scheme is related to the problem of evaluating polynomials over binary finite fields in a newer cost model that counts only "non-linear" polynomial multiplications. We propose a new method for evaluating polynomials in this cost model, and argue (heuristically) that this method is asymptotically optimal. The third part deals with the construction of efficient leakage-resilient symmetric-key authentication and encryption schemes. The constructions are shown to be secure in the standard model under a recently introduced simulatable leakage assumption. This assumption offers practitioners a hope to work with a formal leakage model that allows empirical verifiability. We propose a leakage-resilient CBC-like message authentication code, and also propose a leakage-resilient PRG-based chosen-plaintext secure encryption scheme for which we quantify the leakage it tolerates during the challenge phase in terms of security of a single iteration. Our constructions tolerate continual leakage but require leak-free updates. [less ▲] Detailed reference viewed: 242 (9 UL)Limits of a conjecture on a leakage-resilient cryptosystem Galindo, David ; Venkatesh, Srinivas Vivek in Information Processing Letters (2014), 114(4), 192-196 Recently it was conjectured that an ElGamal-based public-key encryption scheme with stateful decryption resists lunch-time chosen ciphertext and leakage attacks in the only computation leaks information ... [more ▼] Recently it was conjectured that an ElGamal-based public-key encryption scheme with stateful decryption resists lunch-time chosen ciphertext and leakage attacks in the only computation leaks information model. We give a non-trivial upper bound on the amount of leakage tolerated by this conjecture. More precisely, we prove that the conjecture does not hold if more than a (3/8 + o (1)) fraction of the bits are leaked at every decryption step, by showing a lunch-time attack that recovers the full secret key. The attack uses a new variant of the Hidden Number Problem, that we call Hidden Shares – Hidden Number Problem, which is of independent interest. [less ▲] Detailed reference viewed: 53 (2 UL)Cubic Sieve Congruence of the Discrete Logarithm Problem, and fractional part sequences Venkatesh, Srinivas Vivek ; in Journal of Symbolic Computation (2014), 64 The Cubic Sieve Method for solving the Discrete Logarithm Problem in prime fields requires a nontrivial solution to the Cubic Sieve Congruence (CSC) $ x^3 \equiv y^2 z (mod p) $, where 'p' is a given ... [more ▼] The Cubic Sieve Method for solving the Discrete Logarithm Problem in prime fields requires a nontrivial solution to the Cubic Sieve Congruence (CSC) $ x^3 \equiv y^2 z (mod p) $, where 'p' is a given prime number. A nontrivial solution must also satisfy $ x^3 \neq y^2 z $ and $ 1 <= x,y,z < p^a $, where 'a' is a given real number such that $ 1/3 < a <= 1/2 $. The CSC problem is to find an efficient algorithm to obtain a nontrivial solution to CSC. CSC can be parametrized as $ x \equiv v^2 z (mod p) $ and $ y \equiv v^3 z (mod p) $. In this paper, we give a deterministic polynomial-time ($ O(ln^3 p) $ bit-operations) algorithm to determine, for a given 'v', a nontrivial solution to CSC, if one exists. Previously it took $ õ(p^a) $ time in the worst case to determine this. We relate the CSC problem to the gap problem of fractional part sequences, where we need to determine the non-negative integers 'N' satisfying the fractional part inequality $ {\theta N} < \phi $ ($ \theta $ and $ \phi $ are given real numbers). The correspondence between the CSC problem and the gap problem is that determining the parameter 'z' in the former problem corresponds to determining 'N' in the latter problem. We also show in the $ a = 1/2 $ case of CSC that for a certain class of primes the CSC problem can be solved deterministically in $ õ(p^{1/3}) $ time compared to the previous best of $ õ(p^{1/2}) $. It is empirically observed that about one out of three primes is covered by the above class. [less ▲] Detailed reference viewed: 61 (2 UL)Fast Evaluation of Polynomials over Binary Finite Fields and Application to Side-Channel Countermeasures Coron, Jean-Sébastien ; ; Venkatesh, Srinivas Vivek in Batina, Lejla; Robshaw, Matthew (Eds.) Cryptographic Hardware and Embedded Systems – CHES 2014 (2014) We describe a new technique for evaluating polynomials over binary finite fields. This is useful in the context of anti-DPA countermeasures when an S-box is expressed as a polynomial over a binary finite ... [more ▼] We describe a new technique for evaluating polynomials over binary finite fields. This is useful in the context of anti-DPA countermeasures when an S-box is expressed as a polynomial over a binary finite field. For n-bit S-boxes our new technique has heuristic complexity ${\cal O}(2^{n/2}/\sqrt{n})$ instead of ${\cal O}(2^{n/2})$ proven complexity for the Parity-Split method. We also prove a lower bound of ${\Omega}(2^{n/2}/\sqrt{n})$ on the complexity of any method to evaluate $n$-bit S-boxes; this shows that our method is asymptotically optimal. Here, complexity refers to the number of non-linear multiplications required to evaluate the polynomial corresponding to an S-box. In practice we can evaluate any 8-bit S-box in 10 non-linear multiplications instead of 16 in the Roy-Vivek paper from CHES 2013, and the DES S-boxes in 4 non-linear multiplications instead of 7. We also evaluate any 4-bit S-box in 2 non-linear multiplications instead of 3. Hence our method achieves optimal complexity for the PRESENT S-box. [less ▲] Detailed reference viewed: 78 (6 UL)A Leakage-Resilient Pairing-Based Variant of the Schnorr Signature Scheme Galindo, David ; Venkatesh, Srinivas Vivek in Stam, Martijn (Ed.) Cryptography and Coding (2013) Leakage-resilient cryptography aims at capturing side-channel attacks within the provable security framework. Currently there exists a plethora of schemes with provably secure guarantees against a variety ... [more ▼] Leakage-resilient cryptography aims at capturing side-channel attacks within the provable security framework. Currently there exists a plethora of schemes with provably secure guarantees against a variety of side-channel attacks. However, meeting the strongest security levels (resilience against continual leakage attacks) under the weakest assumptions leads currently to costly schemes. Additionally, recent results show the impossibility to achieve the strongest leakage-resilient security levels for cryptosystems whose secret key is uniquely determined by its public key. The above justifies the use of stronger assumptions to achieve simpler, more efficient schemes, since most deployed and practical cryptosystems satisfy the above-mentioned uniqueness of the secret key property. In particular, the Schnorr-based leakage-resilient digital signature schemes proposed up to now are built by gluing together ℓ-copies of the basic signature scheme, resulting in a public key that admits exponentially-many secret keys. Furthermore, the space needed to store the secret key material is proportional to the leakage tolerated by these schemes. We aim at designing a leakage-resilient variant of the Schnorr signature scheme whose secret key’s storage space is constant, independently of the amount of leakage that it can tolerate. We assume that at any given time only the parts of the memory in use leak (split-state/only computation leaks information model); we ease the problem of exhibiting a security reduction by relying on generic groups (generic bilinear group model). We proceed by first proposing a pairing analogue of the Schnorr signature scheme, that we next transform to include split signing key updates. We give a leakage-resilience lower bound in generic bilinear groups against continual leakage attacks for the new scheme. [less ▲] Detailed reference viewed: 36 (1 UL)Analysis and Improvement of the Generic Higher-Order Masking Scheme of FSE 2012 Roy, Arnab ; Venkatesh, Srinivas Vivek in Bertoni, Guido; Coron, Jean-Sébastien (Eds.) Cryptographic Hardware and Embedded Systems - CHES 2013 (2013) Masking is a well-known technique used to prevent block cipher implementations from side-channel attacks. Higher-order side channel attacks (e.g. higher-order DPA attack) on widely used block cipher like ... [more ▼] Masking is a well-known technique used to prevent block cipher implementations from side-channel attacks. Higher-order side channel attacks (e.g. higher-order DPA attack) on widely used block cipher like AES have motivated the design of efficient higher-order masking schemes. Indeed, it is known that as the masking order increases, the difficulty of side-channel attack increases exponentially. However, the main problem in higher-order masking is to design an efficient and secure technique for S-box computations in block cipher implementations. At FSE 2012, Carlet et al. proposed a generic masking scheme that can be applied to any S-box at any order. This is the first generic scheme for efficient software implementations. Analysis of the running time, or masking complexity, of this scheme is related to a variant of the well-known problem of efficient exponentiation (addition chain), and evaluation of polynomials. In this paper we investigate optimal methods for exponentiation in TeX by studying a variant of addition chain, which we call cyclotomic-class addition chain, or CC-addition chain. Among several interesting properties, we prove lower bounds on min-length CC-addition chains. We define the notion of TeX -polynomial chain, and use it to count the number of non-linear multiplications required while evaluating polynomials over TeX . We also give a lower bound on the length of such a chain for any polynomial. As a consequence, we show that a lower bound for the masking complexity of DES S-boxes is three, and that of PRESENT S-box is two. We disprove a claim previously made by Carlet et al. regarding min-length CC-addition chains. Finally, we give a polynomial evaluation method, which results into an improved masking scheme (compared to the technique of Carlet et al.) for DES S-boxes. As an illustration we apply this method to several other S-boxes and show significant improvement for them. [less ▲] Detailed reference viewed: 89 (5 UL)A Practical Leakage-Resilient Signature Scheme in the Generic Group Model Galindo, David ; Venkatesh, Srinivas Vivek in Knudsen, Larsr; Wu, Huapeng (Eds.) Selected Areas in Cryptography (2013) We propose a leakage-resilient signature scheme in the continual leakage model that is based on a well-known identity-based encryption scheme by Boneh and Boyen (Eurocrypt 2004). The proposed signature ... [more ▼] We propose a leakage-resilient signature scheme in the continual leakage model that is based on a well-known identity-based encryption scheme by Boneh and Boyen (Eurocrypt 2004). The proposed signature scheme is the most efficient among the existing schemes that allow for continual leakage. Its efficiency is close to that of non leakage-resilient pairing-based signature schemes. It tolerates leakage of almost half of the bits of the secret key at every new signature invocation. We prove the security of the new scheme in the generic bilinear group model. [less ▲] Detailed reference viewed: 134 (6 UL)Integer Complexity: Breaking the θ(n2) barrier Venkatesh, Srinivas Vivek ; E-print/Working paper (2008) The \textit{integer complexity} of a positive integer $n$, denoted $f(n)$, is defined as the least number of 1's required to represent $n$, using only 1's, the addition and multiplication operators, and ... [more ▼] The \textit{integer complexity} of a positive integer $n$, denoted $f(n)$, is defined as the least number of 1's required to represent $n$, using only 1's, the addition and multiplication operators, and the parentheses. The running time of the algorithm currently used to compute $f(n)$ is $\Theta(n^{2})$. In this paper we present an algorithm with $\Theta(n^{\log_{2}3})$ as its running time. We also present a proof of the theorem: the largest solutions of $f(m)=3k,\,3k\pm1$ are, respectively, $m=3^{k},\,3^{k}\pm3^{k-1}$. [less ▲] Detailed reference viewed: 102 (14 UL) |
||