Covert Computation: Ensuring Undetectable Engagement
Covert computation aims to conceal the fact that computation is occurring and hide engagement in certain tasks like secure computation, authenticated key exchange, and more. By making messages indistinguishable and utilizing steganographic channels, it becomes possible to keep the activities covert and information secure.
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
Short Concurrent Covert AKE (Short cAKE) Karim Eldafrawy SRI International Nick Genise Duality Technologies Stanislaw Jarecki University of California, Irvine Asiacrypt 2023
From secure computation to covert computation Secure computation (SC) of circuit C hides everything about everyone s inputs except for circuit outputs x y A A* B for C C(x,y) (or $ on ) However, SC does not hide that party B engages in SC, and that s already information
From secure computation to covert computation Secure computation (SC) protects the privacy of everyone s input but it reveals that a party engaged in SC for some task C x y A* B for C C(x,y) (or $ on ) Engaging in Secure Computation for some task reveals information: Private Auction: Secure Voting: MPC for some circuit C: reveals that you want to buy some good reveals that you are a voter reveals that you have reasons to run this MPC Authenticated Key Exchange (AKE): reveals a party who uses some credentials to authenticate to some desired counterparty Covert Authentication Question: Can we have a protocol that realizes AKE, but engagement in AKE is undetectable to non-credentialed entities?
Covert Computation Can we hide the fact that computation is taking place? Covert Computation (for circuit C) must hide even whether party B engages in a sec. comp. of C x y Adv B for C (or $ on ) Q: How can we hide that B follows protocol ? A: Make s messages indistinguishable from $ bits Q: How can we hide that B communicates $ bits? A: Run over a steganographic channel (= always sends $ bits) network control messages, picture files, music files, video, encryption (e.g. VPN router), other crypto (e.g. kleptography )
Covert Computation Can we hide the fact that computation is taking place? Covert Computation (for circuit C) must hide even whether party B engages in a sec. comp. of C y/ x Adv B/ for C (or $ on ) random beacon Q: How can we hide that B follows protocol ? A: Make s messages indistinguishable from $ bits Q: How can we hide that B communicates $ bits? A: Run over a steganographic channel (= always sends $ bits) network control messages, picture files, music files, video, encryption (e.g. VPN router), other crypto (e.g. kleptography )
Covert Computation Can we hide the fact that computation is taking place? Covert Computation (for circuit C) must hide even whether party B engages in a sec. comp. of C y/ x Adv B/ for C C(x,y) (or $ on ) random beacon Q: But doesn t output C(x,y) reveal that B runs [C] on some input y? A: Yes, but if circuit C=AKE then its output looks $ for all inputs: Outputs of Authenticated Key Exchange (AKE) are $ keys! In general covert MPC (for arbitrary circuit C) [CGOS 07]: Circuit C includes admissibility condition AC s.t. if AC(x,y)=0 then output is $, otherwise output is C(x,y)
Covert Computation: prior work vs. our results for C A/ B/ (or $ on ) [vAHL 05]: O(1)-round covert 2PC, security only for passive adversaries [CGOS 07]: O(sec.par.)-round covert general MPC (with active security) [GJ 10]: (sec.par.)-round lower-bound for covert MPC without CRS [CDJ 16]: 3-round covert secure Set Intersection in ROM [Jar 18]: O(1)-round covert general 2PC in CRS [Jar 14]: 6-round covert group-based Authentication from RSA (no concurrency) [KN 22]: O(1)-round group-based Authentication from LWE (no concurrency) Our results: 1-round (single simultaneous flow) covert group-based AKE 10x improvement over [Jar 14] in bandwidth: 350B/party using type-3 EC Provable in UC covert AKE model, covers composability and concurrency Tool: concurrently-secure covert Conditional KEM (covert CKEM) for any Language with Sigma-protocol Zero-Knowledge Proof
Covert Computation: whats easy & whats hard for C A/ B/ (or $ on ) Passive KE $ IND PKE ciphertext: ElGamal, Khyber $ [even with a key] CCA PKE ciphertext: Fujisaki-Okamoto, Cramer-Shoup $ Commitment $ Covert 2PC for passive adversaries [vAHL 05] Oblivious Transfer (for $ m s) ElGamal [NP01,AIR01] $ Garbled Circuits SKE ciphertext tuples $ [vAHL 05] ZK Proofs: Verifiable Non-Covert Prover(x,w) 1 Verifier(x) ZK proof Tools for enforcing honest protocol behavior 0 Verifier(x) $|Prover| ZK proof Commitment + Decommitment: Verifiable Non-Covert MAC s Signatures
Towards covert (group-based) AKE (cAKE) Assume root of trust Cert. Authority (CA) with a group public key gpk Assume CA issues certificates cert1,cert2, to end-users A B x =(gpkA,certA) / y=(gpkB,certB) / for cAKE KA KB (or $ on ) KA=KB if certA LvalidCert(gpkB)and certB LvalidCert(gpkA) (otherwise KA and KB independent) (*) simplification: inputs x and y must include also revocation info, and LvalidCert is modified to Lvalid-and-non-revoked-Cert (see the paper)
Towards covert (group-based) AKE (cAKE) Assume root of trust Cert. Authority (CA) with a group public key gpk Assume CA issues certificates cert1,cert2, to end-users A B x =(gpkA,certA) / y=(gpkB,certB) / for cAKE KA KB (or $ on ) KA=KB if certA LvalidCert(gpkB)and certB LvalidCert(gpkA) (otherwise KA and KB independent) How to achieve this? Consider authentication in the A-to-B direction: B (gpkB,certB) A (gpkA,certA) $ CA = COM(certA) ZKP[ CA LComCert(gpkB)] verifiable non-covert If cert = randomizable signature under gpk [Pointcheval-Sanders 16] then Sigma-protocol ZKP for LComCert(gpk) uses only 512 bits and 2 bilinear maps
Towards covert (group-based) AKE (cAKE) Assume CA issues certificates cert1,cert2, to end-users A B x =(gpkA,certA) / y=(gpkB,certB) / for cAKE KA KB (or $ on ) KA=KB if certA LvalidCert(gpkB)and certB LvalidCert(gpkA) (otherwise KA and KB independent) How to achieve this? Consider authentication in the A-to-B direction: B (gpkB,certB) A (gpkA,certA) $ CA = COM(certA) ZKP[ CA LComCert(gpkB)] verifiable non-covert If cert = randomizable signature under gpk [Pointcheval-Sanders 16] then Sigma-protocol ZKP for LComCert(gpk) uses only 512 bits and 2 bilinear maps
Covert AKE idea: replace ZKP with Covert CKEM Assume CA issues certificates cert1,cert2, to end-users B (gpkB,certB) A (gpkA,certA) $ CA = COM(certA) CKEM[ CA LComCert(gpkB)] $ ZKP[ CA LComCert(gpkB)] verifiable non-covert Covert Conditional KEM (Covert CKEM) for L ZK-Send[CGOS07], Conditional OT[J14], Implicit ZK[BCPW15], Witness Encryption (CA,gpkB) (certA,$com) (receiver) (sender) CKEM for L statement x witness w R S If w witness for x in L then KR=KS, o/w KR KS KR KS CKEM covertness property: (1) For any S*: interaction with R(w,x) $ for all x,w (2) For any R*: interaction with S(x) $ for all x
Properties of Covert CKEM for UC-secure cAKE (receiver) (sender) statement x CKEM for L witness w S R If w witness for x in L then KR=KS, o/w KR KS KR KS TRec Covertness: (1) For any S*: interaction with R(w,x) $ for all x,w (2) For any R*: interaction with S(x) $ if all x Zero-Knowledge: Efficient Trapdoor Receiver (TR) (= simulator) s.t. (3) TR(x) outputs KR s.t. KR=KSoutput by S(x) for all x (incl. x not in L) (4) For any S*: interaction with TRec(x)+KR R(x,w)+KR (i.e. even if S* sees R/TRec output KR) Statement-Postponed Zero-Knowledge: (5) TRec learns x after sending all its messages (but before computing KR) Strong Simulation-Soundness: there exists efficient extractor Ext s.t. (6) If R* distinguishes S(x) + KS from $ then ExtR*(x) outputs w for x in L, even if R* interacts with TRec( ) oracle on any x (even x = x), as long as each TRec( ) transcript differs from R* s transcript with S(x)
From -protocol to covert CKEM (DL example) witness w CKEM for LDL [Jar 14] x = gw R S If x = gw KS KR then KR=KS, o/w KS KR SIM for this HVZK: -protocol for L z $ , e $ a = f(x,e,z) = gz / xe a = gr e H(x,a) (RO) z = r + e w
From -protocol to covert CKEM (DL example) [Jar 14] (new in red) x = gw witness w CKEM for LDL R S If x = gw KS KR then KR=KS, o/w KS KR COM = Double Pedersen SPHF is for DLRepEq [CS 98] has trapdoor commitment allows for postponed- statement simulation -protocol for L covert CKEM for L a = gr C=COM( ) e H(x,a) (RO) e H(x,C) (RO) z = r + e w cost(CKEM)=cost( -prot.)+O(1) exp s SPHF[ C=COM( a=f(x,e,z) ) ] TRec(x): [for ZK] 1. pick e $ , z $ 2. set C as trapdoor commitment 3. when statement x revealed get KR SPHF[C=COM(a)] for a = f(x,e,z) = gz / xe KR KS 1-flow: SPHF flow needs x only! concurrency: TRec is straight-line
Summary / Open Problems 1. We showed round-minimal (single simultaneous flow) Universally Composable covert (group-based) AKE using type-3 curve [PS 16] and a DDH group in ROM (10x smaller bandwidth than [Jar 14]) 2. The essential tool is round-minimal concurrent Covert CKEM for any language with -protocol Some related open questions: Covert AKE from weaker assumptions? (No bilinear maps?) Covert AKE with perfect forward security? (Our cAKE has no PFS!) General composable covert computation? (Our cAKE is composable but Covert UC 2PC of [Jar 18] is subprocedure-revealing ) Covertness as a tool in Secure Computation? (e.g. [CDJ 16] reduce O(n2) to O(n) in data-matching problems )
