Path Oram - University of California, Santa Cruz

Path Oram - University of California, Santa Cruz

PATH ORAM AN EXTREMELY SIMPLE OBLIVIOUS RAM PROTOCOL Aaron Chu Presentation for the course of Network Security 1/31/20 CHEAT ENGINE Access patterns leak: 80% of search queries to encrypted database! WHY IT CONCE RNS US ? THE SOLUTION Oblivious RAM (Random Access Machine) : The goal is to access data without revealing the access patterns. ORAM Algorithms: Nave ORAM Square Root ORAM Path ORAM WHAT TO HIDE? Which data is being accessed.

How old it is when it was last accessed. Whether the same data is being accessed. Whether it is sequentially accessed or randomly accessed. Whether the access is read or write. WHAT IS A GOOD ORAM ALGORITHM? a) Correctness: The construction is correct, i.e., it returns data consistent with the request sequence. b) Obliviousness: For any two request sequences with , we have: for anyone except the client c) Performance THE MODEL Client Storage Server blocks Application Capacity: Server

NAVE SOLUTION : table of N blocks For each block we do the following operations: Get the bock from the server. Decrypt the block. Read or write to the block if necessary. Re-encrypt the block with a different key. Write back the block to the storage system. Works: - Correct - Oblivious Overhead: O(N) - Read the entire table for every access SQUARE ROOT ALGORITHM N blocks Permuted memory For each of N requests: 1.

N dummy blocks N block shelter - Correct - Oblivious Overhead: O(N) Look for block in the shelter If not found, get block from permuted memory, put it in shelter Otherwise access the next dummy block After N requests: 2. Reshuffle permuted memory, obliviously update with values in shelter DATA SHUFFLING Permuted memory Use a sorting network:

Oblivious shuffling: sort based on a PRF Enc Sorted based on: Enc PATH ORAM Most practical ORAM construction to date. Highly efficiency and low overhead. Simple algorithm (16 lines of code is enough). Structure Server side: Binary Tree (It doesnt have to be a binary tree) Client side: Position Map, Stash PATH ORAM SERVER END LAYOUT some nodes are empty bucke t block Data blocks stored in nodes of the tree on server end. Its a complete binary tree. Blocks can just be arranged as an array. N : number of blocks B: block size in bits. Z: Bucket size. L: Height of the tree

L = -1. nodes can contain multiple blocks PATH ORAM BLOCK POSITION 1 2 3 4 5 6 7 8 Position comes from the leave sequence number. The position of the block is chosen randomly from 1 2^L (total number of leaves). PATH ORAM BLOCK POSITION 1 2 3 4

5 6 7 8 A block must be placed on the path to its position, if the block is at position 5 it can only be place in this path. PATH ORAM BLOCK POSITION 1 2 3 4 5 6 7 8 A block must be placed on the path to its position, if the block is at position 1 it can only be place in this path. POSITION MAP 1 1429 1

7 2 13 4 11 5 10 6 Server Client 3 3 42 Block No. 1 2 Position 2 3

. . 13 14 1 1 STASH Stash is a cache for blocks. Stash is used to store blocks overflowed from the server. Stash (size is 9) one block THE LOGIC 1. Read the entire path which contains the block requested. 2. Update the block if necessary. 3.

Remap the block to a new position randomly. 4. Re-encrypt the block with a different key. 5. Writeback the whole path. EXAMPLE MODIFY BLOCK 7 1 142 1 3 34 12 7 2 13 5 10 6

Server Client 4 11 Block No. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 2 4

3 4 3 1 2 2 1 1 Position Stash 8 9 4 3 2 1

EXAMPLE 1 142 1 3 34 12 7 2 13 5 10 6 Server Client 4 11 Block No. 1 2

3 4 5 6 7 8 9 10 11 12 13 14 2 4 3 4 3 1 2

2 1 1 Position 1. Lookup blocks 9 8 Stash position 4 3 2 1 EXAMPLE 1 142 1 2. Read the entire path

7 4 11 2 13 5 10 6 Server Client 3 34 12 Block No. 1 2 3 4 5 6

7 8 9 10 11 12 13 14 2 4 3 4 3 1 2 2 1 1 Position

4 3 2 Data is decrypted and stored in the stash. Stash 8 9 1 7 13 10 6 1 EXAMPLE 1 142

1 3 34 12 7 2 13 5 10 6 Server Client 4 11 Block No. 1 2 3 4 5

6 7 8 9 10 11 12 13 14 2 4 3 4 3 1 2 2 1 1

Position 4 3. Client read/modify block 7. Stash 8 9 1 7 13 10 6 3 2 1 EXAMPLE 1

142 1 3 34 12 7 2 13 5 10 6 Server Client 4 11 Block No. 1 2 3 4

5 6 7 8 9 10 11 12 13 14 2 4 3 4 3 1 1 2 1

1 Position 4 4. Assign a new random position. Stash 8 9 1 7 13 10 6 3 2 1

EXAMPLE 1 142 3 34 12 4 11 The deepest bucket first. 2 Try the upper level if full. Server Client Try root level if full. Block No. 1 2 Position Store in the stash if root is full. Stash 2 4 8

5 5. Write path back Blocks should be pushed down as deep as possible. Blocks should be always on the path to its position. 3 4 5 6 7 8 9 10 11 12 13 14 3 4 3 1

1 2 1 1 9 1 7 13 10 4 6 3 2 1 EXAMPLE 1

142 3 34 12 Block 8, 1, 13 can end up at any buckets on the entire path. 4 11 2 5 Server Client Block No. 1 2 3 4 5

6 7 8 9 10 11 12 13 14 2 4 3 4 3 1 1 2 1 1

Position 2 Stash 1 8 2 9 1 1 7 2 13 4 1 10 3 1 6 2

1 EXAMPLE 1 142 3 34 12 Block 9, 7, 10, 6 can end up at these buckets. 4 11 2 5 Server Client Block No. 1 2 3

4 5 6 7 8 9 10 11 12 13 14 2 4 3 4 3 1 1 2

1 1 Position 2 Stash 1 8 2 9 1 1 7 2 13 4 1 10 3 1

6 2 1 EXAMPLE 1 142 8 13 1 4 11 2 7 When writing back: Client pads dummy bocks if the bucket is not full. All the blocks are reencrypted using a randomized encryption scheme. 5

9 6 Server Client 3 34 12 Block No. 1 2 3 4 5 6 7 8 9 10 11 12 13 14

2 4 3 4 3 1 1 2 1 1 Position Stash 10 4 3 2

1 SIZE OF THE POSTION MAP bits are need to store the position for each block in the position map. bits are needed in total. Position map needs to be stored on the client side. What if the position map is too large for a client to keep ? RECURSIVE PAHT ORAM ORAM #1 Server Client Position Map ORAM #2 Position Map for #1 ORAM #3 Position Map for #2 OVERHEAD OF PATH ORAM WHY IT IS SECURE? Obliviousness: Server sees which is a sequence is the position of address based on the position map, together with a

sequence of encrypted paths Proof: For : is statistically independent of Observe that: If : Once is revealed, it is remapped to a new random label If : positions of different addresses are independent Therefore by Bayes rule: STASH SIZE When Z = 5, stash size is R. The probability that the stash overflows is : The size of the stash is independent on N. A constant number is enough to keep the possibility low enough. INTEGRITY MERKEL TREE EVALUATION STASH SIZE VS SECURITY EVALUATION STASH SIZE VS SECURITY EVALUATION BUCKET LOADS EVALUATION STASH SIZE VS BLOCKS

THANK YOU REFERENCES https://www.slideshare.net/ShijieZhang2/path-oram https://eprint.iacr.org/2013/280.pdf http://web.cs.ucla.edu/~rafail/PUBLIC/09.pdf https://www.slideshare.net/DibyenduNath/oram-a-brief-overview https://www.cs.utah.edu/~lifeifei/papers/oramvldb16.pdf https://en.wikipedia.org/wiki/Merkle_tree

Recently Viewed Presentations

  • EGR 2201 Unit 9 First-Order Circuits

    EGR 2201 Unit 9 First-Order Circuits

    Recall that when power is first applied to a dc circuit with inductors or capacitors, voltages and currents change briefly as the inductors and capacitors become energized. But once they are fully energized (i.e., "under dc conditions"), all voltages and...
  • AP Chemistry: post-holiday review

    AP Chemistry: post-holiday review

    Lattice energy . describes the energy of formation of one mole of a solid crystalline ionic compounds when ions in the gas phase combine. ex. Na+ (g) + Cl-(g) NaCl (s) Remember: ΔH. f ° = Na(s) + ½ Cl...
  • Grape Industry Benefits from ALS Research X-ray tomography

    Grape Industry Benefits from ALS Research X-ray tomography

    • Xylem vessels, tubes experience drought-induced breakage ... Trans-longitudinal section showing droplet details in four vessels at different stages of refilling (C), and the corresponding 3D volume rendering (D). Vessel on the far left shows evidence of failed refilling.
  • Poetry Bellringer #1 4/22/14 - scott.k12.ky.us

    Poetry Bellringer #1 4/22/14 - scott.k12.ky.us

    1. What does the son in the poem "Those Winter Sundays" learn in adulthood about love? 2. What is one example of imagery from the poem? What sense did this example of imagery appeal to? Today's Target: I . can...
  • Temperature Regulation Gen. Physiology Biology 346 Misericordia University

    Temperature Regulation Gen. Physiology Biology 346 Misericordia University

    Other freeze-tolerant animals: juvenile painted turtles (Chrysemys picta) gray tree frog (Hyla versicolor) garter snake (Thamnophis sirtalis) Eastern box turtle Antarctic Icefish- freeze intolerance Antifreeze proteins in ICF and ECF Antarctic icefish such as Trematomus, the so-called rock cod, live...
  • Parashat Vayakel - Pekud Por: Eliyahu BaYonah Director

    Parashat Vayakel - Pekud Por: Eliyahu BaYonah Director

    ¿Dónde está el lugar de Mi reposo? (Isaías 66:1) Parashat Semanal פרשת שבוע Parashat Semanal פרשת שבוע Dice Salomón: Ki haumenam yésheb Elohim al ha'áretz hine hashamáyim ushme hashamáyim lo yekalkeluká af kí-habayit haze asher banití. ¿Acaso morará Dios sobre...
  • The Meiji Restoratio n Photograph Interpretation / Compare

    The Meiji Restoratio n Photograph Interpretation / Compare

    Mutsuhito enlightened rule modernization Changes During The Meiji Restoration Abolished feudalism Eliminated samurai armies Reformed education Created a centralized gov't and encouraged loyalty to the emperor Japan's 1st Western-style constitution (1889), followed by the country's first elected Diet.
  • + Fashion Fabric for Fashion / Amanda Johnston

    + Fashion Fabric for Fashion / Amanda Johnston

    Fabric construction. Dyes are in liquid form or pigments (fine powder form) Dyeing is performed at either the yarn, fabric or garment stage. Yarn-dyed fabrics are more expensive but also more colourfast . Fabric dyeing (piece dyeing) is a faster,...