姚燕青新_基于非完美随机源的隐私问题的

1、 姚燕青 北京航空航天大学 基于非完美随机源的隐私问题的安全性研究 CACR 2015 Oct. 2324, 2015Latest ResultsYevgeniy Dodis, Yanqing Yao: Privacy with Imperfect Randomness. CRYPTO (2) 2015: 463-482.Yanqing Yao, Zhoujun Li: Achieving Differential Privacy with Bias-Control Limited Source. IACR Cryptology ePrint Archive 2015: 360 (2015).

2、 Submitted. group elementsfrom DH key exchangephysical sources Perfect RandomnessIdeality biometricdatasecret with partial leakage RealityImperfect SourcesNon-Extractable Sources (e.g., SV86,CG88,Dod01)Can cryptography be based on imperfect random secrets? p Extractable sources (e.g., vN51,CFG+85,Bl

3、u86)p allow for deterministic extraction of nearly perfect randomness p are good for (almost) anything possible with perfect randomnessp Non-extractable sources (e.g., SV sources)p sufficient for simulating probabilistic polynomial-time algorithms (e.g., VV85, SV86, CG88, Zuc96, ACRT99). p sufficien

4、t for authentication applications (e.g., MACs MW97, DKRS06, signature schemes DOPS04, ACM+14)p Are they sufficient for privacy applications Imperfect SourcesPrior work about privacyp SV sources are not sufficient for unconditionally secure symmetric encryption McInnes-Pinkas, CRYPTO 1990p SV sources

5、 are not sufficient for computationally secure encryption,commitment, zero-knowledge,secret sharing, etc. Dodis-Ong-Prabhakaran-Sahai, FOCS 2004p Suggesting traditional privacy requires an extractable source Bosley- Dodis, TCC 2007 p Even if SV source is efficiently samplable The above negative resu

6、lts hold Austrin-Chung-Mahmoody-Pass-Seth, CRYPTO 2014. p SV sources are provably sufficient for achieving Differential Privacy Dodis-(Lpez-Alt)-Mironov-Vadhan, CRYPTO 2012. There is a qualitative gap between traditional & differential privacy ! Question: Is differential privacy possiblewith mor

7、e realistic (i.e., less structured)sources than the SV source? bit encryption scheme weak bit commitment bit extractor bit T-secret sharingTraditional Privacy Differential Privacy PrivacyImpossibility of Traditional PrivacySV sourceBCL source No (Rn,)secure P exists,for some .weak source block sourc

8、e bit extractor bit encryption scheme weak bit commitmentbit T-secret sharingImpossibility of Differential Privacyis fixed, then no (Rn,)-DP & (Un,)-accurate M exists. Weak(k, n) ,where k n log() 6Block(k, m, n)，wherek m log() 8BCL(, b, n)，where b (log()+9)/log(1+)RnCompletely New Result！Achieving DP with BCL sourcesIf DP is possible, then b (log(?)+9)/log(1+).We introduce “Compact BCL consistent sampling”, and use a new truncation parameter to construct a DP mechanism with BCL sources. Study the impossibility of privacy in more complex scenarios . Develop and formalize