Evaluating encrypted Boolean functions on encrypted bits: secure decision-making on the black side

Rajesh Krishnan; Ravi Sundaram

doi:10.1117/12.2018574

29 May 2013 Evaluating encrypted Boolean functions on encrypted bits: secure decision-making on the black side

Rajesh Krishnan, Ravi Sundaram

Proceedings Volume 8754, Open Architecture/Open Business Model Net-Centric Systems and Defense Transformation 2013; 875409 (2013) https://doi.org/10.1117/12.2018574
Event: SPIE Defense, Security, and Sensing, 2013, Baltimore, Maryland, United States

Abstract

We present a novel approach for secure evaluation of encrypted Boolean functions on encrypted bits. Building upon Barrington’s work to transform circuits to group programs and the Feige-Kilian-Naor cryptographic protocol, our novel Fixed Structure Group Program construction for secure evaluation eliminates the need for an expensive Universal Circuit to hide the function. Elements on the Black side weave together and multiply two coordinated streams of random sequences of elements from an unsolvable group; the Boolean decision is recovered while preserving the confidentiality of the decision function and the input bits. The operation is fast and can be further sped up using parallel computation. Our approach can handle expressions with NC¹ complexity, which is the class of Acyclic Boolean Circuits with polynomial width and logarithmic depth in the size of the input. This efficiently parallelizable class includes nonmonotone Boolean expressions of equality, inequality/range, Hamming distance, Boolean matrix multiplication, and kof- m threshold matching operations. The combined benefits of scaling and expressivity of our approach enables secure decision-making on the Black side. Envisioned applications include confidential publish/subscribe systems (with empirically validated performance), secure content-oriented internetworks, confidential forwarding and firewalling rules, and cross-domain guards.

Citation Download Citation

Rajesh Krishnan and Ravi Sundaram "Evaluating encrypted Boolean functions on encrypted bits: secure decision-making on the black side", Proc. SPIE 8754, Open Architecture/Open Business Model Net-Centric Systems and Defense Transformation 2013, 875409 (29 May 2013); https://doi.org/10.1117/12.2018574

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available