PhDThesis - Novel Secret Sharing and Commitment Schemes for Cryptographic Applications, Contents of the Thesis

Download this Presentation

julie PPT making software
0

Presentation Transcript

  • 1.Novel Secret Sharing and Commitment Schemes for Cryptographic Applications
  • 2.Contents of the Thesis 2
  • 3.Cryptographic Primitives Commitment Scheme: Commit: in a commitment scheme, the first party (Bob) initially commits to a value while keeping this value hidden. Reveal: then, he reveals the committed value to the second party (Alice) in order to be checked. Secret Sharing: Sharing: a secret is divided into n shares in order to be distributed among n players. Reconstruction: an authorize subset of players then cooperate to reveal the secret, e.g., t players where t < n is the threshold. 3 Secret = 1 Head Head/Tail can not change it, just reveal it Bob Alice
  • 4.Rational Secret Sharing Problem: the players deny to reveal their shares in the secret recovery phase, therefore, the secret is not reconstructed at all. Example: f (x) = 3 + 2 x + x2  t=3 shares are enough for recovery. Model: players are selfish rather than being honest or malicious. If all players act selfishly, secret recovery fails. Solution: 4 Pi Pj Pk 6 11 only Pk learns the secret “3” 6 11 18 selfish unknown real recovery round fake secret recovery rounds …
  • 5.Trust and Reputation Trust vs Reputation: trust is a personal quantity, created between “2” players, whereas reputation is a social quantity in a network of “n” players. If all players have an equal view, trust = reputation. Our Function is not just a function of a single round, but of the history: 5 A1 A2 A3 A4 0.4 0.5 0.6 0.5 Bad Pi (C) Newcomer Pi (C) Good Pi (C) Bad Pi (D) Newcomer Pi (D) Good Pi (D)
  • 6.Part I 6
  • 7.1. Social Secret Sharing Motivation: components of a secure system may have different levels of importance (weight) as well as reputation (in terms of availability), therefore, a good protocol should balance these two factors respectively. Contribution: we propose a social secret sharing scheme where shares are allocated based on each player's reputation. It is similar to human social life where people share more secrets with whom they trust and vice versa. Review: we use two different secret sharing schemes: Proactive Secret Sharing: to update shares without changing the secret in order to deal with a mobile adversary. Weighted Secret Sharing: to assign multiple shares to some specific players rather than a single share. 7
  • 8.Google Amazon Yahoo Microsoft 3 = 3 2 = 2 4 = 1 1 = 4 Dealer Cooperation Pi (C): is available during secret recovery and sends correct shares. Defection Pi(D): is not available at the required time or may respond with delay. Corruption Pi(X): has been compromised by a passive or active adversary. Google Amazon Yahoo Microsoft s4 s1 s2 s3 s9 s10 s11 s5 s6 s13 Application: Self-Organizing Clouds 8 s5 s6 s13 s9 s10 s11 s4 s1 s2 s3 3 = 3 2 = 2 4 = 2 1 = 3 Dealer Free s9 s10 s11 s13 s14 s1 s2 s3 s5 s6
  • 9.Subprotocol: Enrollment Share Enrollment: How to enroll a new share without having access to the original secret sharing polynomial f(x)? Example: f (x) = 3 + 2 x + x2 (we need at least t = 3 players) C1= (4-2)(4-3) / (1-2)(1-3) = 1 C2= (4-1)(4-3) / (2-1)(2-3) = -3 Lagrange constants C3= (4-1)(4-2) / (3-1)(3-2) = 3 9 P1 2 P2 8 P3 6 3 1 2 1 5 7 P1 2 P2 8 P3 3 6 1 2 5 1 7 P1 6 P2 11 P4 ? P3 18 * C1 + * C2 + * C3 = 13 2 6 1 P1 * C1 + * C2 + * C3 = -7 8 5 2 P2 * C1 + * C2 + * C3 = 21 1 7 3 P3 27
  • 10.P2 P4 P3 P1 Proactive Secret Sharing s1 s2 s3 s4 Share Update: adding a polynomial with zero constant term to the original secret sharing polynomial. 1 9 5 6 Subprotocol: Share Update 10 g (x) = 0 + 4x + 2x2 + 10x3 f’ (x) = 3 + 8x + 9x2 + 2x3 g (1) = 3 g (2) = 5 g (3) = 1 g (4) = 12 f’ (1) = 9 f’ (2) = 6 f’ (3) = 6 f’ (4) = 8 f (1) = 6 f (2) = 1 f (3) = 5 f (4) = 9 f (x) = 3 + 4x + 7x2 + 5x3  Z13 [x] 3 5 1 12 9 6 8 6 + secret = 3 s3 and s4 are now useless mobile adversary
  • 11. Social Secret Sharing: sharing and reconstruction phases are similar to Shamir’s scheme, the only difference is the social tuning step. Tuning: based on the availability, reputation and consequently i are adjusted. Enrollment: players jointly cooperate to generate s14f(x); original polynomial. Update & Disenrollment: players update shares except s4 where new sif’(x). Our Construction 11 Enrollment Amazon Microsoft s14 s1 s2 s3 s13 4 = 2 1 = 4 s4 Update & Disenrollment Amazon Microsoft s14 s1 s2 s3 s13 4 = 2 1 = 3 Amazon Microsoft s4 s1 s2 s3 s13 4 = 1 1 = 4
  • 12.Part II 12
  • 13.2. Socio-Rational Secret Sharing Motivation: we would like to consider a repeated secret sharing game where players enter into a long-term interaction for executing an unknown number of independent secret sharing schemes. Contribution: we propose a socio-rational secret sharing scheme where a public trust network is constructed to incentivize the players to be cooperative, i.e., they can gain extra utility if they cooperate. Reminder: the concept of socio-rational secret sharing is new. Social Secret Sharing: to update weights of players in a setting with “honest” and “malicious” players. Rational Secret Sharing: to deal with secret recovery in a rational setting with “selfish” players. 13
  • 14.Application: Repeated Games Sealed-Bid Auctions: repeated secret sharing game, where Bidders select “n” out of “N” auctioneers based on their reputation. Each bidder then acts as an independent dealer and shares his bid. Auctioneers simulate a secure MPC protocol to define the outcome. In the last round of the MPC, they need to recover the selling price. Only auctioneers who learn (report) the selling price are rewarded. At the end of each game, the reputation of each auctioneer is updated. 14
  • 15.Utility Assumption Rational vs Socio-Rational Secret Sharing: : whether Pi has learned the secret or not, and let . The first preference illustrates that whether Pi learns the secret or not, he prefers to stay reputable. The second assumption means Pi prefers the outcome in which he learns the secret. The third one means Pi prefers the outcome in which the fewest number of other players learn the secret. 15 Socio-Rational Rational
  • 16.Utility Computation Sample Function: which satisfies our utility assumptions 16 assume Pi has contributed in two consecutive periods p and p-1 i  [1 , 3] suppose  = $100 [-3 , -1] or [1 , 3]
  • 17. (2,2)-Socio-Rational Secret Sharing: despite rational secret sharing, cooperation is always the best strategy even if the other party defects. Utility Comparison: where (2,2)- Secret Sharing with Selfish Players (2,2)- Socio-Rational Secret Sharing Comparison 17
  • 18.Part III 18
  • 19.3. Dynamic Secret Sharing Motivation: in a threshold scheme, the sensitivity of the secret as well as the number of players may fluctuate due to various reasons. Over time, mutual trust might be decreased: perhaps due to the organizational problems or security incidents, and vise versa. The structure of the organization to which the players belong might be changed: new players may join the organization or current parties may leave the organization. Therefore, modifying the threshold and/or changing the secret might be required throughout the lifetime of a secret Contribution: we analyze the re-sharing technique in both passive and active adversary models, provide a simple dynamic scheme for changing the secret and threshold, and propose sequential secret sharing. 19
  • 20.Threshold Modification (passive) Example: using Lagrange/Vandermonde method, let 20  P3 generates
  • 21.Threshold Decrease (passive/active) Public Evaluation: remember how players could enroll a newcomer. We use the same approach, let f(x) = 9 + 2x + 5x2  13 f(1) = 6 – 4 ( 𝟑−𝟔 1−4 ) = 2 f(2) = 6 – 4 ( 𝟕−𝟔 2−4 ) = 8  f(x) = 9 + 6x  13 f(3) = 6 – 4 ( 𝟖−𝟔 3−4 ) = 1 21 P1 1 P2 3 P3 3 1 1 2 2 3 2 P1 2 P2 3 P3 1 3 1 1 3 2 2 P1 3 P2 7 P4: Public Share ? P3 8 * 1 + 2 * -3 + * 3 = 1 * 1 + * -3 + * 3 = 4 * 1 + * -3 + * 3 = 1 2 3 1 P1 3 3 1 P2 2 2 1 P3 6 ^ ^ ^ ^
  • 22.Threshold Increase (passive/active) Zero Addition: let f(x,i) be the share of  belonging to Pi (threshold is t). Initially, t’ players are selected at random; each might be honest or malicious. Each Pi shares a secret i using a VSS scheme, where threshold is t’-2. Each Pi adds shares of the accepted i-s together; the new secret is = 𝑖 . 22
  • 23.Part IV 23
  • 24.4. Multicomponent Commitment Motivation: to construct a commitment scheme suitable for sealed-bid auctions, where the bidders decide on their bids ahead of time and independent of whatever info they may gain during the auction. Contribution: a new multicomponent commitment scheme with several committers & verifiers, and three unconditionally secure first-price auction protocols with a decreasing price mechanism, i.e., Dutch-style auction. Review: the goal of a sealed-bid auction is to protect different parameters. Secrecy of the selling price and winner’s identity are optional. To have a fair auction, confidentiality of the losing bids is important: They can be used in future auctions and negotiations by different parties, e.g., auctioneers to maximize their revenues or competitors to win the auction. 24
  • 25.Our Construction Multicomponent Commitment Scheme: we assume that majority of players are honest. Our proposed scheme consists of a trusted initializer T and n players P1… Pn (T leaves the scheme after the initialization). Initialize: T selects n polynomials of degree n-1 and sends gi(x) to Pi and also n-1 distinct points on each gi(x) to other players: Commit: each player Pi computes yi = gi(xi) as a committed value and broadcasts yi to other players, where xi is the secret of Pi. That is, y1…yn are committed values and x1…xn are secrets of players accordingly. Reveal: each Pi discloses gi(x) and his secret xi to other parties through the public broadcast channel. Other players Pj investigate the validity of yi = gi(xi). They then check to see if all n-1 points are on gi(x), i.e., voting. 25 g1 g2 gn … n-1 points … … …
  • 26.Application: Secure 1st-Price Auction Verifiable Protocol with Non-Repudiation: i [,] and  = -+1 Initialize: trusted initializer T randomly selects  polys for each bidder, where B1…Bn. He sends n-1 distinct points on each poly to other parties. Commit: suppose i [0,7],  = 8, i = 7 - 5 = 2, and Z13. Bi first converts i to a specific binary vector and then converts it to a non-binary vector as shown below. Finally, he commits to the resulting field elements. Reveal: auction starts with  and continues by a decreasing price mechanism. The winner proves his claim by revealing all commitments. Losers also prove that their bids have been less than the winning price. E.g., if win= 4, Bi reveals (7- 4 +1)= 4 values in [7,13), i.e., i has been at most 3 26 x=1→[7,13) x=0→[0,7)
  • 27.Application: Secure 1st-Price Auction Efficient Verifiable Protocol with Non-Repudiation:  ≈ log2 Initialize: T randomly selects  polynomials for each bidder. He then sends n-1 distinct points on each polynomial to other parties. Commit: suppose i [0,7],  = log28 = 3, i = 7- (101)2 = 2, and Z13. Bi first converts - i to a binary vector and then converts it to a non-binary vector as shown here. Finally, he commits to the resulting field elements. Reveal: auction starts with  and continues by a decreasing price mechanism. The winner proves his claim by revealing all commitments. Losers also prove that their bids have been less than the winning price. E.g., if win= 5, Bi reveals the 3rd value: 7-(1??)2 = 3, i.e., i has been at most 3 if win= 3, Bi reveals 1st and 3rd values: 7-(1?1)2 = 2, i.e., i has been at most 2 27 x=1→[7,13) x=0→[0,7)
  • 28. There still exist many untouched areas in cryptography that need to be explored, specially from a multidisciplinary perspective, e.g., social and socio-rational secret sharing schemes. The sealed-bid auctions are just an instance of financial functionalities. A similar privacy preserving approach can be used in other problem instances such as investment agreement, stock exchange, strategic negotiations, etc. Final Remarks 28
  • 29. Thank You Very Much Special Thanks to Douglas Stinson, Ian Goldberg (UW), Urs Hengartner (UW), Christos Papadimitriou (UCBerkeley), Charles Rackoff (U of T), Omer Reingold (Microsoft), Ronald Cramer (CWI), defense committee members, my friends in the CrySP lab, and my deepest gratitude to my father who passed away on July 13 and loved to see this moment. 29
  • 30.Review of a Well-Known Solution Previous Solution: trust value T(p+1) is given by the following equations and it depends on the previous trust rating where:   0 and   0 [CIA’00]. 30 T(p) < 0 T(p) = 0 T(p) > 0 T(p) < 0 T(p) = 0 T(p) > 0
  • 31.Intuition and Motivation 31 There exist some common principles for trust modeling A lies to B for the 1st time: defection A lies to B for the 2nd time: same defection + past history A cheat on B: costly defection Impact of the brain’s history 
  • 32.Secret Sharing in a Multidisciplinary Model 32
  • 33.33 Non-cooperative Games Prisoner’s Dilemma: is a well-known non-cooperative game. Players: P1 and P2 Actions: Confess or Keep Quiet Payoffs: Nash Equilibrium: no matter Pi selects “C” or “D”, Pj chooses “D”. -1 , -1 +1 , -2 D: Confess -2 , +1 0 , 0 C: Quiet D: Confess C: Quiet P2 P1 -1 , -1 +1 , -2 -2 , +1 0 , 0 P2 -1 , -1 +1 , -2 -2 , +1 0 , 0 P2 P1 P1 +1 : Free 0 : Jail for 1 year -1 : Jail for 2 years -2 : Jail for 3 years -1 , -1 +1 , -2 -2 , +1 0 , 0 P1 P1: “what if I cooperate” -1 , -1 +1 , -2 -2 , +1 0 , 0 P1 P1: “what if I defect” P2 P2 the ideal outcome
  • 34.STOC’04 Paper Problem: 3-out-of-3 rational secret sharing. Solution: a multi-round recovery approach. In each round, dealer initiates a fresh secret sharing of the same secret. During an iteration, each Pi flips a biased coin ci with Pr[ci = 1] = . Players then compute c* =  ci by MPC without revealing ci-s. If c* = ci = 1, player Pi broadcast his share. There are 3 possibilities: If all shares are revealed, the secret is recovered and the protocol ends. If c* = 1 and 0 or 2 shares are revealed, players terminate the protocol. In any other cases, the dealer and players proceed to the next round. 34 P1 P2 P3 s1 s2 s3 all players are selfish 3 0 0 0 0 1 1 1 1 0 , 2 0 0 0
  • 35.Our Construction in Nutshell Utility Estimation Function: is used by a rational foresighted player. Estimation of the future gain/loss due to the trust adjustment (virtual). Learning the secret at the current time (real). The number of other players learning the secret at the moment (real). Prominent Properties: our solution Has a single reconstruction round. Provides a stable solution concept. Is immune to rushing attack. Prevents the players to abort. 35 decision making $ despite all the existing protocols
  • 36.Protocol: Socio-Rational SS 36 Secret Sharing: Secret Recovery:
  • 37.Threshold Modification (active) Example: using bivar-poly 37 9 + 2 (23) + 7 (23)2 ?=? 3 + 12 (22) + 2 (22)2  473  83  5 (mod 13) fails to increase the threshold P1 generates 
  • 38.Application: Sequential SS Sharing : in the first phase, 38
  • 39.Application: Sequential SS Reconstruction: in the second phase, 39  2 is uniquely determined  1 is uniquely determined (original secret)
  • 40.40 Sequential Secret Sharing: generating multiple secrets with various t-s Conjunctive [TCC’04] At least 2 users at L0 At least 3 users at L0 | L1 At least 4 users at L0 | L1 | L2 At least 6 users at L0 | L1 | L2 | L3 Application of Our Dynamic Scheme L0: t0 = 2 L1: t1 = 3 L2: t2 = 4 L3: t3 = 6 Disjunctive [Crypto’88] 2 users at L0 is enough 3 users at L0 | L1 is enough 4 users at L0 | L1 | L2 is enough 6 users at L0 | L1 | L2 | L3 is enough original Secret0 intermediate Secret1 intermediate Secret2 last Secret3
  • 41.41 Disjunctive Secret Sharing Example: t0 = 2 < t1 = 3 < t2 = 4 < t3 = 6 : max threshold f (x)= 2 + 3 x1 + 1 x2 + 5 x3 + 6 x4 + 13 x5  Z19 Secret is the leading coefficient ids are in monotonically decreasing order by level (can be random) 14 15 10 7 9 8 11 13 12 6 5 2 4 3 1 L0: t0 = 2 L1: t1 = 3 L2: t2 = 4 L3: t3 = 6 f (6-2 = 4) (x) = 11 + 2 x f (6-3 = 3) (x) = 11 + 11 x + x2 f (6-4 = 2) (x) = 2 + 11 x + 15 x2 + 13 x3 f (6-6 = 0) (x) = 2 + 3 x + 1 x2 + 5 x3 + 6 x4 + 13 x5 f (0) (x) = a + b x + c x2 + d x3 + e x4 + g x5 f (1) (x) = b + 2 c x + 3 d x2 + 4 e x3 + 5 g x4 f (2) (x) = 2 c + 6 d x + 12 e x2 + g x3 f (3) (x) = 6 d + 5 e x + 3 g x2 f (4) (x) = 5 e + 6 g x 5 e + 6 g (14) = 1 e = 6 5 e + 6 g (15) = 3 g = 13 (14 , 1) (15 , 3)
  • 42.42 Conjunctive Secret Sharing Example: t0 = 2 < t1 = 3 < t2 = 4 < t3 = 6 : ids are in increasing order or random f (x)= 13 + 3 x + 1 x2 + 5 x3 + 6 x4 + 2 x5  Z19 Secret is the constant coefficient 1 2 9 6 8 7 3 5 4 15 14 11 13 12 10 L0: t0 = 2 L1: t1 = 3 L2: t2 = 4 L3: t3 = 6 f (x) = 13 + 3 x + 1 x2 + 5 x3 + 6 x4 + 2 x5 f (t0 = 2) (x) = 2 + 11 x + 15 x2 + 2 x3 f (t1 = 3) (x) = 11 + 11 x + 6 x2 f (t2 = 4) (x) = 11 + 12 x a + b + c + d + e + g = 11 a + 2 b + 4 c + 8 d + 16 e + 13 g = 14 (1 , 11) (2 , 14) f (0) (x) = a + b x + c x2 + d x3 + e x4 + g x5 (11 , 10) (10 , 17) 5 e + 3 g = 17 5 e + 9 g = 10 f (4) (x) = 5 e + 6 g x (3 , 15) 2 c + 18 d + 13 e + 8 g = 15 f (2) (x) = 2 c + 6 d x + 12 e x2 + g x3 (6 , 8) 6 d + 11 e + 13 g = 8 f (3) (x) = 6 d + 5 e x + 3 g x2 a = 13 b = 3 c = 1 d = 5 e = 6 g = 2
  • 43.Security of the MCS Hiding: each receiver is computationally unbounded and cannot learn secrets before the reveal phase except with a negligible probability Binding: each sender is computationally unbounded and cannot cheat by revealing a fake secret except with a negligible probability Validating: with the honest majority assumption, players can validate all secrets correctly during the reveal phase in the presence of colluders. 43 dishonest minority honest majority guessing one point of honest players
  • 44.Dutch-Style Auction Decreasing Mechanism: starts from the highest price and continues by a decreasing mechanism. This is secure without using any crypto techniques but we are looking for other properties. Example: 1 = 2 2 = 1 3 = 1 (2 bits for each bid: 4 options) Let j = 22 – 1 = 3 possible prices (excluding zero). Each bidder Bi broadcasts 1 or 0 depending on whether he wants to pay price j or not. If all agent broadcast 0, set j = j – 1 and go to step-2 otherwise j is the selling price and the bidder who submitted 1 wins. Losing bids are not revealed by losers. 44 2 3 1 2 1
  • 45.Cost Analysis Computation & Communication: interpolating a polynomial of degree at most n-1 at n points takes O(C(n) log n), that is, O(n log2 n) using FFT: MCS: n polynomials(n-1) are evaluated at n points. VNR: n polynomials(n-1) are evaluated at n points. EVNR: n=n*log2 polynomials(n-1) are evaluated at n points. we have full secrecy, i.e., (n-1) players cannot learn the committed value, and the honest majority assumption is for the correctness. 45
Related
Latest Release
SlideHTML5 Home Explore About Us
Support Contact Us FAQ Blog
Legal Terms DMCA Cookies Policy Privacy Terms of Service
SlideHtml5

Free online presentation maker for an exceptional way of presenting. Make interactive online presentations that impress, inspire, and connect.

© 2024 SlideHTML5. All rights reserved

© 2024 SlideHTML5.

All rights reserved