{"id":1130,"date":"2025-11-25T23:05:17","date_gmt":"2025-11-26T07:05:17","guid":{"rendered":"https:\/\/omniteck.com\/?p=1130"},"modified":"2025-11-25T23:05:33","modified_gmt":"2025-11-26T07:05:33","slug":"constant%e2%80%91time-oram-with-fully-homomorphic-encryption","status":"publish","type":"post","link":"https:\/\/xn--y9aq2bc.com\/?p=1130","title":{"rendered":"Constant\u2011time ORAM with Fully Homomorphic Encryption"},"content":{"rendered":"<div class=\"taxonomy-category wp-block-post-terms\"><span class=\"wp-block-post-terms__prefix\">Category: <\/span><a href=\"https:\/\/xn--y9aq2bc.com\/?cat=223\" rel=\"tag\">LLM Chats<\/a><span class=\"wp-block-post-terms__separator\">\u2192<\/span><a href=\"https:\/\/xn--y9aq2bc.com\/?cat=224\" rel=\"tag\">Technical Solutions<\/a><\/div>\n\n\n<h3 class=\"wp-block-heading\">Why combine ORAM and FHE?<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Oblivious RAM (ORAM)<\/strong> hides the access pattern of memory reads\/writes, preventing leakage from which data is accessed.<\/li>\n\n\n\n<li><strong>Fully Homomorphic Encryption (FHE)<\/strong> lets a server compute on encrypted data without ever seeing the plaintext.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">When both are used, an adversary learns <strong>nothing<\/strong> about the data values <strong>or<\/strong> the sequence of operations\u2014crucial for secure cloud computation on sensitive workloads.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Core construction<\/h3>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>Step<\/th><th>Operation (performed by the client)<\/th><th>Operation (performed by the server)<\/th><\/tr><\/thead><tbody><tr><td>1<\/td><td>Encrypt each data block with an FHE scheme \u2192 ciphertexts <code>c_i<\/code>.<\/td><td>\u2014<\/td><\/tr><tr><td>2<\/td><td>Store the ciphertexts in an ORAM tree (e.g., Path\u2011ORAM).<\/td><td>Maintain the tree structure; no decryption needed.<\/td><\/tr><tr><td>3<\/td><td>To read\/write block <code>b<\/code>:<br>\u2022 Client generates a <strong>homomorphic query token<\/strong> that encodes the logical path to <code>b<\/code>.<\/td><td>Server uses the token to <strong>homomorphically evaluate<\/strong> the ORAM routing logic, retrieving the encrypted block without learning which leaf was accessed.<\/td><\/tr><tr><td>4<\/td><td>Server returns the ciphertext (or updated ciphertext) to the client.<\/td><td>All operations are performed on ciphertexts; the server never sees plaintext or the actual address.<\/td><\/tr><tr><td>5<\/td><td>Client decrypts (if needed) and, for writes, re\u2011encrypts the updated block and repeats the ORAM <strong>eviction<\/strong> step homomorphically.<\/td><td>Server runs the eviction algorithm on encrypted blocks, preserving the ORAM invariant.<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\">Achieving constant\u2011time behavior<\/h3>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Fixed\u2011size buckets<\/strong> \u2013 Each ORAM node stores a constant number <code>Z<\/code> of ciphertexts (e.g., <code>Z = 4<\/code>).<\/li>\n\n\n\n<li><strong>Uniform access pattern<\/strong> \u2013 Every logical operation triggers the same number of homomorphic evaluations (e.g., always traverse a full path of height <code>log\u2082 N<\/code>).<\/li>\n\n\n\n<li><strong>Parallel homomorphic evaluation<\/strong> \u2013 Modern FHE schemes (CKKS, BFV) support SIMD packing; the server can process all buckets of a level in a single homomorphic batch, keeping latency independent of the accessed block.<\/li>\n<\/ol>\n\n\n\n<p class=\"wp-block-paragraph\">Thus the total runtime per logical access is <strong>O(log\u202fN)<\/strong> in the number of homomorphic batches, but each batch has a <strong>constant<\/strong> size, yielding a <em>practically constant\u2011time<\/em> routine from the client\u2019s perspective.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Example parameter set<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Data size<\/strong>: <code>N = 2\u00b9\u2076<\/code> blocks.<\/li>\n\n\n\n<li><strong>ORAM bucket size<\/strong>: <code>Z = 4<\/code>.<\/li>\n\n\n\n<li><strong>FHE scheme<\/strong>: BFV with 128\u2011bit security, ciphertext modulus <code>q \u2248 2\u2076\u2074<\/code>.<\/li>\n\n\n\n<li><strong>Batch size<\/strong>: <code>Z\u00b7log\u2082 N = 4\u00b716 = 64<\/code> ciphertext slots per homomorphic evaluation.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">With these settings, a single logical read\/write requires:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>One homomorphic evaluation of the routing function per tree level (16 levels).<\/li>\n\n\n\n<li>One homomorphic eviction pass (also 16 levels).<\/li>\n<\/ol>\n\n\n\n<p class=\"wp-block-paragraph\">Both steps are executed in parallel across the 64 slots, giving a predictable wall\u2011clock time (e.g., ~200\u202fms on a modern GPU\u2011accelerated FHE server).<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Security notes<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Access\u2011pattern leakage<\/strong> is eliminated by ORAM\u2019s obliviousness.<\/li>\n\n\n\n<li><strong>Data\u2011value leakage<\/strong> is prevented by the semantic security of the FHE scheme.<\/li>\n\n\n\n<li>The combined construction remains secure under the standard <strong>IND\u2011CPA<\/strong> assumption for FHE and the <strong>ORAM security definition<\/strong> (indistinguishability of access sequences).<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>In summary<\/strong>, a constant\u2011time routine can be built by storing FHE\u2011encrypted blocks in a fixed\u2011bucket ORAM tree, using homomorphic tokens to traverse the tree uniformly, and performing parallel homomorphic evaluations for routing and eviction. This yields predictable latency while protecting both data values and access patterns.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Why combine ORAM and FHE? When both are used, an adversary learns nothing about the data values or the sequence of operations\u2014crucial for secure cloud computation on sensitive workloads. Core construction Step Operation (performed by the client) Operation (performed by the server) 1 Encrypt each data block with an FHE scheme \u2192 ciphertexts c_i. \u2014 &hellip; <\/p>\n<p class=\"link-more\"><a href=\"https:\/\/xn--y9aq2bc.com\/?p=1130\" class=\"more-link\">Continue reading<span class=\"screen-reader-text\"> &#8220;Constant\u2011time ORAM with Fully Homomorphic Encryption&#8221;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"","sticky":false,"template":"","format":"chat","meta":{"footnotes":""},"categories":[223,224],"tags":[],"class_list":["post-1130","post","type-post","status-publish","format-chat","hentry","category-llms","category-technical-solutions","post_format-post-format-chat"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/xn--y9aq2bc.com\/index.php?rest_route=\/wp\/v2\/posts\/1130","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/xn--y9aq2bc.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/xn--y9aq2bc.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/xn--y9aq2bc.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/xn--y9aq2bc.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1130"}],"version-history":[{"count":2,"href":"https:\/\/xn--y9aq2bc.com\/index.php?rest_route=\/wp\/v2\/posts\/1130\/revisions"}],"predecessor-version":[{"id":1133,"href":"https:\/\/xn--y9aq2bc.com\/index.php?rest_route=\/wp\/v2\/posts\/1130\/revisions\/1133"}],"wp:attachment":[{"href":"https:\/\/xn--y9aq2bc.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1130"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/xn--y9aq2bc.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1130"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/xn--y9aq2bc.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1130"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}