CINXE.COM
Witness Encryption and Null-IO from Evasive LWE
<!DOCTYPE html> <html lang="en"> <head> <meta charset="utf-8"> <meta name="viewport" content="width=device-width, initial-scale=1, shrink-to-fit=no"> <link href="/css/dist/css/bootstrap.min.css" rel="stylesheet"> <title>Witness Encryption and Null-IO from Evasive LWE</title> <link rel="stylesheet" href="/css/eprint.css?v=10"> <link rel="shortcut icon" href="/favicon.ico" type="image/x-icon" /> <link rel="apple-touch-icon" href="/img/apple-touch-icon-180x180.png" /> <style> a.toggle-open:after { content:' -'; font-weight: 800; } a.toggle-closed:after { content: " ›"; font-weight: 800; } .paper-abstract { white-space: pre-wrap; } #metadata dt { margin-top: 1rem; } #metadata dt + dd { /* gap between dt and first dd */ margin-top: .75rem; } #metadata dd { margin-left: 2rem; } #metadata dd.keywords { padding-bottom: .5rem; } span.authorName { margin-top: .5rem; font-style: italic; } </style> <script> MathJax = { tex: { inlineMath: [['$', '$'], ['\\(', '\\)']], displayMath: [ ['$$','$$'], ["\\[","\\]"] ], processEnvironments: false }, loader: { load: [ "ui/safe", "ui/lazy", ], }, options: { safeOptions: { allow: { URLs: "none", classes: "safe", cssIDs: "safe", styles: "safe", }, }, } }; </script> <script id="MathJax-script" async src="/js/mathjax/tex-chtml.js"></script> <meta name="citation_title" content="Witness Encryption and Null-IO from Evasive LWE"> <meta name="citation_author" content="Vinod Vaikuntanathan"> <meta name="citation_author" content="Hoeteck Wee"> <meta name="citation_author" content="Daniel Wichs"> <meta name="citation_journal_title" content="Cryptology ePrint Archive"> <meta name="citation_publication_date" content="2022"> <meta name="citation_pdf_url" content="https://eprint.iacr.org/2022/1140.pdf"> <meta property="og:image" content="https://eprint.iacr.org/img/iacrlogo.png"/> <meta property="og:image:alt" content="IACR logo"/> <meta property="og:url" content="https://eprint.iacr.org/2022/1140"> <meta property="og:site_name" content="IACR Cryptology ePrint Archive" /> <meta property="og:type" content="article" /> <meta property="og:title" content="Witness Encryption and Null-IO from Evasive LWE" /> <meta property="og:description" content="Witness encryption (WE) allows us to use an arbitrary NP statement $x$ as a public key to encrypt a message, and the witness $w$ serves as a decryption key. Security ensures that, when the statement $x$ is false, the encrypted message remains computationally hidden. WE appears to be significantly weaker than indistinguishability obfuscation (iO). Indeed, WE is closely related to a highly restricted form of iO that only guarantees security for null circuits (null iO). However, all current approaches towards constructing WE under nice assumptions go through iO. Such constructions are quite complex and are unlikely to lead to practically instantiable schemes. In this work, we revisit a very simple WE and null iO candidate of Chen, Vaikuntanathan and Wee (CRYPTO 2018). We show how to prove its security under a nice and easy-to-state assumption that we refer to as "evasive LWE" following Wee (EUROCRYPT 2022). Roughly speaking, the evasive LWE assumption says the following: assume we have some joint distributions over matrices $\mathbf{P}$, $\mathbf{S}$ and auxiliary information $\mathsf{aux}$ such that $$({\mathbf{S}\mathbf{B} + \mathbf{E}},{\mathbf{S} \mathbf{P} + \mathbf{E}'}, \mathsf{aux}) \approx_c ({\mathbf{U}},{\mathbf{U'}}, \mathsf{aux}),$$ for a uniformly random (and secret) matrix $\mathbf{B}$, where $\mathbf{U}, \mathbf{U}'$ are uniformly random matrices, and $\mathbf{E},\mathbf{E}'$ are chosen from the LWE error distribution with appropriate parameters. Then it must also be the case that: $$\mathbf{S}\mathbf{B} + \mathbf{E}, \mathbf{B}^{-1}(\mathbf{P}),\mathsf{aux}) \approx_c (\mathbf{U}, \mathbf{B}^{-1}(\mathbf{P}),\mathsf{aux}).$$ Essentially the above says that given $\mathbf{S}\mathbf{B} + \mathbf{E}$, getting the additional component $\mathbf{B}^{-1}(\mathbf{P})$ is no more useful than just getting the product $({\mathbf{S}\mathbf{B} + \mathbf{E}})\cdot \mathbf{B}^{-1}(\mathbf{P}) \approx \mathbf{S} \mathbf{P} + \mathbf{E}'$." /> <meta property="article:section" content="PUBLICKEY" /> <meta property="article:modified_time" content="2022-08-31T23:32:08+00:00" /> <meta property="article:published_time" content="2022-08-31T23:32:08+00:00" /> </head> <body> <noscript> <h1 class="text-center">What a lovely hat</h1> <h4 class="text-center">Is it made out of <a href="https://iacr.org/tinfoil.html">tin foil</a>?</h4> </noscript> <div class="fixed-top" id="topNavbar"> <nav class="navbar navbar-custom navbar-expand-lg"> <div class="container px-0 justify-content-between justify-content-lg-evenly"> <div class="order-0 align-items-center d-flex"> <button class="navbar-toggler btnNoOutline" type="button" data-bs-toggle="collapse" data-bs-target="#navbarContent" aria-controls="navbarContent" aria-expanded="false"> <span class="icon-bar top-bar"></span> <span class="icon-bar middle-bar"></span> <span class="icon-bar bottom-bar"></span> </button> <a class="d-none me-5 d-lg-inline" href="https://iacr.org/"><img class="iacrlogo" src="/img/iacrlogo_small.png" alt="IACR Logo" style="max-width:6rem;"></a> </div> <a class="ePrintname order-1" href="/"> <span class="longNavName">Cryptology ePrint Archive</span> </a> <div class="collapse navbar-collapse order-3" id="navbarContent"> <ul class="navbar-nav me-auto ms-2 mb-2 mb-lg-0 justify-content-end w-100"> <li class="ps-md-3 nav-item dropdown"> <a class="nav-link dropdown-toggle" href="#" id="navbarDropdown" role="button" data-bs-toggle="dropdown" aria-expanded="false"> Papers </a> <ul class="dropdown-menu me-3" aria-labelledby="navbarDropdown"> <span class="text-dark mx-3" style="white-space:nowrap;">Updates from the last:</span> <li><a class="dropdown-item ps-custom" href="/days/7">7 days</a></li> <li><a class="dropdown-item ps-custom" href="/days/31">31 days</a></li> <li><a class="dropdown-item ps-custom" href="/days/183">6 months</a></li> <li><a class="dropdown-item ps-custom" href="/days/365">365 days</a></li> <li><hr class="dropdown-divider"></li> <li><a class="dropdown-item" href="/byyear">Listing by year</a></li> <li><a class="dropdown-item" href="/complete">All papers</a></li> <li><a class="dropdown-item" href="/complete/compact">Compact view</a></li> <li><a class="dropdown-item" href="https://www.iacr.org/news/subscribe">Subscribe</a></li> <li><hr class="dropdown-divider"></li> <li><a class="dropdown-item" href="/citation.html">How to cite</a></li> <li><hr class="dropdown-divider"></li> <li><a class="dropdown-item" href="/rss">Harvesting metadata</a></li> </ul> </li> <li class="ps-md-3 nav-item dropdown"> <a class="nav-link dropdown-toggle" href="#" id="submissionsDropdown" role="button" data-bs-toggle="dropdown" aria-expanded="false"> Submissions </a> <ul class="dropdown-menu me-3" aria-labelledby="submissionsDropdown"> <li><a class="dropdown-item" href="/submit">Submit a paper</a></li> <li><a class="dropdown-item" href="/revise">Revise or withdraw a paper</a></li> <li><a class="dropdown-item" href="/operations.html">Acceptance and publishing conditions</a></li> </ul> </li> <li class="ps-md-3 nav-item dropdown"> <a class="nav-link dropdown-toggle" href="#" id="aboutDropdown" role="button" data-bs-toggle="dropdown" aria-expanded="false"> About </a> <ul class="dropdown-menu me-3" aria-labelledby="aboutDropdown"> <li><a class="dropdown-item" href="/about.html">Goals and history</a></li> <li><a class="dropdown-item" href="/news.html">News</a></li> <li><a class="dropdown-item" href="/stats">Statistics</a></li> <li><a class="dropdown-item" href="/contact.html">Contact</a></li> </ul> </li> </ul> </div> <div class="dropdown ps-md-2 text-right order-2 order-lg-last"> <button class="btn btnNoOutline" type="button" id="dropdownMenuButton1" data-bs-toggle="dropdown" aria-expanded="false"> <img src="/img/search.svg" class="searchIcon" alt="Search Button"/> </button> <div id="searchDd" class="dropdown-menu dropdown-menu-end p-0" aria-labelledby="dropdownMenuButton1"> <form action="/search" method="GET"> <div class="input-group"> <input id="searchbox" name="q" type="search" class="form-control" autocomplete="off"> <button class="btn btn-secondary border input-group-append ml-2"> Search </button> </div> </form> <div class="ms-2 p-1 d-none"><a href="/search">Advanced search</a></div> </div> </div> </div> </nav> </div> <main id="eprintContent" class="container px-3 py-4 p-md-4"> <div class="row mt-4"> <div class="col-md-7 col-lg-8 pe-md-5"> <h4>Paper 2022/1140</h4> <h3 class="mb-3">Witness Encryption and Null-IO from Evasive LWE</h3> <div class="author"><span class="authorName">Vinod Vaikuntanathan</span><span class="affiliation">, MIT</span></div> <div class="author"><span class="authorName">Hoeteck Wee</span><span class="affiliation">, NTT Research</span></div> <div class="author"><span class="authorName">Daniel Wichs</span><span class="affiliation">, Northeastern University</span><span class="affiliation">, NTT Research</span></div> <h5 class="mt-3">Abstract</h5> <p style="white-space: pre-wrap;">Witness encryption (WE) allows us to use an arbitrary NP statement $x$ as a public key to encrypt a message, and the witness $w$ serves as a decryption key. Security ensures that, when the statement $x$ is false, the encrypted message remains computationally hidden. WE appears to be significantly weaker than indistinguishability obfuscation (iO). Indeed, WE is closely related to a highly restricted form of iO that only guarantees security for null circuits (null iO). However, all current approaches towards constructing WE under nice assumptions go through iO. Such constructions are quite complex and are unlikely to lead to practically instantiable schemes. In this work, we revisit a very simple WE and null iO candidate of Chen, Vaikuntanathan and Wee (CRYPTO 2018). We show how to prove its security under a nice and easy-to-state assumption that we refer to as "evasive LWE" following Wee (EUROCRYPT 2022). Roughly speaking, the evasive LWE assumption says the following: assume we have some joint distributions over matrices $\mathbf{P}$, $\mathbf{S}$ and auxiliary information $\mathsf{aux}$ such that $$({\mathbf{S}\mathbf{B} + \mathbf{E}},{\mathbf{S} \mathbf{P} + \mathbf{E}'}, \mathsf{aux}) \approx_c ({\mathbf{U}},{\mathbf{U'}}, \mathsf{aux}),$$ for a uniformly random (and secret) matrix $\mathbf{B}$, where $\mathbf{U}, \mathbf{U}'$ are uniformly random matrices, and $\mathbf{E},\mathbf{E}'$ are chosen from the LWE error distribution with appropriate parameters. Then it must also be the case that: $$\mathbf{S}\mathbf{B} + \mathbf{E}, \mathbf{B}^{-1}(\mathbf{P}),\mathsf{aux}) \approx_c (\mathbf{U}, \mathbf{B}^{-1}(\mathbf{P}),\mathsf{aux}).$$ Essentially the above says that given $\mathbf{S}\mathbf{B} + \mathbf{E}$, getting the additional component $\mathbf{B}^{-1}(\mathbf{P})$ is no more useful than just getting the product $({\mathbf{S}\mathbf{B} + \mathbf{E}})\cdot \mathbf{B}^{-1}(\mathbf{P}) \approx \mathbf{S} \mathbf{P} + \mathbf{E}'$.</p> </div> <div id="metadata" class="col-md-5 col-lg-4 ps-md-5 mt-4 mt-md-0"> <h5>Metadata</h5> <dl> <dt> Available format(s) </dt> <dd> <a class="btn btn-sm btn-outline-dark" href="/2022/1140.pdf"> <img class="icon" src="/img/file-pdf.svg">PDF</a> </dd> <dt>Category</dt> <dd><a href="/search?category=PUBLICKEY"><small class="badge category category-PUBLICKEY">Public-key cryptography</small></a></dd> <dt>Publication info</dt> <dd>Published by the IACR in ASIACRYPT 2022</dd> <dt>Contact author(s)</dt> <dd><span class="font-monospace"> vinodv<span class="obfuscate"> @ </span>mit edu<br>wee<span class="obfuscate"> @ </span>di ens fr<br>wichs<span class="obfuscate"> @ </span>ccs neu edu </span> </dd> <dt>History</dt> <dd>2022-09-05: approved</dd> <dd>2022-08-31: received</dd> <dd><a rel="nofollow" href="/archive/versions/2022/1140">See all versions</a></dd> <dt>Short URL</dt> <dd><a href="https://ia.cr/2022/1140">https://ia.cr/2022/1140</a></dd> <dt>License</dt> <dd><a rel="license" target="_blank" href="https://creativecommons.org/licenses/by/4.0/"> <img class="licenseImg" src="/img/license/CC_BY.svg" alt="Creative Commons Attribution" title="Creative Commons Attribution"><br> <small>CC BY</small> </a> </dd> </dl> </div> </div> <p class="mt-4"><strong>BibTeX</strong> <button id="bibcopy" class="ms-2 btn btn-sm btn-outline-dark" aria-label="Copy to clipboard" onclick="copyBibtex()"> <img src="/img/copy-outline.svg" class="icon">Copy to clipboard</button></p> <pre id="bibtex"> @misc{cryptoeprint:2022/1140, author = {Vinod Vaikuntanathan and Hoeteck Wee and Daniel Wichs}, title = {Witness Encryption and Null-{IO} from Evasive {LWE}}, howpublished = {Cryptology {ePrint} Archive, Paper 2022/1140}, year = {2022}, url = {https://eprint.iacr.org/2022/1140} } </pre> <script> var bibcopy; function triggerTooltip() { console.log('setting tooltip'); } window.onload = triggerTooltip; function copyBibtex() { let range = document.createRange(); range.selectNode(document.getElementById('bibtex')); window.getSelection().removeAllRanges(); window.getSelection().addRange(range); document.execCommand('copy'); window.getSelection().removeAllRanges(); let bibcopy = document.getElementById('bibcopy'); let copyTooltip = new bootstrap.Tooltip(bibcopy, {trigger: 'manual', title: 'Copied!'}); copyTooltip.show(); setTimeout(function() { copyTooltip.dispose(); }, 2000); } </script> </main> <div class="container-fluid mt-auto" id="eprintFooter"> <a href="https://iacr.org/"> <img id="iacrlogo" src="/img/iacrlogo_small.png" class="img-fluid d-block mx-auto" alt="IACR Logo"> </a> <div class="colorDiv"></div> <div class="alert alert-success w-75 mx-auto"> Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content. </div> </div> <script src="/css/bootstrap/js/bootstrap.bundle.min.js"></script> <script> var topNavbar = document.getElementById('topNavbar'); if (topNavbar) { document.addEventListener('scroll', function(e) { if (window.scrollY > 100) { topNavbar.classList.add('scrolled'); } else { topNavbar.classList.remove('scrolled'); } }) } </script> </body> </html>