Making malicious security orders of magnitude more efficient than previous FAST DISTRIBUTED RSA KEY GENERATION FOR semi-honest SEMI-HONEST AND MALICIOUS ADVERSARIES Tore Frederiksen, Yehuda Lindell1,2, Valery Osheter2, Benny Pinkas1 15 min vs. 41 sec 1: Bar-Ilan University 2: Unbound Tech OUTLINE • Introduction • Semi-honest construction • Malicious construction • Efficiency • Conclusion 05/06/2018 Page 2 INTRODUCTION – PUBLIC KEY ENCRYPTION m Gen ℓ → &' (' / ← Dec ) ) ← Enc / 1. -. m 05/06/2018 Page 3 INTRODUCTION – DISTRIBUTED PKE m ," - * ← Res * , * - . * ← Dec # - 1) 3 !" # ← Enc * () * ← Dec # . 1) 2 * ← Res * , * - . ," . 05/06/2018 Page 4 INTRODUCTION – MOTIVATION • Sometimes it can also be used for distributed signature schemes – Which is an end in itself • Relevant for MPC protocols – CDN01, semi-homomorphic PKE – DPSZ12, somewhat-homomorphic PKE • Cloud based key management – – 05/06/2018 Page 5 INTRODUCTION – RSA • RSA: – Find ℓ bit primes pand q -. – Public key: $% = ', ) (= 3, 2 + 1) 4- – Private key: 2 ≡ ) mod $ − 1 (% − 1) • RSA is widely in use – TLS, PGP, … • Lots of previous work on the distributed setting – …, [Gil99], [BF01], [ACS02], [DM10], [HMR+12] • Challenging to solve efficiently 05/06/2018 Page 6 INTRODUCTION – DISTRIBUTED RSA • Distributed RSA: – Find ℓ bit primes " = " + " and ' = ' + ' $ & $ & 01 – Public key: " + " ⋅ (' + ' ) = +, - (= 3, 2 + 1) $ & $ & 50 – Private key: 3 + 3 ≡ - mod " − 1 (' − 1) $ & • Pick random " , ' , " , ' $ $ & & • Do Rabin-Miller • Repeat 05/06/2018 Page 7 INTRODUCTION – DISTRIBUTED RSA • Candidate generation – Sampling random ! , $ , ! , $ s.t. ! = ! + ! and $ = $ + $ " " % % " % " % • Construct modulus – Compute ( = ! + ! ⋅ $ + $ " % " % • Verify modulus – Check that ( is the product of two primes • Construct keys -. – Construct shares * and * s.t. * ≡ , mod ! − 1 ⋅ ($ − 1) " % 05/06/2018 Page 8 INTRODUCTION – INTUITION Candidate generation Construct modulus Verify modulus Construct keys 05/06/2018 Page 9 OUTLINE • Introduction • Semi-honest construction • Malicious construction • Efficiency • Conclusion 05/06/2018 Page 10

Fast Distributed RSA Key Generation for Malicious Adversaries PDF

26 Pages

2017

7.44 MB

English

Checking for file health...

Preview Fast Distributed RSA Key Generation for Malicious Adversaries

Making malicious security orders of magnitude more efficient than previous FAST DISTRIBUTED RSA KEY GENERATION FOR semi-honest SEMI-HONEST AND MALICIOUS ADVERSARIES Tore Frederiksen, Yehuda Lindell1,2, Valery Osheter2, Benny Pinkas1 15 min vs. 41 sec 1: Bar-Ilan University 2: Unbound Tech OUTLINE • Introduction • Semi-honest construction • Malicious construction • Efficiency • Conclusion 05/06/2018 Page 2 INTRODUCTION – PUBLIC KEY ENCRYPTION m Gen ℓ → &' (' / ← Dec ) ) ← Enc / 1. -. m 05/06/2018 Page 3 INTRODUCTION – DISTRIBUTED PKE m ," - * ← Res * , * - . * ← Dec # - 1) 3 !" # ← Enc * () * ← Dec # . 1) 2 * ← Res * , * - . ," . 05/06/2018 Page 4 INTRODUCTION – MOTIVATION • Sometimes it can also be used for distributed signature schemes – Which is an end in itself • Relevant for MPC protocols – CDN01, semi-homomorphic PKE – DPSZ12, somewhat-homomorphic PKE • Cloud based key management – – 05/06/2018 Page 5 INTRODUCTION – RSA • RSA: – Find ℓ bit primes pand q -. – Public key: $% = ', ) (= 3, 2 + 1) 4- – Private key: 2 ≡ ) mod $ − 1 (% − 1) • RSA is widely in use – TLS, PGP, … • Lots of previous work on the distributed setting – …, [Gil99], [BF01], [ACS02], [DM10], [HMR+12] • Challenging to solve efficiently 05/06/2018 Page 6 INTRODUCTION – DISTRIBUTED RSA • Distributed RSA: – Find ℓ bit primes " = " + " and ' = ' + ' $ & $ & 01 – Public key: " + " ⋅ (' + ' ) = +, - (= 3, 2 + 1) $ & $ & 50 – Private key: 3 + 3 ≡ - mod " − 1 (' − 1) $ & • Pick random " , ' , " , ' $ $ & & • Do Rabin-Miller • Repeat 05/06/2018 Page 7 INTRODUCTION – DISTRIBUTED RSA • Candidate generation – Sampling random ! , $ , ! , $ s.t. ! = ! + ! and $ = $ + $ " " % % " % " % • Construct modulus – Compute ( = ! + ! ⋅ $ + $ " % " % • Verify modulus – Check that ( is the product of two primes • Construct keys -. – Construct shares * and * s.t. * ≡ , mod ! − 1 ⋅ ($ − 1) " % 05/06/2018 Page 8 INTRODUCTION – INTUITION Candidate generation Construct modulus Verify modulus Construct keys 05/06/2018 Page 9 OUTLINE • Introduction • Semi-honest construction • Malicious construction • Efficiency • Conclusion 05/06/2018 Page 10

See more

The list of books you might like

Most books are stored in the elastic cloud where traffic is expensive. For this reason, we have a limit on daily download.