Cryptography in Individual Account Sharing and Partial Secrets Reconstruction
Explore the innovative approach of Individual Cryptography in scenarios like account sharing and partial secrets reconstruction. Learn about protocols like MPC and PIK for secure data handling. Discover solutions for secure online services and verifying individual credentials using cryptographic techniques.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Individual Individual Cryptography Cryptography Stefan Dziembowski, Sebastian Faust, Tomasz Lizurej
In a In a nutshell nutshell: : We initiate the study of I Individual ndividual C Cryptography ryptography MPC hard cryptography 2
Outline Outline 1. 1. Motivation Motivation 1. 1. Account Account sharing 2. 2. Partial Partial reconstruction reconstruction of 2. Formal model and the MPC(TEE)-hardness 3. Proof of Individual Knowledge (PIK) 4. Outlook sharing of secret secret shares shares 3
Example 1: Account sharing Example 1: Account sharing Credentials Credentials ? Credentials Credentials ? (expensive) (expensive) online service online service Credentials Credentials ? Strawman Strawman solution access . Works if the parties do not solution: make knowledge of ? equivalent to root do not fully trust each other. 4
How to How to attack strawman strawman countermeasure countermeasure attack the the The parties use an MPC protocol protocol that emulates a virtual party . MPC In this way they can jointly control their shared account. (expensive) (expensive) online service online service Virtual party holding Virtual party holding credentials credentials ? 5
Our Our solution solution Proof of Individual Individual Knowledge (PIK) Knowledge (PIK) Proof of VERIFIER VERIFIER PROVER PROVER Credentials Credentials ? Credentials Credentials ? A protocol that allows a verifier to check that ? is stored on a single machine. single 6
Example 2: Example 2: P Partial secrets secrets artial reconstruction of shared reconstruction of shared PARTY 1 PARTY 1 Additive secret sharing Sharing Sharing ?? DEALER DEALER PARTY 2 PARTY 2 Secret Secret ? Sharing Sharing ?? Dealer s Dealer s goal computing computing any without reconstructing entire ?. goal: : share secret ? so that any function function of of ? is not possible 7
Our Our solution solution Individual (ISS) (ISS) Individual Secret Secret Sharing Sharing PARTY 1 PARTY 1 Sharing Sharing ?? DEALER DEALER Individual Individual Secret Secret Sharing Sharing PARTY 2 PARTY 2 Secret Secret ? Sharing Sharing ?? The Party 1 and Party 2 can compute any function of ? either if they they have have full full knowledge knowledge of ? or they perform a heavy a heavy computation computation on on shared shared ?. 8
Outline Outline 1. Motivation 1. Account sharing 2. Partial reconstruction of secret shares 2. 2. Formal Formal model and the MPC(TEE) model and the MPC(TEE)- -hardness 3. Proof of Individual Knowledge (PIK) 4. Outlook hardness 9
?? ?? ?? ? ???(?) ???(?) Goal Goal: : Find functions: hard hard to compute using distributed cryptography, but easy easy to compute individually. 10
MPC MPC- -hardness hardness TEE TEE- -hardness hardness ?? ?? ?? ?? ?? ?? ?(??,??,??) ?(??,??,??) 11
The MPC The MPC- -hardness hardness Sequential calls to hash computed much faster in a a regular hash functions functions like SHA256 can be regular CPU CPU than in MPC. in MPC. ??? SHA256 SHA256 SHA256 SHA256 SHA256 SHA256 ? 12
The TEE The TEE- -hardness hardness SHA256 SHA256 SHA256 SHA256 OUT SHA256 SHA256 ? SHA256 SHA256 SHA256 SHA256 OUT SHA256 SHA256 ? 13
The The massive massive parallel parallel computations computations Simple Simple assumption assumption, applicable for both for both - - MPCs and TEEs. MPCs and TEEs. , applicable 14
The The distributed distributed adversary adversary Distributed adversary ? = (?1, ,??). Communication in rounds (at most ? rounds). (??, ,??) 15
The The MPC MPC- -Oracle Oracle ?: ?,?? ?,?? Q: Q: (x, (x, mode A: A: H(x) H(x) or mode) ) or (??, ,??) SLOW SLOW FAST FAST Mode Mode Setting Setting Modelling how the H is computed in an MPC setting. Inputs are NOT revealed. queries At most ? queries. Modelling how the H is computed in a regular processor. Inputs are revealed. Unbounded Unboundednumber of queries Inputs Inputs secrecy secrecy Number Number of queries. of queries 16
Formal Formal model model the the extractors extractors (??, ,??, ,??) (?1,????) (?2,????) (?3,????) (?4,????) ?? ?1 ?2 ?3 ?4 ????, ,?? FAST queries transcript FAST queries transcript ????, ,?? ????) (?? (??, ,??) 17
Outline Outline 1. Motivation 1. Account sharing 2. Partial reconstruction of secret shares 2. MPC(TEE)-hardness and the formal model 3. 3. Proof of Proof of Individual Individual Knowledge (PIK) Knowledge (PIK) 4. Outlook 18
Proof of Proof of Individual Individual Knowledge (PIK) definition definition VERIFIER VERIFIER ? Knowledge (PIK) - - PROVER PROVER ? Secret Secret ? Secret Secret ? ????= ???/?? 19
PIK PIK - - completeness completeness VERIFIER VERIFIER ? PROVER PROVER ? ?? ?? Secret Secret ? Secret Secret ? The (??, , ??) bounded ????= ??? with overwhelming probability. bounded (?,?) finish with 20
PIK PIK - - soundness soundness VERIFIER VERIFIER ? PROVER PROVER (??, ,??) ??efficient efficient and with low number with low number of of false false positives positives and Secret Secret ? Secret Secret ? ????), ,??( (?? ????)}] ????= ??? Pr[? {??( (?? < ? ????. 21
? ? PIK PIK the the protocol protocol Choose random ? ?,?? ? Secret Secret ? Secret Secret ? Find ? nonces ??, , such that scratch scratch ?,?,?? starts with ? zeroes ??, ,?? Verify correctness of computation 22
Stay Stay alert! alert! The popular hash functions linearly process long inputs. Example: Merkle-Damgard scheme for SHA 256. ? = ??||?? H H ?? ? Compression Compression function function ?? ?? H H H H IV IV ??? 23
The The precomputation precomputation on a on a shared shared secret secret ? = ??||?? ?? ?? ???256(?) be easily easily computed computed in a in a distributed distributed way can can be way ?? ?? H H H H ???? IV IV ??? ???? ???? 24
The The procedure procedure scratch scratch(?,?,?) ?: ?,?? ?,?? ? ? ? ?? ?? ?? ? ?,??, ? ?,?? ? ? ? ? ?? ?? ?? ? = ??, ,??, ?? ?,?? ? ? ? ? ?? ?? ?? ? ? ? Repeat ? + ? times 25
Completeness, soundness and the extractor efficiency Completeness The Prover ? with scratch scratch attempts with an an access access to to S S needs to do around ? ??+? ? attempts, the Verifier will need to verify ? nonces. . ?? ? Soundness Large amount of columns appear in the transcript to finish the protocol. columns in the in the scratch scratch attempts attempts must ?? ? ?? Finally, we can define an efficient extractor that looks for full columns of computation in the transcript. 26
Outlook Analyze the primitives and protocols where the MPC(TEE) attacks may apply. Discuss the MPC(TEE) Hard functions. 27
Thank you 28 This presentation used icons from flaticon.com
